HNSW 与近似最近邻

RAG 工程化深水考 5 题讲解 1 段

向量检索的默认索引。分层图 + 贪心下沉把 O(N) 降到近似 O(log N)，代价是召回不再是 100%，而且图结构常驻内存。M、ef_construction 定索引质量，ef_search 是唯一能在线拧的旋钮 —— 拿延迟换召回。

也叫：HNSW · ANN · 近似最近邻 · ef_search · ef_construction · 向量索引

原理拆解：HNSW出自 T2-4

上层跳得远，下层找得准

多层小世界图：从顶层入口贪心下沉，复杂度从暴力的 O(N) 降到大约 O(log N)

顶层 · 城市级节点只有北京、上海、广州这样的节点，你一步跳到上海上层稀疏，用来「长距离跳跃」

中层 · 上海各个区在这一层跳到黄浦区，范围收窄一圈每层贪心走向离目标更近的邻居，走不动了就下沉一层

底层 · 街道和店铺所有节点都在这一层，在附近小范围精找，输出 Top-K下层稠密，用来「精细定位」；每层的边连成一张小世界网络，任意两点跳几步就能到

三个旋钮（建好之后只剩一个还能动）

参数	作用	调大的后果	改它要不要重建
`M`	每个节点的邻居数（图的稠密度）	召回↑、内存↑、构建慢	要重建
`ef_construction`	建索引时的候选队列长度	索引质量↑、建索引更慢	要重建
`ef_search`	查询时的候选队列长度	召回↑、查询变慢	不用，运行时直接调

一句很实在的工程回答：「召回不够，先调 ef_search 看看」—— 它是唯一能在线调的旋钮，不重建索引就能试。而 M 和 ef_construction 一旦建好就固定了。

其他索引：IVF 先聚类、只搜几个簇，内存友好但召回略低；DiskANN 把索引放 SSD，适合内存放不下的超大规模；量化（标量／乘积／二值）用精度换内存，能压到原来的几分之一。

代价落在三处：图结构常驻内存，涨到千万级时先顶不住的是内存（开篇那个故障就是它）；召回不是 100%，ef_search 调太小会漏；删除只能软删，打标记跳过，删多了得重建。

HNSW（Hierarchical Navigable Small World，分层可导航小世界）是目前最主流的 ANN 索引，pgvector、Qdrant、Milvus 默认都用它。

想象你要从北京找上海某条街的一家店：

HNSW 就是这个结构——多层图，上层稀疏用来"长距离跳跃"，下层稠密用来"精细定位"。每层的节点通过边连成一张"小世界"网络（任意两点间跳几步就能到），检索时从顶层入口出发，每层贪心地走向离目标更近的邻居，走不动了就下沉一层，直到底层输出 Top-K。

复杂度从暴力检索的 O(N) 降到大约 O(log N)——这就是它能撑起毫秒级检索的原因。