HNSW 算法学习与项目实践：从近似最近邻到向量检索工程

作者: lorixyu

发表于2026-05-17

更新于2026-05-17

总字数: 8.4k字

预估阅读时长: 27分钟

访问量:

本文旨在理解为什么需要 HNSW、它如何用多层图做近似最近邻搜索、M / ef_construction / ef_search 等参数到底控制什么，以及它和 IVF、PQ、LSH、Annoy、DiskANN、BM25 等相关算法分别适合什么场景。

HNSW 是一种基于分层小世界图的近似最近邻索引。第 0 层包含所有向量，负责最终精细搜索；高层只包含部分节点，负责长距离导航。查询时从最高层入口点开始，逐层贪心靠近目标区域，到第 0 层后使用 ef_search 控制候选宽度进行更充分的搜索。构建时，每个新节点随机分配层数，并用 ef_construction 搜索候选邻居，再通过 heuristic 选择兼顾距离和多样性的连接边。核心参数中，M 控制图的稠密度和内存，ef_construction 控制建图质量，ef_search 控制查询召回和延迟。

1. 背景：为什么向量检索需要 ANN

一个不错的视频：「向量数据库技术」

在 RAG、语义搜索、推荐系统、图片检索、代码检索等场景中，数据通常会被 Embedding 模型编码成高维向量。例如：

文档 chunk -> 768 维 / 1024 维向量
图片 -> CLIP 向量
用户行为序列 -> 表征向量
商品、问题、代码片段 -> 语义向量

查询时，我们希望找到和 query vector 最接近的 Top-K 个向量。

最直接的方式是暴力搜索：

对库里每一个向量计算距离或相似度。
维护一个 Top-K 堆。
返回距离最近的 K 个结果。

如果有 N 个向量，每个向量维度是 dim，那么一次查询的复杂度大致是：

1	O(N * dim)

当 N 达到百万、千万甚至更高时，全量扫描会很贵。即使单次距离计算可以用 SIMD、GPU、批处理优化，本质上仍然需要扫大量向量。

于是引出 ANN：

1	ANN：Approximate Nearest Neighbor，近似最近邻搜索

ANN 不一定保证返回数学意义上完全精确的最近邻，而是在速度、内存、召回率之间做平衡。它追求的是：

召回足够高，比如 Recall@10 >= 0.95。
延迟足够低，比如毫秒级查询。
内存和构建成本可控。

HNSW 就是当前工程上非常常见的一类 ANN 图索引算法。

2. 最近邻搜索里的几个基础概念

2.1 向量距离与相似度

HNSW 本身是一个索引框架，它不绑定某一种距离函数。常见距离包括：

度量	含义	常见场景
`L2` / 欧氏距离	两个向量之间的直线距离	SIFT、图像特征、一般数值向量
Inner Product / 内积	向量点积，越大越相似	推荐、Embedding 检索
Cosine / 余弦相似度	向量夹角相似度	文本语义检索、RAG

余弦相似度定义为：

1	cos(a, b) = dot(a, b) / (\|\|a\|\| * \|\|b\|\|)

如果所有向量都提前归一化到单位长度，那么：

1	cos(a, b) = dot(a, b)

这也是很多向量数据库会建议对文本 Embedding 做归一化的原因：归一化后，内积、余弦、L2 之间可以相互转化，距离计算也更稳定。

2.2 Top-K、Recall@K 与 Ground Truth

向量检索的结果通常不是只看 Top-1，而是看 Top-K。

比如 k = 10 时，查询返回 10 个最相似结果。

为了衡量 ANN 的准确性，通常先用暴力搜索算出精确结果，也就是 ground truth，然后比较 ANN 结果覆盖了多少真实近邻。

1	Recall@K = ANN 返回的 Top-K 中命中真实 Top-K 的数量 / K

例如：

精确 Top-10：[1,2,3,4,5,6,7,8,9,10]
HNSW Top-10：[1,2,3,4,8,11,12,13,14,15]
命中：1,2,3,4,8，共 5 个
Recall@10 = 0.5

调参时，HNSW 主要是在召回率、查询延迟、内存、构建时间之间做 trade-off。

3. HNSW 是什么

HNSW 全称是：

1	Hierarchical Navigable Small World

可以拆成三个关键词：

Hierarchical：分层结构。
Navigable：图是可导航的，可以沿着边逐步走向目标。
Small World：小世界图，节点之间通常可以通过较短路径到达。

HNSW 的核心思想是：

用一个多层近邻图来组织向量。高层节点稀疏、边跨度大，负责快速导航；底层节点全、边更密，负责精细搜索。

可以把它类比成地图：

高层像高速公路，节点少，但可以快速靠近目标区域。
底层像城市街道，节点多，用于找具体门牌号。

也可以类比跳表：

跳表用多层链表加速有序数据查找。
HNSW 用多层图加速高维向量空间里的近邻查找。

4. HNSW 的整体结构

HNSW 由多层图组成：

