HNSW 算法：可导航小世界图的最邻近搜索

FreeGuideOnline 4阅读 2026-06-14

HNSW 算法：可导航小世界图的最邻近搜索

HNSW (Hierarchical Navigable Small World) 是当前向量近似最近邻搜索领域性能最出色的算法之一。它在海量高维数据中，能够以亚线性时间复杂度快速找到与查询向量最相似的邻居。本教程从零开始，帮助你理解 HNSW 的核心思想与工作流程。

1. 解决什么问题：向量近似最近邻搜索

在推荐系统、图像检索、语义搜索等场景中，我们常需要将图片、文本等转化为向量嵌入，然后快速寻找与目标向量最相似的 Top-K 个向量。

精确搜索在面对百万级或更高维数据时，线性扫描无法满足实时要求。HNSW 是一种图索引方法，它将所有向量构造成一个多层次的“小世界图”，牺牲微小的精度换取数百倍的速度提升。

2. 核心概念：可导航小世界图与分层结构

2.1 小世界图 (Small World Graph)

想象一个社交网络：任意两个人之间的平均路径长度很短，并且朋友的朋友大概率也是朋友（高聚类系数）。在向量空间中，我们为每个点建立连接到其附近的邻居，形成一个“纳维恩-小世界”网络。

长距离边：连接跨越较大距离的点，负责快速跨越整个空间（像社交网络中的“弱连接”）。
短距离边：连接紧密的近邻，保证局部搜索的精准性。

搜索时，从任意一个入口点开始，贪心地沿着图的边向查询向量更近的邻居移动，直至无法进一步靠近为止。

2.2 为何需要分层：HNSW 的“高速公路”系统

单纯的小世界图构建时间随数据量增长而恶化，且需要仔细调节参数。HNSW 的创新在于引入分层结构，灵感来自跳表 (Skip List) ：

底层 (Layer 0)：包含所有数据点，边密集，覆盖整个数据集，用于精细搜索。
上层 (Layer > 0)：包含的点逐层指数级减少（通过概率选择点进入上层）。这些层上的图边长、稀疏，起到“高速公路”的作用，能够快速跳过大量无关点，将搜索引导至目标附近区域。

每一层本身都是一个可导航小世界图。搜索从最顶层的入口点开始，贪心寻路，每下降一层，都在该层找到距离查询最近的局部最优解，然后以该点为入口进入下一层继续搜索，最终在 Layer 0 得到结果。

3. HNSW 索引构建过程

构建过程是增量式的，逐个将向量插入图中。对于每一个新插入的向量 q：

确定最高层级 L 使用一个指数衰减的概率分布随机生成 L（L = floor(-ln(uniform(0,1)) * m_L)）。m_L 是层生成乘数，控制层级衰减速度。L 越大，该点在越高层存在。
寻找每层的入口点 从顶层向下，找到每一层中距离 q 最近的点作为下一层搜索的入口（上层入口通常缓存为全局入口点）。
在所属层级插入并连接边 对于点 q 所属的每一层 lc（从 L 下至 0）：
- 使用该层的贪心搜索，从入口点出发，找到距离 q 最近的 efConstruction 个候选邻居（efConstruction 为构建时控制搜索宽度的参数）。
- 从候选邻居中选择 M 个距离最近的点（第 0 层通常使用 M 的 2 倍，记为 M_max0）建立双向连接。连接时还会进行剪枝：如果一个新连接会使某个邻居的度超出上限，则仅保留距离该邻居最近的边，删除较远的边，以保持图稀疏。

通过这种分层构建，HNSW 不需要全局重新平衡，天然支持在线增量插入新向量。

4. HNSW 搜索过程详解

给定查询向量 q，寻找 k 个最近邻：

初始化
- 从顶层 topLayer 开始，将全局入口点设为当前最近点。
- 使用一个动态候选集 W（大小限制为 efSearch，搜索时控制宽度的参数）保存已访问节点，并维护一个大小为 efSearch 的最邻近结果集。
从上至下逐层贪心搜索

