向量数据库HNSW算法

向量数据库构建好embedding后，需要通过相关算法进行检索，它常用到的相似性搜索算法有HNSW，HNSW算法是NSW算法改进而来,它是属于ANN算法中不同类别的图类别中的一种。

    节点与节点之间的连接方式可以形成3类图：正则图，随机图，正则和随机结合图（小世界），如下图1：

1.正则图

    在图论中根据一个点固定连接几根线来区分是几正则图，每个顶点都有相同数据的邻居的图，每个顶点的度相同，每个顶点的度为n，则被称为n-正则图，它的特点是聚类系数接近饱和时，聚类系数比较高，平均路径短，但是度会特别大如图1:

2.随机图

    随机图就是随机生成图，每个节点之间的连接是随机的，聚类系数相对较低，度也比较小。

3.小世界理论

    匈牙利作家F. Karinthy在1929年提出小世界现象，它与六度分离理论相关，但在描述和定义上有所不同。六度分离理论描述的是一个人给一个陌生人送信，它只能通过自己的熟人进行中转送信，每次中转找跟自己最熟的人，最后发现只需要中转5次，6个步骤就可以送到收信人手上。小世界理论表示若网络中任意两点间的平均距离L随网络格点数N的增加呈对数增长（即L ~ ln N），且网络的局部结构上仍具有较明显的集团化特征，则称该网络具有小世界现象。

    NSW算法就是通过构建一个小世界网络，通过黑色边来检索相邻点，通过红色长边(高速公路)来实现不同类节点的快速检索。它构造的网络如下图3，它通过任意一个蓝色的点，寻找该点的相邻节点，找到相邻节点距离绿色点最近的点，然后又从最近的点继续寻找最近点的点，直到找不到更近的点为止。

 HNSW算法是在NSW的基础上加上了跳表,这样效率更高，每一个点都有50%的概率进入上一层的链表，从而将NSW的计算复杂度由多重复杂度降到了对数复杂度，比如图4展示了查找38的过程。

    下图5是对HNSW的一个立体展示过程。