Level 3:          o ------------- o

Level 2:     o ---- o -------- o ---- o

Level 1:  o -- o -- o ---- o -- o -- o

Level 0: o-o-o-o-o-o-o-o-o-o-o-o-o-o-o

其中：

第 0 层包含所有向量节点。
越高层，节点越少。
每个节点被随机分配一个最高层级。
一个节点如果出现在第 l 层，那么它也一定出现在所有更低层，也就是 0..l 层。
搜索从最高层的 entry_point 开始，逐层向下。

4.1 节点结构

在项目中可以把一个 HNSW 节点理解成：

struct HNSWNode {
    node_id_t id;
    doc_id_t doc_id;
    std::vector<float> vector;
    std::vector<std::vector<node_id_t>> neighbors; // neighbors[level]
};

其中：

id：向量节点 ID，用于图内部寻址。
doc_id：业务文档 ID，用于从检索结果映射回文档。
vector：原始向量数据。
neighbors[level]：该节点在某一层的邻居列表。

4.2 全局索引元信息

一个 HNSW 索引通常还需要保存：

struct HNSWIndexMeta {
    size_t dim;
    size_t node_count;
    node_id_t entry_point;
    int max_level;
    int M;
    int maxM;
    int maxM0;
    int ef_construction;
    int ef_search;
    DistanceType distance_type;
};

这些信息不仅用于查询和插入，也要在持久化时写入 header page 或元数据文件。

5. HNSW 的核心直觉

5.1 单层近邻图的问题

如果只维护一张近邻图，每个点都连向自己的若干近邻，那么可以在图上做贪心搜索：

从某个入口节点出发。
看当前节点的邻居。
如果某个邻居离 query 更近，就跳过去。
重复直到没有更近的邻居。

问题是：这种搜索容易陷入局部最优。

原因是近邻图的边多数是局部短边。如果入口点离目标区域很远，搜索可能需要很多小步才能靠近目标，或者走到某个局部区域后就出不来了。

5.2 小世界图的作用

小世界图希望同时拥有两类边：

短边：连接局部邻居，保证精细搜索。
长边：连接较远区域，保证快速导航。

NSW（Navigable Small World）就是利用这种思想，在单层图里通过增量构建自然形成一些长边。

HNSW 则进一步显式加入层次结构：

高层天然稀疏，因此边的跨度更大。
底层包含所有点，因此适合最终精细搜索。
搜索路径从粗到细，避免一开始就在底层图里盲目扩展。

5.3 为什么不是简单取最近的 M 个邻居

一个常见误区是：每个节点只要连接最近的 M 个点就够了。

实际并不一定。

如果最近的 M 个点都挤在同一个方向或同一个局部簇里，这些边会高度冗余。它们虽然距离近，但对图的可导航性帮助有限。

HNSW 的邻居选择 heuristic 会尽量保留：

距离当前点较近的边。
方向上更分散的边。
能把图连到不同区域的边。

因此 HNSW 追求的不只是“局部最近”，还追求“图整体容易导航”。(启发式)

6. HNSW 的查询算法

HNSW 查询分成两段：

高层贪心下降。
底层宽搜索。

6.1 高层贪心搜索

从最高层的 entry_point 开始，在每一层做贪心搜索：

current = entry_point

for level from max_level down to 1:
    while exists neighbor closer to query than current:
        current = closer_neighbor

高层搜索通常只保留一个当前最优点，所以速度很快。它的目标不是直接找最终答案，而是把入口点移动到更接近 query 的区域。

6.2 第 0 层 ef 搜索

到第 0 层后，HNSW 不再只做单点贪心，而是维护一个候选集合。

核心数据结构通常有两个：

candidate_set：待扩展候选，优先扩展离 query 最近的点。
top_candidates：当前找到的较好结果，最多保留 ef_search 个。

伪代码：

search_layer(query, entry_points, ef, level):
    visited = set()
    candidate_set = min-heap by distance
    top_candidates = max-heap by distance

    for ep in entry_points:
        dist = distance(query, ep)
        candidate_set.push(ep, dist)
        top_candidates.push(ep, dist)
        visited.add(ep)

    while candidate_set is not empty:
        candidate = candidate_set.pop_nearest()
        worst = top_candidates.peek_worst()

        if distance(query, candidate) > distance(query, worst):
            break

        for neighbor in candidate.neighbors[level]:
            if neighbor in visited:
                continue
            visited.add(neighbor)

            d = distance(query, neighbor)
            if top_candidates.size < ef or d < top_candidates.peek_worst_distance():
                candidate_set.push(neighbor, d)
                top_candidates.push(neighbor, d)

                if top_candidates.size > ef:
                    top_candidates.pop_worst()

    return top_candidates

最终从 top_candidates 里取距离最近的 k 个结果。

6.3 `ef_search` 和 `k` 的关系

k 是用户要几个结果，ef_search 是搜索时保留多少候选。

通常要求：

1	ef_search >= k

