前言
HNSW用于近似最近邻搜索，下面将首先讲解HSNW的构建原理，为了方便读者阅读HNSW源码，避免被HNSW繁杂的参数弄的晕头转向，我还附上了HSNW索引的内存模型图，图中的参数对应HNSW源码中的参数，读者可以不理解参数所代表的意思时对着索引内存模型图。结尾附上了带中文注释的源码地址。
一、NSW原理
HNSW近邻搜索算法是在NSW近邻搜索算法的基础上改进而来，实际上NSW可以说的HNSW的组成部分。所以在介绍HNSW之前，我先介绍NSW算法原理，在理解了NSW原理之后，也就理解了百分之八十的HNSW原理。下面我们开始NSW的学习之旅。
在理想状态下，一个优秀的近邻搜索算法应该包含三点，一、构图算法的时间复杂度低。二、查找目标点的查找效率高。三、具备“高沙公路“机制（相距较远的点之间的连线，用于快速接近目标节点）。
上图为NSW算法的结构图（随意画的），假设有一个二维的平面，我们现在把图中的二维数据向量随机的逐个插入到平面直角坐标系中，他们的位置关系如上图所示。为了让读者更好的理解“高速公路机制”，我来解释一下上图的原理。黑色的线连接的两个点，表示这两个点是近邻关系。红色的线就是“高速公路”机制。假设我要查找的是图中的绿点query的近邻点，并且查找的出发点为图中的a节点（随机出发点），我们计算节点a的所有友节点距离节点query的距离，并得到节点b是a节点所有友节点中距离查找点query最近的点，于是就跳转到节点b，并以节点b为下一个出发点继续查找，发生在节点a上的过程一模一样的发生在节点b上，于是我们就找到了节点c，在遍历节点c的有节点时，我们发现节点c的所有友节点距离节点query的距离都没有比节点c本身距离节点query的距离更近，于是节点c就是我们要找的距离query最近的点。
通过上面的例子我们可以明显的感觉到“高速公路”机制在查找中起到的重要作用，通过“高速公路”我们可以快速的到达目标节点附近，大大的减少了节点之间的跳转，很大的提升了查找的效率。
接下来我来谈一谈“高速公路”机制形成的过程。在构图算法够造节点之间结构的时候，点是随机插入的，这就表明在早期的图构建的时候，出现“高速公路”的概率会非常的大，假如我们要构建的图由一百万个节点组成，节点的友节点数量设置为4。在插入第10个节点的时候，我只能在前9个节点中选出4个距离最近的友节点，我选择的余地很小，只有9个节点可供选择，所以选出来的4个友节点基本上并不是真正意义上的距离当前节点最近的友节点，这时候“高速公路”就出现了。那么在什么时候更加容易出现呢？这个问题的答案很明显，只有在构建图早期选择余地小的时候更容易出现高速公路。举个极端的例子，当我在插入第一百万个节点时，图结构已经被训练了999999，所以在当前图中查找到的友节点一定是当前图中真正意义上的近邻。
（2）NSW中逐渐被取代的“高速公路”
上一节中，我们讲到了“高速公路”机制为NSW近邻搜索所带来的好处。本节标题为什么说NSW中的“高速公路”会被逐渐取代呢。为了解释NSW中的“高速公路”为什么会被逐渐取代，接下来我们来聊一聊NSW近邻图构建过程中的细节。
上图为NSW算法的结构图（认真画的），假设有一个二维的平面，我们现在把图中的二维数据向量按照a、b、c、d、e、f的顺序随机逐个插入到平面直角坐标系中，并且节点的友节点数量设置为4。
第一步：当a节点插入图中时只有它自己，所以没有友节点可以选择，a->0。
第二步：当b节点插入图中时，只有a节点供选择（不管距离是不是接近），于是只能将b节点的友节点指向a，并且a节点也更新自己的友节点，因为a节点的友节点数量为0，没有超过4，所以更新a节点的友节点指向b，这样就在a节点和b节点之间添加了双向的箭头，a->b、b->a。
第三步：当c节点插入图中时，只有a节点和b节点课供选择，所以b节点的友节点只能指向a节点和b节点，并且更新a节点和b节点的友节点，因为a节点和b节点当前的友节点数量还是1，所以直接加入c节点为友节点，a-73->b-90->c、b-73->a-88->c、c-88->b-90->a。
第四步：当d节点插入图中时，只有a节点、b节点和c节点可供选择，所以d节点的友节点只能指向a节点、b节点和c节点，并且更新a节点、b节点和c节点的友节点，因为a节点、b节点和c节点当前的友节点数量还是2，所以直接加入d节点为友节点，a-73->b-90->c-120->d、b-73->a-85->d-88->c、c-39->d-88->b-90->a、d-39->c-85->b-120->a。
第五步：当e节点插入图中时，只有a节点、b节点、c节点和d节点可供选择，所以d节点的友节点只能指向a节点、b节点、c节点和d节点，并且更新a节点、b节点、c节点和d节点的友节点，因为a节点、b节点、c节点和d节点当前的友节点数量还是3，所以直接加入e节点为友节点，a-48->e-73->b-90->c-120->d、b-73->a-85->d-88->c-99->e、c-39->d-59->e-88->b-90->a、d-39->c-85->b-101->e-120->a、e-48->a-59->c-99->b-101->d。
第六步：这一步是关键的一步，也是解释为什么“高速公路”会被短边所取代的一步。注意三点，一、目前结构中的所有节点的友节点数量都为4。二、4个友节点是所有节点友节点数量的上限。三、每个节点之间都是双向箭头连接。当f节点插入图中时，有a节点、b节点、c节点、d节点和e节点5个节点可供选择。因为友节点的上限为4个，所以f节点只能选中这5个节点中离自己最近的四个节点作为自己的友节点即a节点、b节点、c节点和d节点。当插入f节点后，相应的更新a节点、b节点、c节点和d节点的友节点。a-48->e-73->b-90->c-120->d、b-52->f-73->a-85->d-88->c-99->e、c-39->d-59->e-87->f-88->b-90->a、d-39->c-56->f-85->b-101->e-120->a、e-48->a-59->c-99->b-101->d、f-52->b-56->d-87->c-121->a
更新a: f节点和a节点之间的距离为121，大于a节点友节点中距离a节点最远的节点d（120），所以a节点不需要更新友节点。a-48->e-73->b-90->c-120->d
更新b： f节点和b节点之间的距离为52，小于b节点友节点中距离b节点最远的节点e（99），所以b节点剔除当前最远的友节点e，并加入新的节点f。b-52->f-73->a-85->d-88->c-99->e
更新c： f节点和c节点之间的距离为87，小于c节点友节点中距离c节点最远的节点a（90），所以c节点剔除当前最远的友节点a，并加入新的节点f。c-39->d-59->e-87->f-88->b-90->a
更新d： f节点和d节点之间的距离为56，小于d节点友节点中距离d节点最远的节点a（120），所以d节点剔除当前最远的友节点a，并加入新的节点f。d-39->c-56->f-85->b-101->e-120->a
通过上面六个点的插入，不难发现，节点的友节点在新的节点插入的过程中会不断的被更新，节点友节点中的长边“高速公路”会不断的随着新的节点的插入被短边所取代，所以就有了本节标题中所说的“逐渐被取代的“高速公路””。
以上内容就是NSW算的全部内容。
（3）HNSW算法原理
接下来开始我们的正文——HNSW算法的介绍，通过上面的讲解，其实我已经讲解了HNSW80%的内容。上一节中我讲到NSW图结构中的“高速公路”会随着点的插入逐渐被短边所取代，所以在图结构最终构建完成后，图结构中的“高速公路”（长边）将会所剩无几，那么“高速公路”在查找过程中所带来的优势也会变得微乎其微。
那么怎么样让NSW中的“高速公路”保持一定的数量呢？那就是将NSW和跳表结合起来，所以我们先来看看跳表的原理。
如上图所示，原始链表为有序链表，原始链表中的每个节点都有50%的概率添加到一级索引层，而一级索引层的节点同样也有50%的概率添加到二级索引层。当我现在要查找图中绿色节点32时，我可以分两种方法查找。方法一：在原始链表中查找，那么需要跳转11次才能到达绿色节点。方法二：先在二级索引中查找，经过两次跳转到达30节点，然后从下一级的30节点开始查找，最后再到原始链表查找，那么算上层之间的跳 转，只需要跳转6次便可到达绿色节点。
跳表通过将节点随机的分层，保证了上层结构为“高速公路”，底层为精细查找，通过上层“高速公路”快速接近目标查找点，那么HNSW就是NSW和跳表的结合体。
如下示意图图所示，读者应该可以明显的感觉的跳表和NSW的结合给搜索带来的优势。
以上内容就是对HNSW原理的个人总结。有不准确或不到位的地方希望读者指出。如果想要进一步了解HNSW的代码实现，请到我的github上下载源码，代码来自于https://github.com/kakao/n2.git，我只是对里面的参数和关键代码添加了注解，希望可以帮助读者更加轻松的理解代码意思，下载地址为：https://github.com/MartinNum/HNSW_explain.git。下面附上内存模型图，图中的参数对应代码中的参数，读者可以结合内存模型图理解代码。
