HNSW（Hierarchical Navigable Small World 层次可导航小世界图）
当前 向量数据库 事实标准 的 ANN 索引算法 — 用"多层可导航图"结构，把 N 个高维向量的查询复杂度降到 O(log N)，召回率可达 95-99%。
定义
HNSW 由 Yury Malkov 于 2016 论文 "Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs" 提出。核心思路：
- 多层结构：类比"跳表"（Skip List），底层包含所有向量节点，上层包含逐层稀疏的子集
- 可导航小世界图：每层节点形成图，每个节点与少量邻居（M=16~64）相连
- 从顶向下查询：从最高层入口开始贪心搜索 → 沿图边移向查询点 → 逐层下降 → 在底层精确定位 Top-K
关键超参数
| 参数 | 含义 | 典型值 |
|---|---|---|
M |
每节点最大邻居数 | 16-48 |
efConstruction |
构建时候选集大小 | 200-500 |
efSearch |
查询时候选集大小 | 50-500（越大召回越高/越慢） |
| 层数 | 自动决定（与 log N 成正比） | 5-10 层 |
性能特点
- 召回率：95-99%（典型配置下接近暴力搜索）
- 查询复杂度：O(log N)，比暴力 O(N) 快 1000×
- 缺点：内存占用大（向量+图边，3-5× 向量本身）；增量更新代价较高
工业实现
| 系统 | HNSW 实现 |
|---|---|
| hnswlib | C++ 原创参考实现 |
| Faiss | IndexHNSWFlat |
| Milvus | 默认索引选项之一 |
| Weaviate | 默认 ANN 索引 |
| Qdrant | 默认 ANN 索引 |
| Elasticsearch | 8.x 内置 HNSW |
| pgvector | 0.5.0+ 支持 |
与其他算法的对比
| 算法 | 召回率 | 速度 | 内存 | 大规模性 |
|---|---|---|---|---|
| HNSW | 95-99% | 极快 | 大 | 中（受内存约束） |
| IVF-Flat | 90-95% | 快 | 中 | 高 |
| IVF-PQ | 80-95% | 极快 | 小 | 极高（十亿级） |
| DiskANN | 95% | 快 | 极小（磁盘） | 极高 |
| 暴力 | 100% | 慢 | 小 | 低 |
在 AI 产业链中的位置
绝大多数 向量数据库 在"中小规模 + 高召回"场景的默认选择。一旦数据量超过单机内存（典型 1-10 亿向量），需切换到 IVF-PQ / DiskANN 等磁盘/量化方案。
相关
∈ belongs_to::3-07-AI原生中间件与开发平台