HNSW 向量检索算法
1. 一句话总结
HNSW 是目前向量数据库中最主流、性能最强的 ANN（近似最近邻） 搜索算法。它巧妙地结合了“小世界网络（六度分隔理论）”和“跳表（Skip List）”的思想，通过在内存中构建多层图结构，实现了海量高维向量的极速检索。
2. 核心思想拆解
要理解 HNSW，可以把它拆成两个关键部分：NSW（可导航小世界） + H（分层）。
2.1 什么是 NSW（可导航小世界）？
-
直觉类比：你在社交网络中找一个完全不认识的人（比如某个遥远国家的程序员）。你先找你认识的朋友中“最可能认识外国人”的那个，你朋友再找他认识的人里最接近目标的……这就是“小世界网络”的导航特性。
-
在向量里的体现：将向量看作图中的“节点”，相似的向量互相连接形成“边”。图中既有密集的短连接（连接相近的邻居），也有稀疏的长连接（跨越较远距离）。这保证了搜索时不会陷入死胡同，总能快速逼近目标。
2.2 为什么需要 H（Hierarchical 分层）？
单纯的 NSW 在数据量极大时，搜索效率依然会下降。HNSW 引入了分层结构来解决这个问题，它的思路和 Redis 中的 跳表（Skip List） 如出一辙。
-
第 0 层（底层）：包含所有的向量节点，连接最密集，用于最后的精准定位。
-
较高层：节点数量呈指数级递减。只有少数被随机抽中的节点才能进入上层，节点间的连接跨度极大，相当于“高速公路”。
-
最高层：通常只有一个或极少数几个入口节点。
3. 检索过程（自顶向下）
当我们需要查找与查询向量 $Q$ 最相似的向量时，HNSW 会执行以下步骤：
-
从顶层开始：在最顶层极少数的节点中，计算距离，找到离 $Q$ 最近的节点。
-
逐层下沉：以上一层找到的最近节点作为当前层的入口点，在当前层的图关系中继续寻找更近的邻居。
-
底层精确搜索：一直下沉到第 0 层（包含所有数据的层），进行最后的局部探索，找到全局最优的近似结果（Top-K）。
💡 核心优势： 顶层的快速跳转极大排除了大量无关区域，底层的小范围搜索保证了高召回率。
4. 关键参数与工程调优
在实际使用（如 Milvus, Qdrant 等数据库）中，HNSW 离不开以下三个核心参数：
|
参数名称 |
作用时机 |
含义 |
调大（增大）的影响 |
调小（减小）的影响 |
|
|
建索引时 |
每个节点在图中允许的最大连接边数。 |
召回率上升，内存占用变大，建图变慢。 |
节省内存，但图的连通性变差，可能找不到最优解。 |
|
|
建索引时 |
构建索引时，动态列表（候选池）的大小。 |
索引质量更高（连线更合理），但构建速度明显变慢。 |
建树极快，但召回率（精度）下降。 |
|
|
查询检索时 |
搜索时，探索候选集的大小（搜索宽度）。 |
搜索精度（召回率）提升，但单次查询耗时增加。 |
查询速度极快，但容易漏掉最相似的向量。 |
(注：通常设置 ef 是你想要获取的 Top-K 数量的 4~16 倍)
5. 优缺点总结
🌟 优点
-
极速的查询性能：即使在亿级规模数据下，延迟通常也在毫秒级。
-
极高的召回率：在牺牲极少精度的前提下（通常 95%+），换取巨大的性能飞跃。
-
支持增量更新：可以随时向图中插入新的向量节点，而不需要全量重建索引。
⚠️ 缺点（代价）
-
极其吃内存：因为需要在内存中存储所有的图关系（大量的边和指针）。例如 100 万个 4096 维的向量，光索引可能就需要占据十几个 GB 的内存空间。
