本文目录导读：
HNSW（Hierarchical Navigable Small World） 是一种目前最流行、性能最顶尖的近似最近邻搜索（ANNS）算法之一，它被广泛应用于需要快速向量检索的场景，向量数据库（Milvus、Qdrant、Weaviate）、RAG（检索增强生成）、图像搜索、推荐系统等。
HNSW 的核心思想是：用多层图结构，模拟类似“跳表（Skip List）”的快速查找过程。
下面我来详细解释其原理、优缺点以及关键参数。
核心原理：从“小世界”到“分层”
HNSW 由两个核心概念组合而成：
-
可导航小世界图：在普通近邻图的基础上，通过引入“长程链接”，使得任意两个节点之间的平均路径长度很短（即“六度分隔”理论），这样，从任意点出发，通过跳跃长链接，能很快到达目标区域。
-
层次化结构：虽然NSW图很快，但在数据量极大时，搜索链路依然很长，HNSW 借鉴跳表的思想，将图分层：
- 底层（Layer 0）：包含数据集中的所有向量，这一层负责最精确的搜索。
- 高层（Layer 1， 2， ...）：每往上一层，只包含部分“幸运”的点（通常是随机选出来的），层数越高，节点越稀疏，且节点之间拥有更长的“跳跃链接”。
为什么要分层？ 想象一下：你要在一本有10万页的旧书里找一页内容。
- 无分层：你需要一页一页地翻，或者从一个目录索引开始找，在NSW图里，可以从一个点开始，沿着链接一步步走。
- 有分层：HNSW 相当于让你先飞到书的目录层（高层），目录里标题跨度很大，你很快能定位到大概的章节，然后你再跳回正文层（底层），在每个小段落里精确查找，这大大减少了搜索步数。
HNSW 的工作流程（简要）
建图（插入节点）
当要插入一个新向量 q 时，算法会：
- 确定层数：用一个指数衰减的随机函数，给
q分配一个最高层数L，层数越高，节点越少。 - 自上而下插入：
- 从顶层（
L层）开始，贪婪地寻找到q最近的邻居节点ep。 - 然后进入下一层（
L-1层），继续从ep出发搜索，找到该层的新近邻，同时将q与其中efConstruction个最近邻的节点建立双向连接（并会进行剪枝以控制度数）。 - 重复这个过程,直到最底层（Layer 0）完成插入。
- 从顶层（
搜索（查询过程）
当要查询一个向量 q 的最近邻时：
- 从顶层开始：从预设的最高层入口点
enter_point开始。 - 贪婪下降：在当前层，执行贪婪搜索（每次都找离
q最近的邻居移动），不断接近目标区域。 - 跳到下一层：当在当前层找不到更近的点时，将当前找到的最近点作为下一层的起点，继续搜索。
- 底层精细搜索：到达最底层（Layer 0）后，执行广度优先/优先级队列搜索（如
efSearch控制），收集k个最精确的最近邻。
关键参数
在实际使用中（如 faiss、milvus、qdrant），你主要会调整以下几个参数：
| 参数 | 含义 | 影响 |
|---|---|---|
M |
每个节点在图中的最大连接数（度数）。 | 越大：图越稠密，召回率高，搜索慢，内存占用高。越小：图稀疏，召回率低，搜索快。 |
efConstruction |
建图时动态候选集大小。 | 越大：建图更精确，质量高（召回率高），但建图时间非常慢。 |
efSearch |
搜索时动态候选集大小。 | 越大：搜索精度（召回率）越高，但查询速度越慢。 |
| 优点 | 缺点 |
|---|---|
| 查询速度快：通常被认为是百万/亿级数据上最快的ANNS算法之一，延迟很低。 | 内存占用大：需要存储整个图索引（节点和边），内存显式开销高于 IVF（倒排文件）等算法。 |
| 召回率高：通过分层结构，通常能在低延迟下达到接近100%的召回率。 | 建图慢：特别是 efConstruction 设得较大时，构建索引非常耗时。 |
| 支持动态插入：可以随时插入新向量，无需重建整个索引（但性能最佳仍建议批量构建）。 | 不支持删除：标准的HNSW不支持高效的删除操作（删除后边结构会乱）。 |
算法成熟：有非常优秀的开源实现（如 hnswlib、faiss 中的 HNSW）。 |
参数敏感：调整 M 和 efSearch 需要在速度和精度之间仔细权衡。 |
HNSW vs. 其他主流算法
| 特性 | HNSW | IVF（倒排文件） | PQ（乘积量化） |
|---|---|---|---|
| 搜索速度 | 极快（log n 增长） | 快（取决于 nprobe） |
非常快（内存计算快，但需压缩解码） |
| 内存占用 | 高（存图结构） | 中等（存聚类中心+IVF列表） | 极低（存压缩后的码本） |
| 召回率 | 极高（可达99%+） | 高（需平衡） | 较高（有损失） |
| 动态插入 | ✅ 支持 | ❌ 通常需重建 | ❌ 重建成本高 |
| 适用场景 | 毫秒级低延迟、高精度、在线系统 | 平衡型，大数据集 | 极致节省内存，移动端或超大库 |
在实际项目中的应用
- 向量数据库：Milvus、Weaviate、Qdrant 都将 HNSW 作为核心或主要的索引类型。
- RAG 应用：当你用 LangChain 或 LlamaIndex 搭建 RAG 时，底层的向量存储（如 Chroma、Pinecone、Zilliz）通常默认推荐 HNSW 索引来快速找到相关文档块。
- Faiss：Meta的Faiss库中，
IndexHNSWFlat是最常用的接口之一。
一个简单的类比
- 顶层（高层）：就像国家地图，你只看到大城市（北京、纽约、伦敦），通过高速高铁（长程链接）快速切换到目标国家区域。
- 中间层：城市地图，你看到了各个区（朝阳区、曼哈顿区）。
- 底层：街道地图，你精确地看到每个小区和门牌号（具体向量点）。
总结一句话
HNSW 通过“先跳到远处（高层加快速度），再细查本地（底层保证精度）”的分层图结构，在牺牲一定内存和建库时间的前提下，换取了当今最好的搜索速度与召回率组合。 如果你的应用对查询延迟和召回精度有极高的要求，并且数据库内存足够，通常HNSW 是首选方案。
希望这个解释能帮你理解 HNSW，如果想深入细节，可以查阅原论文《Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs》。