如果 ef_search = k，搜索很窄，速度快但容易漏。

如果 ef_search >> k，搜索更充分，召回更高，但延迟也更高。

例如：

k = 10
ef_search = 20   -> 快，但召回可能一般
ef_search = 50   -> 常见折中
ef_search = 100  -> 召回更高，延迟更大
ef_search = 200  -> 高召回场景，但成本明显增加

7. HNSW 的插入算法

HNSW 是增量构建的。每插入一个新向量，就把它连入多层图。

7.1 随机生成节点层数

每个节点会被随机分配一个最高层级。常见方式是指数衰减分布：

1 2	level = floor(-ln(uniform(0, 1)) * mL) mL = 1 / ln(M)

效果是：

大多数节点只在第 0 层。
少数节点进入第 1 层。
更少节点进入第 2 层。
极少数节点进入更高层。

这使得 HNSW 的层次结构像跳表一样自然形成。

7.2 插入流程

插入一个新节点 q 时：

如果图为空，把新节点设为 entry_point。
随机生成新节点最高层 level_q。
从当前 entry_point 和全局最高层开始，逐层贪心搜索，找到更接近新节点的位置。
对于 min(level_q, max_level) 到第 0 层：
- 使用 ef_construction 做 search_layer。
- 从候选中选出最多 M 个邻居。
- 建立双向连接。
- 如果旧节点邻居数超过上限，需要重新裁剪。
如果新节点层数高于当前全局最高层：
- 更新 entry_point = q。
- 更新 max_level = level_q。

伪代码：

insert(q):
    level_q = random_level()

    if graph is empty:
        entry_point = q
        max_level = level_q
        return

    ep = entry_point

    for level from max_level down to level_q + 1:
        ep = greedy_search(q, ep, level)

    for level from min(level_q, max_level) down to 0:
        candidates = search_layer(q, [ep], ef_construction, level)
        selected = select_neighbors_heuristic(q, candidates, M)

        connect q with selected at this level

        for each neighbor in selected:
            if neighbor.degree(level) > max_degree(level):
                neighbor.neighbors[level] =
                    select_neighbors_heuristic(neighbor, neighbor.neighbors[level], max_degree(level))

        ep = candidates

    if level_q > max_level:
        entry_point = q
        max_level = level_q

7.3 双向边与邻居裁剪

HNSW 图通常维护近似双向连接：

1 2	q -> neighbor neighbor -> q

但当 neighbor 的邻居数量超过上限时，需要裁剪。

这一步非常关键。只给新节点选好邻居还不够，还要保证被连接的旧节点不会因为边太多导致内存膨胀，同时又不能随便删掉有价值的导航边。

8. HNSW 的邻居选择 heuristic

邻居选择有两种思路：

8.1 简单策略：取最近的 M 个

最简单的方法是：

按距离排序候选点。
取最近的 M 个。

优点：

实现简单。
局部距离最优。

缺点：

容易选出集中在同一方向的冗余边。
图的连通性和可导航性可能变差。

8.2 启发式策略：保留分散邻居

HNSW 论文里的 heuristic 思想可以概括为：

候选点不仅要离当前点近，还不能被已经选中的邻居“遮挡”。

直观理解：

候选点 c 离当前点 q 很近。
但如果已经选中的某个邻居 s 比 q 更接近 c，那么从 q 直接连到 c 的价值可能不高。
因为搜索可以先到 s，再到 c。

简化伪代码：

select_neighbors_heuristic(q, candidates, M):
    sort candidates by distance(q, candidate)
    selected = []

    for c in candidates:
        good = true
        for s in selected:
            if distance(c, s) < distance(c, q):
                good = false
                break

        if good:
            selected.push(c)

        if selected.size == M:
            break

    return selected

这个策略会牺牲一点纯局部最近性，但能提升图的导航能力。

9. HNSW 核心参数详解

这一节是工程调参最重要的部分。

9.1 `M`

M 控制每个节点在每层最多保留多少个邻居。

它影响：

图的稠密度。
内存占用。
建图时间。
查询召回。
图的可导航性。

一般规律：

`M` 大小	效果
较小	内存低，构建快，但图更稀疏，召回可能下降
较大	图更密，召回更高，但内存和构建时间上升

常见经验值：

M = 8   -> 省内存，适合低维或召回要求不极端的场景
M = 16  -> 非常常见的默认折中
M = 32  -> 更高召回，更高内存
M = 48+ -> 高召回或复杂数据集，但成本明显增加

在很多实现中，第 0 层会允许更多邻居：

1 2	maxM = M maxM0 = 2 * M

因为第 0 层包含所有节点，承担最终精细搜索，适当提高底层连接数有利于召回。

9.2 `ef_construction`

ef_construction 是建图时的候选队列大小。

插入新节点时，HNSW 会先搜索一批候选邻居，然后再从中挑选最终连接边。ef_construction 越大，候选池越充分，建出来的图质量通常越好。

影响：

