向量检索快，不是因为算得少：HNSW 的分层图在替你做取舍
HNSW 是当下向量数据库最常用的近似最近邻索引：它把向量组织成一张分层近邻图，上层稀疏、边长，负责快速跳到目标区域，底层稠密，负责在小范围内细找。它快的前提是放弃精确性，返回的是近似结果，召回率由图的构建质量与 efSearch、M 等参数共同决定。最常见的误区是把它当精确索引、以为调大 efSearch 就能解决一切，以及在带元数据过滤时先取 top-k 再过滤，导致结果不足 k 条。读完你能说清分层、邻居选择与搜索终止的机制，并知道怎样按召回率和内存预算调参。
是什么
HNSW（Hierarchical Navigable Small World，分层可导航小世界图）是一种基于图的近似最近邻索引，也是目前主流向量数据库的默认索引类型。一句话直觉：它像查地图时先走省际高速跳到目标城市，再换市区道路，最后步行到门牌号——上层图节点少、连接远，负责大跨度跳跃；底层图包含全部节点，负责精细定位。
需要先分清两个概念：向量数据库是系统，负责向量的存储、写入、过滤、持久化、分片与一致性；HNSW 只是其中的索引结构，解决"给定一个查询向量，怎样在毫秒级找出最相似的 k 条"。典型场景包括 RAG 的知识库召回、以图搜图、音频指纹、推荐系统的粗排召回、海量文本去重。这些场景的共同点是数据量大到无法逐条算距离，又允许结果有极小的偏差。
核心原理
HNSW 的第一层设计是分层。每个向量被随机分配一个最高层号，第 0 层包含全部向量，越往上节点越少。若记参数 M 为每个节点的目标连接数，则一个向量出现在第 l 层及以上的概率约为 M 的 -l 次方，呈指数衰减。这个随机分配与向量本身长什么样无关，只由随机数决定；实现里通常取 level = floor(-ln(U) * mL)，其中 mL = 1/ln(M)。因为上层节点稀疏而连接数上限相同，上层的边天然更长，起到的正是"高速公路"的作用。
第二层设计是构建时的邻居选择。插入一个新向量时，先从顶层入口点开始做贪心搜索，逐层下降到它自己的最高层，把每层找到的最近点当作下一层的入口。在它存在的每一层，用宽度为 efConstruction 的 beam search 找出候选邻居，再从中挑最多 M 个（第 0 层是 2M）建立双向连接。这里不能简单取最近的 M 个：如果几个向量挤在一起，彼此连成一个小团，图就会形成"孤岛"，搜索一旦走进去就出不来。所以论文给出一个多样性启发式——候选 c 只有在"它到新点的距离"小于"它到某个已选邻居的距离"时才被接纳，从而逼着节点连向不同方向。邻居的连接数超限时，也按同样规则裁掉最没价值的那条边。
第三层设计是查询。从顶层入口点出发，在第 1 层及以上只做贪心：不断走向比当前点更近的邻居，直到局部最优，然后带着这个点下沉一层。到了第 0 层，改用大小为 efSearch 的候选池：一个最小堆存放待探索节点，一个最大堆存放当前最好的若干结果；每次弹出最近的候选，若它已经比结果堆里最远的那个还远、且结果已满，就立刻停止。最后从结果堆里取前 k 个。
import heapq
def search_layer(graph, q, entry, ef, dist):
visited = {entry}
cand = [(dist(q, entry), entry)] # 小顶堆：待探索
best = [(-dist(q, entry), entry)] # 大顶堆：当前最好的 ef 个
while cand:
d, u = heapq.heappop(cand)
if len(best) >= ef and d > -best[0][0]:
break # 最近的候选都比结果里最差的远，收工
for v in graph[u]:
if v in visited:
continue
visited.add(v)
dv = dist(q, v)
if len(best) < ef or dv < -best[0][0]:
heapq.heappush(cand, (dv, v))
heapq.heappush(best, (-dv, v))
if len(best) > ef:
heapq.heappop(best)
return [v for _, v in best]复杂度上，层数约为对数级，每层只访问常数个邻居，因此距离计算次数大致随数据量呈对数增长，而暴力检索是线性。代价藏在两处：一是图本身要占内存，二是"贪心 + 剪枝"没有任何正确性保证，可能错过真正的最近邻。
常见考点与误区
- 误区一：HNSW 返回的就是精确的 k 个最近邻。 错。它是近似索引，
efSearch再大也只是"更可能"找到，不构成保证。面试里正确的答法是给出 recall@k 的定义：返回结果与暴力搜索结果的重合比例，并说明召回率与延迟是一条可以调的曲线，而不是一个固定指标。 - 误区二：召回不够就无脑调大 efSearch。 查询参数只能在图已经建好的前提下挖潜。如果建索引时
efConstruction太小、M太小，图的质量上限已经被锁死，查询端再怎么加宽也只是在烂图上多走几步。反过来，efConstruction只影响构建时间与图质量，对查询延迟没有直接影响，这一点常被答混。 - 考点三：带元数据过滤的查询怎么做。 典型错误是先取 top-k 再按条件过滤（post-filter）：过滤选择性一高，k 条可能只剩两三条，接口却仍然返回"成功"。先过滤再在图里搜（pre-filter）也不稳：被过滤掉的节点会让图断开，遍历可能困在局部。工程上的解法是把高频过滤字段做成分区或子索引，或者使用支持过滤感知遍历的实现；选择性极高时，直接暴力扫描反而更快。
- 考点四：删除和更新怎么处理。 多数实现不做真正的原地删除，而是打删除标记（tombstone），节点和边仍留在图里。于是频繁更新会让图越来越"脏"：内存不降、无效候选变多、召回和延迟一起劣化。更新本质上是删旧插新，需要靠段合并（compaction）或定期重建来回收，这也是向量库写入放大明显的原因之一。
- 考点五：内存只算向量本身。 一条 768 维 float32 向量是 3 KB，一亿条就是约 307 GB；此外第 0 层每个节点最多存 2M 个邻居 id，M=16 时约 128 字节/条，一亿条再添十几 GB，还没有算上层、元数据和索引开销。所以"能不能全放内存"往往由原始向量决定，量化才是把那 307 GB 压下来的主要手段。
实践建议
- 用 ground truth 调参，不要抄默认值。 采样几千条查询，用暴力检索算出真 top-k，再扫不同的
efSearch，画出召回率对 p99 延迟的曲线，选满足业务召回的最小值。M的起点可以取 16–32，efConstruction取 200–500，高维或高召回场景往上加；先固定构建参数把库建好，再单独调查询参数，避免两个变量一起动。 - 过滤字段提前规划。 上线前统计各过滤条件的命中比例，把常用且选择性高的字段做成独立分区或子集合；确认所选实现是否支持过滤感知的图遍历。如果业务经常"按租户 + 时间 + 标签"组合过滤，分区键选错，后面调什么参数都救不回来。
- 把删除率和重建成本纳入容量规划。 监控被标记删除的比例，设定阈值触发段合并或重建；批量导入用一次性构建，避免逐条插入把构建成本摊成十几倍。需要低延迟更新时，接受"新数据进小段、后台合并"的架构，而不是期望索引原地变干净。
- 内存不够时先量化再分片。 SQ8 能把 float32 压到四分之一，PQ 更激进但距离估计误差更大，通常用于粗排或与全精度重排配合。分片时注意每片各取 k 条再归并即可，不要每片取全量；跨片归并的堆操作要计入总延迟。
一句话总结：HNSW 用分层图和多样性剪枝把线性扫描压成对数级查找，代价是召回不再有保证；把它当成可调的近似索引，参数与过滤策略才谈得上正确。