HNSW（Hierarchical Navigable Small World，分层可导航小世界）是目前向量库里最常见的 ANN（Approximate Nearest Neighbor，近似最近邻）索引之一。Milvus、Faiss、pgvector、Elasticsearch 的稠密向量检索，底层很多都绕不开它。

一句话：在高维向量图上做「先粗后细」的贪心导航，用近似换毫秒级延迟。

读完本文，你应该能：

  1. 说清 NSW 和「分层」各自解决什么问题
  2. 画出从上到下的检索路径
  3. 知道落地时 M、efConstruction、efSearch 怎么调

1. 问题从哪来？

传统库用 B+ 树一类结构做精确查找；向量检索要找的是「语义最近」——比如在 1536 维空间里找离 Query 最近的 Top-K Chunk。

暴力做法是和全库算一遍距离，准确但 $O(N)$，数据一大就扛不住。ANN 接受一点召回损失，把查询压到接近 $O(\log N)$。HNSW 是其中工程表现最好的一类。

2. 小世界图（NSW）

先把每个向量当成图上的一个点，和若干近邻连边，得到一张 Navigable Small World（可导航小世界）图。

  • 六度分割直觉： 任意两点之间，往往只要很少几跳（Hop）就能走到附近
  • 查询方式：贪心路由。 从某个入口点出发，反复走到「当前邻居里离目标更近」的点，直到局部最优

类比导航：先飞到目标城市（大步），再打车到城区（中步），最后走到门牌号（小步）。NSW 只有「一层密网」时，点一多就容易在局部迷路，或者路径变长。

3. 分层：HNSW 的核心

HNSW 借鉴 Skip List（跳表）的思路，把同一张向量图叠成多层：

1
2
3
4
5
Top Layer（稀疏）   :  [A] --------------------------> [Z]     大跨度跳转
                         |                               |
Middle Layer        :  [A] --------> [M] ------------> [Z]     中等粒度
                         |            |                  |
Bottom Layer（密集）:  [A]->[B]->...->[M]->...-------->[Z]     精细局部搜索

规则很简单：

层 特点 作用
顶层 节点少、边「长」 快速锁定大致区域
中间层 逐渐变密 缩小候选范围
底层 包含全部向量 在邻域里精修 Top-K

检索流程：

  1. 从最高层某个入口点开始贪心走，走到该层局部最优
  2. 以该点为入口降到下一层，继续贪心
  3. 到底层后扩大候选集，输出距离最近的 Top-K

插入时每个点会随机分配一个最高层号（上层更稀），再在各层用类似搜索的过程选邻居连边。上层像高速公路，底层像小路——这就是「Hierarchical」比单层 NSW 稳、也更快的原因。

4. 和 RAG / 向量库的关系

在 Graph RAG、Naive RAG 里，向量侧的任务通常是：听懂口语 Query，吐出能跟后续流程 join 的 ID + score。HNSW 管的是「怎么在海量 Embedding 里把这一步做快」。

经验量级（视维度、机器、参数而定）：

  • 延迟： 百万～千万级向量，单次查询常见在数毫秒到十几毫秒
  • 召回： 调参得当，Recall@K 往往能到 95%～98%+（仍是近似，不是暴力 100%）

它和「选 Milvus 还是 ES」是两层问题：引擎决定过滤、运维、混合检索怎么接；HNSW 的参数决定召回和延迟的杠杆。

5. 两个必调参数

参数 含义 调大之后 常见范围感
M 每个节点最多连多少条边 召回↑，内存↑，建索引更慢 常试 16～64
efConstruction 建索引时候选队列宽度 图质量↑，构建更慢 通常明显大于 M
efSearch 查询时候选队列宽度 召回↑，延迟↑ 按延迟预算往上加，直到召回够用

实务上可以记：

  • 内存紧、只要「够用」召回 → M 别盲目拉满
  • 线上抖延迟 → 先动 efSearch，比动 M 便宜（M 要重建索引）
  • 离线可以建得「贵」一点（高 efConstruction），换线上更稳的图

6. 小结

HNSW = 多层小世界图 + 自上而下的贪心导航。

把它想成向量空间里的高速公路系统：上层负责跨越，底层负责精修。理解了这套结构，再去看向量库文档里的 M / ef，就不会只剩「抄默认值」了。