越大：召回上限更高，图质量更好，构建更慢。
越小：构建更快，但可能错过关键边，后续查询即使调大 ef_search 也救不回来。

经验规则：

1 2	ef_construction >= M ef_construction 通常远大于 M

常见取值：

1 2	M = 16, ef_construction = 100 ~ 200 M = 32, ef_construction = 200 ~ 400

在你的 RAG-DB 项目规划中，M = 16、ef_construction = 200 是一个合理的起点。

9.3 `ef_search`

ef_search 是查询时第 0 层搜索的候选队列大小。

它是线上最常调的参数之一，因为它不需要重建索引。

影响：

越大：搜索更充分，召回更高，延迟更高。
越小：查询更快，但更容易漏召回。

经验规则：

1	ef_search >= k

常见取值：

1 2	k = 10, ef_search = 32 / 50 / 100 k = 50, ef_search = 100 / 200

项目初始配置可以使用：

1
2
3

M = 16
ef_construction = 200
ef_search = 50

然后通过 benchmark 画出：

1	Recall@10 vs P50/P95/P99 latency

9.4 `k`

k 是业务查询需要返回的结果数。

注意：

1	k 不是 HNSW 索引结构参数，而是查询请求参数。

但它会影响 ef_search 的合理下限。

如果业务只需要 Top-5，ef_search = 50 可能已经足够。

如果业务要 Top-100，ef_search = 50 就不合理，因为候选数比返回数还少。

9.5 `max_level`

max_level 是当前图的最高层。

它不是手动固定的核心参数，通常由随机层数和数据规模共同决定。随着节点数量增加，最高层会逐渐升高。

常见直觉：

1 2	N 越大，需要的层数越多 M 越大，高层节点下降得越快

很多实现会用类似下面的层数生成方式：

1 2	mL = 1 / ln(M) level = floor(-ln(random()) * mL)

9.6 `entry_point`

entry_point 是搜索入口，通常是当前最高层的某个节点。

查询和插入都会从它开始。

如果插入的新节点层数超过当前最高层，那么新节点会成为新的 entry_point。

9.7 `distance_type`

距离类型会直接影响结果语义：

距离	结果排序方向	注意点
L2	越小越近	常用于传统特征
Inner Product	越大越相似	有的实现会转成负距离
Cosine	越大越相似	通常需要向量归一化

工程中要特别注意：

建索引和查询必须使用同一种距离定义。
如果使用 cosine，最好统一在写入前归一化。
如果使用内积，确认库内部是最大化相似度还是最小化距离。

9.8 `dim`

dim 是向量维度。

它不改变 HNSW 的图算法，但会影响：

每次距离计算成本。
向量存储空间。
CPU cache 命中率。
SIMD 优化方式。

高维向量下，瓶颈往往不是图遍历本身，而是大量距离计算。

9.9 `random_seed`

HNSW 的层数分配是随机的。random_seed 会影响：

每个点进入哪些层。
图结构细节。
benchmark 的可复现性。

做实验时建议固定 seed，避免调参结果因为随机性抖动。

9.10 `num_threads`

部分实现支持多线程构建或查询。

注意：

并发查询相对容易，因为大多是只读。
并发插入更复杂，需要保护图结构、邻居列表、entry point、visited pool 等共享状态。
插入和查询并发时要考虑读写锁、版本可见性和持久化一致性。

9.11 `allow_replace_deleted`

一些 HNSW 实现支持逻辑删除和复用已删除位置。

删除在 HNSW 中比插入困难，因为：

被删除节点可能是图上的关键导航节点。
直接物理删除会破坏邻居连接。
逻辑删除会让图里保留无效点，影响搜索效率。

如果删除频繁，常见策略是：

逻辑删除 + 后台重建。
分段索引，定期 compaction。
对高删除率业务考虑其他索引方案。

9.12 参数总览表

参数	控制什么	增大后的收益	增大后的代价	是否需要重建
`M`	图的最大邻居数	召回更高，图更容易导航	内存更大，构建更慢	通常需要
`maxM0`	第 0 层最大邻居数	底层搜索更充分	底层内存增加	通常需要
`ef_construction`	建图候选宽度	图质量更高	构建更慢	需要重新构建才影响旧图
`ef_search`	查询候选宽度	召回更高	查询更慢	不需要
`k`	返回结果数	返回更多候选给业务	需要更大搜索宽度	不需要
`max_level`	图最高层	导航层次更多	元数据和少量边增加	自动生成
`distance_type`	相似度语义	匹配业务目标	选错会导致结果错误	通常需要
`dim`	向量维度	表达能力可能更强	距离计算和存储更贵	由模型决定

10. HNSW 的复杂度与成本

严格复杂度不是 HNSW 最大的卖点，工程平均表现更重要。

可以这样理解：

10.1 查询复杂度

查询分成：

高层导航。
底层 ef_search 宽搜索。

高层节点少，通常很快。

底层成本主要与下面因素相关：

