HNSW向量索引原理详解

层次可导航小世界图（Hierarchical Navigable Small World graphs）——Malkov 和 Yashunin 于 2016 年提出，后发表在 IEEE TPAMI——是 pgvector、Qdrant、Weaviate、Milvus、Lucene 和 Faiss 的默认索引。这个结构的本质比其名字简单：它是一个跳表，只不过"下一个"的含义变成了"在向量空间中更近"。

它是一个多维跳表

排好序的数值跳表由多层链表叠叠堆叠而成。最底层包含所有元素；每上一层都是下一层的随机采样。搜索时沿稀疏的顶层链表前进，直到越过目标，然后降一层，再前进，如此往复——对数级而非线性复杂度，且结构本身不要求全局有序，只需满足"小于"关系。

HNSW 就是将"小于"替换为"更近"的思路。每个向量是一个节点，每个节点被赋予一个最大层号，通过指数衰减的随机抽取得出——论文中使用 l = floor(-ln(U) * mL)，其中 mL = 1 / ln(M)——因此出现在第 l 层或更高层的概率为 M^-l。设 M = 16，则每 16 个节点有一个到达第 1 层，每 256 个有一个到达第 2 层；千万量级向量的顶层约为 log16(10^7) ≈ 5.8，即六层。在同一层内，每个节点维护到其近邻的有序链接；顶层稀疏且链接跨度大，底层密集且链接距离短。

查询到来时，搜索从最高层的固定入口节点开始，流程如下：

layer 5..1   贪心下降，beam width = 1：
               重复：
                 查看当前节点在该层的所有邻居
                 如果某个邻居比当前节点更接近 q，则移动到该邻居
                 否则降到下一层，保持在同一节点

layer 0      beam 搜索，beam width = ef_search：
               candidates = {entry}, results = {entry}
               当 candidates 非空时：
                 c = 最近且未访问的候选节点
                 如果 dist(c, q) > results 中最差结果且 |results| == ef：跳出
                 对 c 的每个邻居 n：
                   如果 n 未访问：加入 candidates 和 results
                 仅保留 results 中最好的 ef 个

返回           ef 个结果中最好的 k 个

上层是一种粗粒度的" teleport"：用少数几步 hops 将搜索带到向量空间的大致正确区域。所有精度都来自第 0 层的 beam 搜索，ef_search 就是 beam 宽度。它至少要等于 k，提高它会使搜索变慢但更准确——这个旋钮就是查询时全部的召回率/延迟权衡。

可以算一下计算量。每次扩展最多评估 M 个邻居，因此第 0 层搜索若扩展约 ef_search 个节点，大约需要 ef_search × M 次距离计算。取 ef_search = 40、M = 16，约为 640 次——对比一千万个向量。这个比例（四到五个数量级的减少），就是整个方案的核心价值。

实际调参顺序是：让 M 保持默认，ef_construction 设置到构建窗口能承受的上限（因为构建完成后就没成本了），然后根据实测召回率调整 ef_search。只有当高 ef_search 仍然达不到召回率目标时，才考虑增大 M——那是图本身对你的数据来说太稀疏的信号。

第 0 层链接：  2M * 4 bytes         = 128 B  (M = 16, 4 字节 id)
上层：         每个节点的期望节点数为 M/(M-1) = 1.067，
               因此额外的 0.067 层 * M * 4 bytes  =   4 B
                                                         -------
每个向量的图开销                                  ~132 B

对比向量本身（1536 维）：                        6144 B

  开销 = 2.1%          当 M = 16, d = 1536
  开销 = 4.3%          当 M = 32, d = 1536
  开销 = 8.4%          当 M = 32, d =  384

关键在于第三行。对于宽幅 float32 向量，图的开销微乎其微，没必要在 M 上省内存。但对于窄向量或量化向量，它占比很大——1536 维二进制量化的向量每个仅 192 字节，因此当 M = 32 时图的代价甚至超过向量本身。量化改变了内存的流向，而你原本忽略的图参数变成了关键所在。

为什么构建是昂贵的部分

插入一个节点的流程与 beam 宽度为 ef_construction 的搜索相同，然后选择邻居并修复它们的链接列表。因此构建大约需要 N × ef_construction × M 次距离计算：设一千万向量、ef_construction = 64、M = 16，约为百亿量级。这就是 HNSW 构建需要数小时的缘由，也是它虽然能很好并行却从不便宜的原因。

这也解释了内存需求。构建期间图必须驻留在内存中，因为每次插入都要遍历现有图。在 pgvector 中对应 maintenance_work_mem；超过时构建会溢出，并收到一条提示信息——告知从第几个元组开始图已不再能容纳，暗示构建将显著变慢。把这条提示当错误处理：调高参数然后重新开始，而不是等待一个已经慢了十倍的构建完成。

删除。移除一个节点会让那些唯一经过它的节点失去连接，因此引擎将节点标记为已删除但保留在图中。召回率和内存都会随 tombstone 比例下降，只能通过重建或压缩来恢复。

过滤搜索。贪心遍历是针对整个图的。如果大多数邻居不满足你的谓词，遍历就会停滞，此时只会得到过少的结果而不会报错。引擎通过额外链接、自适应策略或迭代扫描来应对——但这些都不是免费的。

ef_search 低于 k。请求 50 个结果但 beam 宽度只有 40 是不可能的。有些引擎会静默截断，因此召回率悄然下降而不是直接报错。

聚类或重复数据。数千个近乎相同的向量会将一个节点的邻居列表填满同一个东西的副本，浪费了图的连通性。建索引前先去重，可以同时提升召回率并缩小索引体积。

插入顺序。图依赖于节点的插入顺序，因此同一份数据上的两个索引并不相同，不同重建之间的召回率可能有微小波动。每次重建后都要实测召回率，而不是假设它会延续。

相关文章

Vector Databases Compared: What Actually Differs

Quantising Vectors: Binary, Scalar and Product Quantisation

Storing Vectors Cheaply: The Real Cost of 100M Embeddings