HNSW向量索引原理
HNSW向量索引原理
当知识库规模达到百万甚至千万级别时，如果每次查询都需要与所有向量计算相似度，搜索效率会非常低。因此，在工程实践中通常会引入ANN（Approximate Nearest Neighbor，近似最近邻）算法，通过构建索引结构减少搜索范围。其中，HNSW（Hierarchical Navigable Small World，分层可导航小世界图）是目前应用非常广泛的一种向量索引结构。
我认为理解HNSW主要需要解决三个核心问题：
第一，HNSW的分层结构是什么样的；
第二，一个新的Chunk是如何加入HNSW索引的；
第三，查询时Query如何从最高层逐步搜索到底层，并最终返回TopK结果。
一、HNSW的分层结构是什么？
HNSW本质上是一种多层图结构，它不是像传统数据库索引那样通过数据排序关系建立树，而是通过向量之间的相似度建立节点之间的连接关系。假设HNSW有5层：
Layer 4（最高层）
Layer 3
Layer 2
Layer 1
Layer 0（最低层）其中，Layer 0是最底层，也是最完整的一层，所有向量节点都会存在于这一层。而越往上的层，节点数量越少，主要作用是帮助查询快速定位目标区域。
例如，一个知识库中存在大量Chunk：
Layer 0:
A ---- B ---- C ---- D ---- E ---- F ---- G
Layer 1:
A -------- C -------- E
Layer 2:
C -------- E
Layer 3:
E可以看到，Layer 0包含所有节点，而高层只是从底层节点中抽取出来的一部分节点。
这种结构类似现实中的地图系统：高层像高速公路，节点数量少，但可以快速跨越较大的范围；中间层像城市道路，用于进一步缩小搜索范围；最低层像普通街道，包含所有节点，用于最终精细查找。
二、HNSW和B+树的关系
理解HNSW时，可以类比MySQL中的B+树索引。
B+树通过多层索引结构减少搜索范围：
Root
↓
Index层
↓
Leaf层查询时，从根节点开始，根据Key大小不断向下选择路径，最终定位到叶子节点。例如查询id=100时，如果当前节点值为50，由于100大于50，因此继续向右子树查找；如果查询值小于50，则继续向左子树查找。
HNSW虽然同样采用了多层结构，但是它并不是树，而是一种图结构：
Layer 4
↓
Layer 3
↓
Layer 2
↓
Layer 1
↓
Layer 0其中，高层负责快速导航，低层负责更加精细的搜索。
两者最大的区别在于：B+树依靠数据排序关系进行导航，例如根据Key大小判断应该进入左子树还是右子树；而HNSW依靠向量距离进行导航，例如比较当前节点和Query向量的相似度，选择距离最近的节点继续搜索。
因此可以简单理解为：
- B+树是按照数据大小查找数据；
- HNSW是按照向量相似度查找数据。
三、为什么一个Chunk会出现在多个层？
HNSW中的一个节点并不是只存在于某一层，而是根据随机策略决定它能够出现的最高层。
例如，现在有一个新的Chunk：
Chunk AHNSW会随机决定它的最高层。
假设随机结果：
最高层 = Layer 2那么Chunk A会存在于：
Layer 2
Layer 1
Layer 0但是不会存在于：
Layer 3
Layer 4也就是说：
如果一个节点出现在某一层，那么它一定会出现在比它更低的所有层。
例如：
Layer 3:
A
Layer 2:
A
Layer 1:
A
Layer 0:
A这里每个A实际上表示的是同一个Chunk，只是在不同层拥有不同的邻居关系。
这一点和B+树有一定相似性：B+树中的索引层保存叶子节点的导航信息，而HNSW中的高层保存底层节点的导航关系。
四、HNSW索引是如何构建的？
当一个新的Chunk加入向量库时，HNSW并不是简单地随机放入某个位置，而是通过随机分层和近邻连接两个步骤完成构建。
首先，HNSW会随机决定该节点的最高层。
例如：
Chunk A
随机结果：
最高层 = Layer 3那么：
Layer 3 √
Layer 2 √
Layer 1 √
Layer 0 √都会存在Chunk A。
其次，在每一层中，HNSW会寻找距离较近的节点，并建立连接。
例如Layer 0中已经存在：
B -------- C -------- D现在加入A。
系统计算A与附近节点的距离：
A-B距离较近
A-C距离较远
A-D距离较远于是建立连接：
A -------- B -------- C -------- D最终，每一层保存的并不是完整文本内容，而是节点以及节点之间的邻居关系。
可以理解为：
节点 = Chunk对应的向量
边 = 两个向量之间的相似关系需要注意的是，HNSW并不存在“区域划分”的概念，它不是把向量空间划分成区域A、区域B、区域C，而是通过图结构让节点之间形成可导航路径。
五、HNSW查询过程是什么？
假设用户输入：
苹果公司2025年的营收是多少？首先，Query会通过Embedding模型转换成向量，然后进入HNSW索引进行搜索。
搜索会从最高层开始。
例如Layer 3：
A -------- B -------- C计算Query和三个节点的距离：
Query-A = 10
Query-B = 3
Query-C = 8发现B距离Query最近，因此当前搜索节点变为B。
接下来进入下一层。
这里有一个非常容易误解的地方：很多人认为Layer 3中的B需要通过一条边连接到Layer 2中的某个节点。
实际上并不是这样。
HNSW不同层之间不存在跨层边。正确理解是：如果Layer 3存在节点B，那么Layer 2、Layer 1、Layer 0中一定也存在同一个节点B。
因此下降过程实际上是：
Layer 3中的B
↓
Layer 2中的B进入下一层后，再从Layer 2中B的邻居开始继续搜索。
例如Layer 2：
A ---- B ---- D继续计算：
Query-A
Query-D如果发现D距离更近：
B → D然后继续下降。
整个搜索过程可以理解为：
最高层快速定位方向
↓
中间层不断缩小范围
↓
Layer 0进行精细搜索六、最终TopK如何返回？
最终搜索会来到Layer 0。
因为Layer 0包含所有Chunk节点，并且连接最密集，所以它负责最终的近邻搜索。
例如最终找到候选节点：
Chunk A
Chunk B
Chunk C
Chunk D然后计算这些候选节点与Query的真实距离并排序：
Top1: Chunk B
Top2: Chunk A
Top3: Chunk D最终返回TopK结果。
在RAG系统中，这些召回的Chunk通常还会继续进入Reranker模型进行重新排序，然后选择最相关的几个上下文交给LLM生成答案。
七、总结
HNSW可以简单理解为：给所有Embedding向量建立一个分层近邻图，高层节点较少，用于快速定位搜索方向；低层节点较多，用于最终精细搜索。
它的核心流程如下：
第一，构建索引时，每个Chunk随机决定自己的最高层，然后加入该层以及下面所有层，并在每层与附近节点建立连接。
第二，查询时，Query从最高层开始搜索，找到当前最近节点后，使用同一个节点进入下一层，因为该节点一定存在于所有更低层。
第三，最终在Layer 0完成精细搜索，并返回距离Query最近的TopK向量。
因此，HNSW和B+树最大的相似点是：两者都通过多层结构减少搜索范围。
最大的区别是：B+树按照数据排序关系进行导航，而HNSW按照向量之间的相似度进行导航。