1	ef_search * 每个候选的邻居数 * 距离计算成本

近似理解：

1	查询成本 ≈ O(ef_search * M * dim)

10.2 构建复杂度

构建时每插入一个点都要搜索候选并连边，因此比查询更贵。

近似理解：

1	构建成本 ≈ O(N * ef_construction * M * dim)

其中还包括邻居裁剪和堆操作。

10.3 空间复杂度

HNSW 的空间主要由两部分组成：

向量本身。
图边。

向量空间：

1	N * dim * sizeof(float)

如果 N = 1,000,000，dim = 768，float32 = 4 bytes：

1	1,000,000 * 768 * 4 ≈ 3 GB

图边空间近似：

O(N * M)

如果每条边存 uint32 node_id，M = 16，底层约 2M，再加上高层边和 vector/list 开销，图结构可能占用数百 MB 到数 GB。

所以 HNSW 常见瓶颈之一就是内存。

11. 参数调优实践

11.1 推荐调参顺序

不要一开始就同时调所有参数。推荐顺序：

固定数据集、距离函数、评估方式。
先选一个常见 M，比如 16。
选择足够大的 ef_construction，比如 200。
通过调整 ef_search 得到召回-延迟曲线。
如果 ef_search 很大仍然召回不够，再提高 M 或 ef_construction 重建索引。
如果内存压力过大，再降低 M 或引入压缩、分片、磁盘索引。

11.2 什么时候调 `ef_search`

优先调 ef_search 的场景：

查询召回略低。
构建图质量基本可信。
不想重建索引。
线上希望按 SLA 动态调节速度和准确率。

现象：

1
2
3

ef_search 从 20 -> 50，Recall 明显提升
ef_search 从 50 -> 100，Recall 继续提升但变慢
ef_search 从 100 -> 200，Recall 提升变小，延迟明显增加

这说明 ef_search 存在边际收益递减。

11.3 什么时候调 `M`

需要调大 M 的场景：

图太稀疏。
高 ef_search 下召回仍然上不去。
数据分布复杂，局部簇很多。
需要更高 Recall@K。

代价：

内存明显增加。
构建时间增加。
插入时邻居裁剪更贵。

11.4 什么时候调 `ef_construction`

需要调大 ef_construction 的场景：

构建阶段太草率，导致图质量差。
查询时开很大的 ef_search 仍然找不到正确近邻。
benchmark 显示召回上限明显不足。

注意：

1 2	ef_construction 只影响建图过程。对已经建好的旧图，运行时调大 ef_construction 不会直接改善查询结果。

11.5 一组项目起步配置

对于百万级文本 Embedding 检索，可以从下面配置开始：

dim = 768 或 1024
distance_type = cosine 或 inner_product
M = 16
maxM0 = 32
ef_construction = 200
ef_search = 50
k = 10

然后做 benchmark：

实验组	`M`	`ef_construction`	`ef_search`	观察指标
A	16	100	20	低延迟基线
B	16	200	50	平衡配置
C	16	200	100	高召回查询
D	32	200	50	更密图
E	32	400	100	高召回高成本

重点观察：

Recall@10
P50 / P95 / P99 延迟
QPS
构建耗时
索引大小
内存峰值

12. HNSW 在项目中的工程落地

用户查询
   |
   v
Embedding 模型
   |
   v
Query Vector
   |
   v
HNSW Vector Index
   |
   v
Top-K doc_id
   |
   v
文档存储 / Chunk 表
   |
   v
返回候选文本

12.1 数据写入流程

1	Document -> Chunk -> Embedding -> Insert into HNSW -> Store doc_id mapping

需要注意：

向量和 doc_id 映射要一致。
插入失败时不能只写了一半。
如果文档更新，需要处理旧向量删除或失效。
如果支持事务，要考虑索引更新和文档存储的一致性。

12.2 查询流程

1	Query Text -> Query Embedding -> HNSW Top-K -> Fetch Chunks -> Optional Rerank

在 RAG 场景中，HNSW 通常不是最后一步。实际系统可能会：

HNSW 召回 Top-50。
BM25 召回 Top-50。
用 RRF 融合。
用 Cross-Encoder / Reranker 重排 Top-20。
取 Top-5 放入 prompt。

12.3 持久化设计

HNSW 持久化通常需要保存：

Header：dim、M、ef_construction、distance_type、entry_point、max_level、节点数。
Vector data：每个节点的向量。
Neighbor lists：每个节点每层邻居。
Doc mapping：node_id -> doc_id。
Deleted bitmap：逻辑删除标记。

可以设计成：

hnsw.index
  Header Page
  Node Pages
  Neighbor Pages
  Vector Pages
  Mapping Pages

如果项目里已有 Buffer Pool，可以将节点和邻居列表序列化到 Page 中，并通过 dirty page 控制增量刷盘。

12.4 并发控制

并发查询：

多数情况下是只读，可以用 shared lock。
visited set 应该是线程本地的，不能全局共享。
候选堆也是线程本地的。