对于每一层 lc 从 topLayer 降至 1：
- 以当前入口点为基础，执行贪心搜索：不断从 W 中取出未扩展的点，探索其邻居，将更近的点加入结果集，直到所有候选点的邻居都不比当前第 efSearch 个结果更近。
- 完成后，选择该层找到的最远那个最近邻作为进入下一层的入口点。
在底层 (Layer 0) 完成精细搜索

以同样的 efSearch 参数彻底搜索，直到候选集完全耗尽或无法找到更近的点。最后从结果集中返回最接近的 k 个邻居。

参数 efSearch 越大，搜索范围越广，召回率越高，但速度越慢。通常 efSearch 在运行时动态调整，efSearch 必须 ≥ k。

5. 关键参数及其影响

参数	含义	经验设置	影响
`M`	构建时每个点在第 0 层以上的最大连接数	通常 12 ~ 48，高维数据可稍大（如 64）	越大，索引占据内存越多，构建越慢，但更高召回率
`M_max0`	第 0 层的最大连接数	常用 `2 * M`	控制底层图精度和内存
`efConstruction`	构建时搜索候选集大小	常用 200 ~ 800	越大，构建图质量越高，但构建时间延长显著
`efSearch`	搜索时动态候选集大小	通常是 `k` 的倍数，如 `k` 的 10 倍，可动态调大	影响搜索速度与召回率的基本杠杆
`mL`	层级生成乘数（1/ln(2)≈1.44 是常用值）	默认 1 / ln(2)	控制点进入更高层的概率，影响层级高度和内存开销

6. HNSW 的优缺点

优点

超高的查询性能：在众多基准测试中，HNSW 的 QPS（每秒查询数）和召回率表现处于最前沿。
天然支持增量插入和删除（惰性删除或标记）。
无需训练阶段，直接构建索引，对数据分布无假设。
可通过调节 efSearch 在速度和精度之间灵活权衡。

局限性

内存占用较高，因为需要存储所有图连接信息（每个向量需要约 M * dim * sizeof(coord) 元的额外内存）。
如果数据插入顺序不佳或分布极度偏移，早期图质量可能不够理想，但影响通常较小。
不适合频繁更新和数据流巨大且需要极低延迟写入的场景（每次插入都要执行多重搜索）。

7. 何时选用 HNSW

当你的场景满足以下条件时，HNSW 是最佳选择之一：

向量维度在几十到几千维之间。
数据集规模从万级到亿级，查询延迟要求毫秒级。
对内存有一定容忍度，追求高吞吐和高召回率。
需要在线插入新向量而无需完全重建索引。

常见替代方案：IVF-PQ 类（内存更优，但需训练），Annoy（内存低，精度略低），局部敏感哈希（高维数据极快但召回波动大）。

8. 动手实践：使用主流库

Python 中常用 hnswlib 快速上手：

import hnswlib
import numpy as np

dim = 128
num_elements = 100000

# 初始化索引
p = hnswlib.Index(space='l2', dim=dim)
p.init_index(max_elements=num_elements, ef_construction=200, M=16)
p.set_ef(50)   # 设置搜索时的 efSearch

# 插入数据
data = np.random.randn(num_elements, dim).astype('float32')
p.add_items(data)

# 搜索 10 个最近邻
query = np.random.randn(1, dim).astype('float32')
labels, distances = p.knn_query(query, k=10)

其他语言也有高效的实现（如 C++ 的 hnswlib 原版，Rust 的 hora，Java 的 java-hnsw），接口理念一致。

9. 总结

HNSW 通过分层可导航小世界图，巧妙地将跳表思想与向量近邻搜索结合，实现了极致的查询效率和优秀的可扩展性。理解其分层构建与贪心搜索机制，能够让你在工程实践中精准调节参数，在召回率、内存和速度之间找到最优平衡点。