AI产业链地图

HNSW

又名 Hierarchical Navigable Small World · 层次可导航小世界图 · HNSW 算法

HNSW 由 Yury Malkov 于 2016 论文 *"Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs"* 提出。核心思路

第三层 · AI 基础设施
首次提出2016关键参与方Milvus · Weaviate · Qdrant · hnswlib

HNSW（Hierarchical Navigable Small World 层次可导航小世界图）

当前 向量数据库 事实标准 的 ANN 索引算法 — 用"多层可导航图"结构，把 N 个高维向量的查询复杂度降到 O(log N)，召回率可达 95-99%。

定义

  1. 多层结构：类比"跳表"（Skip List），底层包含所有向量节点，上层包含逐层稀疏的子集
  2. 可导航小世界图：每层节点形成图，每个节点与少量邻居（M=16~64）相连
  3. 从顶向下查询：从最高层入口开始贪心搜索 → 沿图边移向查询点 → 逐层下降 → 在底层精确定位 Top-K

关键超参数

参数 含义 典型值
M 每节点最大邻居数 16-48
efConstruction 构建时候选集大小 200-500
efSearch 查询时候选集大小 50-500（越大召回越高/越慢）
层数 自动决定（与 log N 成正比） 层

性能特点

  • 召回率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 等磁盘/量化方案。

相关

所属AI原生中间件与开发平台