并发插入：

会修改邻居列表。
可能修改 entry point。
可能触发旧节点邻居裁剪。
需要 exclusive lock 或更细粒度锁。

简单实现可以先用：

std::shared_mutex mutex_;

// search
std::shared_lock lock(mutex_);

// insert
std::unique_lock lock(mutex_);

后续再优化为分层锁、节点锁或批量构建。

12.5 删除与更新

HNSW 不擅长高频物理删除。

常见做法：

删除时只打 tombstone。
查询结果过滤掉 deleted 节点。
后台定期重建索引。
更新文档时插入新向量，旧向量标记删除。

如果删除率很高，索引会逐渐膨胀，查询也会浪费时间访问无效节点。

12.6 过滤条件的问题

很多业务查询不是单纯向量检索，还会带过滤条件：

1
2
3

WHERE tenant_id = 123
AND created_at >= '2026-01-01'
AND category = 'database'

过滤会影响 HNSW：

如果先 HNSW 后过滤，可能 Top-K 里大量结果被过滤掉，导致召回不足。
如果先过滤再 HNSW，需要为过滤后的子集建立索引或动态搜索，成本高。

常见方案：

多租户分别建索引。
常用 category 分片建索引。
HNSW 返回更大的 Top-N，再过滤。
在搜索过程中判断 filter，并适当增大 ef_search。
对强过滤场景考虑 IVF、倒排、bitmap 与向量索引结合。

13. 与 HNSW 相关的算法

13.1 Flat / Brute Force

暴力搜索是最简单、最准确的方法。

特点：

召回 100%。
实现简单。
适合小数据量或 GPU 批量计算。
数据量大时延迟高。

它通常作为 ANN 的 ground truth 生成方式。

13.2 KD-Tree / Ball Tree

KD-Tree 和 Ball Tree 是传统空间索引。

特点：

对低维数据有效。
维度升高后容易退化。
不适合几百维、上千维的文本 Embedding 主场景。

结论：

1 2	低维几何数据可以考虑 KD-Tree；高维语义向量通常优先考虑 HNSW、IVF、PQ 等 ANN。

13.3 LSH

LSH 全称 Locality Sensitive Hashing，局部敏感哈希。

核心思想：

相似向量以更高概率被 hash 到同一个桶。

查询时只查同桶或相邻桶，减少比较数量。

优点：

理论清晰。
支持一些特定距离度量。
插入相对直接。

缺点：

参数调起来不直观。
为了高召回可能需要很多 hash table。
工程效果很多时候不如 HNSW。

13.4 Annoy

Annoy 是 Spotify 开源的 ANN 库，核心思想是多棵随机投影树。

特点：

索引可以 mmap，加载快。
适合读多写少。
构建后通常不支持高效动态插入。
综合召回和速度在很多场景不如 HNSW，但工程简单。

适合：

静态索引。
内存映射。
推荐系统候选召回。

13.5 IVF

IVF 全称 Inverted File Index，倒排文件索引。

核心思想：

先用聚类把向量空间分成 nlist 个簇。
每个簇维护一个倒排列表。
查询时只搜索离 query 最近的 nprobe 个簇。

参数：

参数	含义
`nlist`	聚类中心数量
`nprobe`	查询时探测多少个簇

特点：

适合大规模数据。
可与 PQ 结合节省内存。
查询速度和召回由 nprobe 控制。
聚类质量会影响召回。

HNSW vs IVF：

对比项	HNSW	IVF
核心结构	多层近邻图	聚类 + 倒排列表
查询方式	图上导航	先找簇，再扫列表
动态插入	相对友好	可以插入，但聚类中心固定
高召回表现	通常很好	依赖 `nprobe` 和聚类质量
内存	图边较重	可结合压缩降低

13.6 PQ / OPQ

PQ 全称 Product Quantization，乘积量化。

它不是单独的导航索引，而是一种向量压缩和近似距离计算方法。

核心思想：

把高维向量切成多个子空间。
每个子空间分别做聚类。
用每个子空间的 codebook id 表示原向量。

优点：

大幅降低向量存储。
可以加速距离计算。
适合超大规模向量库。

缺点：

距离是近似的，会损失召回。
实现和调参复杂。

OPQ 是 Optimized Product Quantization，会先做一个旋转变换，让向量更适合 PQ 分块。

常见组合：

1
2
3

IVF + PQ
HNSW + PQ
HNSW 召回候选 + 原始向量精排

13.7 ScaNN

ScaNN 是 Google 提出的向量检索方案，核心包含：

分区。
向量量化。
重排序。

它在一些内积检索任务上表现很好。

特点：

工程优化强。
适合大规模向量检索。
原理和实现都比简单 HNSW 更复杂。

13.8 DiskANN

DiskANN 面向超大规模、磁盘友好的 ANN。

核心目标：

1	在数据无法全部放入内存时，仍然保持较高召回和较低延迟。

特点：

图索引思想。
重点优化 SSD 访问模式。
适合十亿级向量或内存受限场景。
工程复杂度高于内存 HNSW。

如果 HNSW 的内存成本无法接受，可以研究 DiskANN 或基于 mmap / SSD 的图索引。

13.9 NSG

NSG 全称 Navigating Spreading-out Graph。

它也是图 ANN 算法，强调构建一个稀疏但导航性好的图。

特点：

图更稀疏。
搜索性能强。
构建过程相对复杂。

HNSW 的优势是实现和工程生态更成熟。

13.10 BM25

BM25 不是向量 ANN 算法，而是传统关键词检索算法。

它基于词频、逆文档频率和文档长度归一化，适合精确关键词匹配。

在 RAG 中，HNSW 和 BM25 往往互补：

检索方式	优势	劣势
HNSW 向量检索	语义匹配，能找近义表达	对精确词、编号、专有名词可能不稳定
BM25 关键词检索	精确词匹配强，可解释	不理解语义相似

因此常见混合检索：

1	HNSW Top-N + BM25 Top-N -> 融合排序 -> Rerank

13.11 RRF

RRF 全称 Reciprocal Rank Fusion，用于融合多个排序列表。

公式：

1	score(d) = sum(1 / (k + rank_i(d)))

其中：

rank_i(d) 是文档 d 在第 i 个检索器里的排名。
k 是平滑常数，常见取值如 60。

RRF 不需要不同检索器的分数可比，只需要排名，因此很适合融合 BM25 和向量检索。

13.12 Reranker

Reranker 通常是 Cross-Encoder 或更强的排序模型。

流程：

1 2	召回阶段：HNSW / BM25 快速拿 Top-50 或 Top-100 重排阶段：Reranker 精排 Top-10

HNSW 负责快，Reranker 负责准。

14. HNSW 的优缺点

14.1 优点

查询速度快。
高召回表现好。
支持增量插入。
参数相对直观。
工程生态成熟。
适合中高维向量检索。

14.2 缺点

内存占用高。
构建时间不低。
删除和高频更新复杂。
强过滤条件会影响召回。
分布式分片后需要全局 Top-K 合并。
对距离函数、归一化、参数设置比较敏感。

15. 常见误区

15.1 HNSW 不是精确搜索

HNSW 是 ANN，返回的是近似最近邻。

如果业务需要绝对精确结果，应使用暴力搜索、精确索引，或者在 HNSW 召回后用原始向量进行更大范围精排。

15.2 `ef_search` 不是越大越好

ef_search 越大，召回通常越高，但延迟也越高。

当召回曲线进入平台期后，继续增大 ef_search 的收益很小。

15.3 只调 `ef_search` 不能解决所有问题

如果建图质量差，例如 M 太小或 ef_construction 太小，图里缺少关键连接，那么查询时再怎么扩大搜索，也可能找不到正确路径。

15.4 最近的 M 个邻居不一定是最好的 M 条边

HNSW 需要的是可导航图，不只是局部 KNN 图。

边的多样性和连通性非常重要。

15.5 向量归一化不能忽略

如果使用 cosine，但写入和查询时没有统一归一化，结果可能偏差很大。

归一化策略必须在建索引前确定，并在查询时保持一致。

16. 一个可落地的 C++ 实现骨架

下面是一个简化版接口设计，用于帮助整理项目代码结构。

class HNSWIndex {
public:
    HNSWIndex(size_t dim,
              int M,
              int ef_construction,
              DistanceType distance_type);

    void Insert(std::vector<float> vector, doc_id_t doc_id);

    std::vector<SearchResult> Search(const std::vector<float>& query,
                                     size_t k,
                                     int ef_search) const;

    void SaveIndex(const std::string& path) const;

    void LoadIndex(const std::string& path);

private:
    int RandomLevel();

    node_id_t GreedySearch(const std::vector<float>& query,
                           node_id_t entry,
                           int level) const;

    std::vector<Candidate> SearchLayer(const std::vector<float>& query,
                                       const std::vector<node_id_t>& entry_points,
                                       int ef,
                                       int level) const;

    std::vector<node_id_t> SelectNeighborsHeuristic(
        const std::vector<float>& query,
        std::vector<Candidate>& candidates,
        int max_neighbors) const;

    float Distance(const std::vector<float>& a,
                   const std::vector<float>& b) const;

private:
    size_t dim_;
    int M_;
    int maxM_;
    int maxM0_;
    int ef_construction_;
    DistanceType distance_type_;

    node_id_t entry_point_;
    int max_level_;

    std::vector<HNSWNode> nodes_;
    mutable std::shared_mutex mutex_;
};

实现优先级建议：

先实现 L2 或 cosine 距离。
实现单线程插入和查询。
用小数据集和暴力搜索对拍。
加入 select_neighbors_heuristic。
加入持久化。
加入并发查询。
做 SIMD 和内存布局优化。

17. 测试与 Benchmark 设计

17.1 正确性测试

测试	方法	期望
单点查询	插入一个向量，查询自身	距离为 0 或相似度最高
小规模对拍	100 个随机向量与暴力搜索比较	Top-1 基本一致
Recall@K	1000 / 10000 向量，暴力搜索生成 ground truth	达到预期召回
持久化一致性	Save 后 Load 再查	结果一致
删除过滤	删除后查询	不返回 deleted 节点

17.2 性能测试

指标	含义
Build Time	构建索引总耗时
QPS	每秒查询数
P50	中位延迟
P95	95 分位延迟
P99	99 分位延迟
Recall@K	召回率
Memory Usage	内存占用
Index Size	持久化索引大小

18. HNSW 在 RAG 系统中的位置

一个完整 RAG 检索链路通常不是只有 HNSW：

flowchart LR
    A[User Query] --> B[Query Embedding]
    B --> C[HNSW Vector Search]
    A --> D[BM25 Keyword Search]
    C --> E[Candidate Fusion]
    D --> E
    E --> F[Reranker]
    F --> G[Top Contexts]
    G --> H[LLM Answer]

HNSW 的职责是语义召回：

找表达不同但语义相近的内容。
快速从大规模 chunk 中缩小候选范围。

BM25 的职责是关键词召回：

找专有名词。
找编号、函数名、错误码、配置项。
找用户 query 中明确出现的词。

Reranker 的职责是精排：

更细粒度判断 query 和 chunk 是否真正相关。
降低单纯向量距离带来的误召回。

本作品由 lorixyu 于 2026-05-17 16:01:30 发布

作品地址：HNSW 算法学习与项目实践：从近似最近邻到向量检索工程

除特别声明外，本站作品均采用 CC BY-NC-SA 4.0 许可协议，转载请注明来自 lorixyu

HNSW 算法学习与项目实践：从近似最近邻到向量检索工程

1. 背景：为什么向量检索需要 ANN

2. 最近邻搜索里的几个基础概念

2.1 向量距离与相似度

2.2 Top-K、Recall@K 与 Ground Truth

3. HNSW 是什么

4. HNSW 的整体结构

4.1 节点结构

4.2 全局索引元信息

5. HNSW 的核心直觉

5.1 单层近邻图的问题

5.2 小世界图的作用

5.3 为什么不是简单取最近的 M 个邻居

6. HNSW 的查询算法

6.1 高层贪心搜索

6.2 第 0 层 ef 搜索

6.3 ef_search 和 k 的关系

7. HNSW 的插入算法

7.1 随机生成节点层数

7.2 插入流程

7.3 双向边与邻居裁剪

8. HNSW 的邻居选择 heuristic

8.1 简单策略：取最近的 M 个

8.2 启发式策略：保留分散邻居

9. HNSW 核心参数详解

9.1 M

9.2 ef_construction

9.3 ef_search

9.4 k

9.5 max_level

9.6 entry_point

9.7 distance_type

9.8 dim

9.9 random_seed

9.10 num_threads

9.11 allow_replace_deleted

9.12 参数总览表

10. HNSW 的复杂度与成本

10.1 查询复杂度

10.2 构建复杂度

10.3 空间复杂度

11. 参数调优实践

11.1 推荐调参顺序

11.2 什么时候调 ef_search

11.3 什么时候调 M

11.4 什么时候调 ef_construction

11.5 一组项目起步配置

12. HNSW 在项目中的工程落地

12.1 数据写入流程

12.2 查询流程

12.3 持久化设计

12.4 并发控制

12.5 删除与更新

12.6 过滤条件的问题

13. 与 HNSW 相关的算法

13.1 Flat / Brute Force

13.2 KD-Tree / Ball Tree

13.3 LSH

13.4 Annoy

13.5 IVF

13.6 PQ / OPQ

13.7 ScaNN

13.8 DiskANN

13.9 NSG

13.10 BM25

13.11 RRF

13.12 Reranker

14. HNSW 的优缺点

14.1 优点

14.2 缺点

15. 常见误区

15.1 HNSW 不是精确搜索

15.2 ef_search 不是越大越好

15.3 只调 ef_search 不能解决所有问题

15.4 最近的 M 个邻居不一定是最好的 M 条边

15.5 向量归一化不能忽略

16. 一个可落地的 C++ 实现骨架

17. 测试与 Benchmark 设计

17.1 正确性测试

17.2 性能测试

6.3 `ef_search` 和 `k` 的关系

9.1 `M`

9.2 `ef_construction`

9.3 `ef_search`

9.4 `k`

9.5 `max_level`

9.6 `entry_point`

9.7 `distance_type`

9.8 `dim`

9.9 `random_seed`

9.10 `num_threads`

9.11 `allow_replace_deleted`

11.2 什么时候调 `ef_search`

11.3 什么时候调 `M`

11.4 什么时候调 `ef_construction`

15.2 `ef_search` 不是越大越好

15.3 只调 `ef_search` 不能解决所有问题