一句话定义
HNSW（Hierarchical Navigable Small World）把全库组织成多层近邻图：上层稀疏、边长（跨大区域），底层稠密、覆盖全部向量；查询自顶向下贪心导航，到底层后用候选队列 efSearch 做精细扩散——当前低延迟高召回检索的事实标准。
为什么重要
2018 年定型至今，HNSW 是绝大多数向量库（Milvus、Qdrant、pgvector、Elasticsearch、Weaviate 等）的默认或旗舰索引：毫秒内对千万级向量做到 95%+ 召回，且在线只需调一个 efSearch。读懂 HNSW 等于掌握了向量索引的主流域，也掌握了"图索引"这一类的通用原理（Vamana、NSG 同源）。
前置知识
kp-006（Flat 基线）；贪心搜索的直觉（本篇内建立）。
核心概念
- NSW（可导航小世界图）：每个向量是节点，与若干近似近邻连边；长程边让搜索可"跳跃"，短边保证局部精确。
- 启发式选边（heuristic pruning）：新邻居只有当它比现有邻居都"更远于已有邻域"时才保留，避免邻居全挤在一簇、图成"死胡同网络"。
- 分层：每个节点以指数衰减概率出现在更高层；层 0 是全量图，越高越稀疏。
- M：每节点保留的邻居数（层 0 常为 2M），内存与召回的核心参数。
- efConstruction：建库时候选队列长度，决定插入时搜索的"认真程度"。
- efSearch：查询时候选队列长度，≥k，在线唯一旋钮。
原理与机制
插入：随机抽层 l；从顶层入口点贪心下降到第 l 层；在 l 到层 0 的每一层，用 efConstruction 搜索近似近邻，按启发式选出至多 M 条边接入，并回填邻居的反向边（超限则触发邻居重新剪枝）。查询：从顶层入口贪心（每步移向邻居中离 q 最近者，局部最优即止），逐层下降；到层 0 后改为维护大小为 efSearch 的候选堆，持续扩展直到堆内无法改进，返回 top-k。
复杂度：层间跳转 O(log N)，层 0 扩散与 efSearch 近似线性、与 N 弱相关——这是 HNSW 延迟随数据量增长平缓的原因。
参数影响分析：
| 参数 | 召回 | 延迟 | 内存 | 改动成本 |
|---|---|---|---|---|
| M ↑ | 升（图更连通） | 微升 | 图内存近似线性升 | 需重建 |
| efConstruction ↑ | 升（建图质量好） | 建库显著变慢 | 不变 | 需重建 |
| efSearch ↑ | 单调升 | 单调升 | 不变 | 在线可调 |
公式或模型
内存估算（工程近似）：
向量: N × d × bytes(量化前4B)
图: 约等于 N × 2M × 4B × (1 + 上层占比), 层0按每节点2M个邻居、每指针4字节计
例: N=1e7, d=768, M=16, fp32 → 30.7GB + 图约 1.3GB ≈ 32GB 量级图示
层2: A ─────────────────── B (稀疏: 长程边, 快速跨越)
│ │
层1: A ──── C ──────────── B (中等密度)
│ │ │
层0: A─D─E─C─F─G─H─I─J─B─ … (全量: 短边, efSearch 精搜)
查询: 入口A → 顶层贪心跳到B附近 → 逐层下降 → 底层扩散收集top-k实例或案例
1000 万条 768 维、M=16、efConstruction=200 建库约 1~2 小时（单机）；查询 efSearch=64 时 recall@10 ≈ 0.98、p99 ≈ 2 毫秒。同库开 int8 SQ 压缩后内存降约 75%，召回降至 0.96，把 efSearch 提到 128 拉回 0.98、p99 仍 < 4 毫秒——"图导航 + 压缩向量 + 补偿参数"是生产系统的标准组合拳。
直观类比
HNSW 是"城市路网找店"：先上高速（顶层）跨城，再下省道（中层），最后在街巷里（底层）把 efSearch 个候选店都走一遍比较。M 是每个路口能接的街道数，efSearch 是"在街巷里认真逛几家再决定"。
常见误区
- "efSearch 设小于 k"——候选队列比返回数还小，召回必然受损；efSearch ≥ k 是底线，实际常取 k 的 2~8 倍。
- "M 越大越好"——内存线性上涨、建库变慢，而召回边际收益快速递减；16~48 之间按评测选点。
- "HNSW 支持高效删除"——图结构删除困难，多数实现用 tombstone 标记 + 段合并清理（见 kp-022），高频删除需专门评估。
- "增量插入无代价"——持续乱序插入会让图质量缓慢劣化（对比批量构建），大规模写入后建议重建成"干净图"。
自测题
- efConstruction 和 efSearch 分别影响什么？
- 启发式选边解决什么问题？
- N=2000 万、d=1024、M=32、float32，内存量级是多少？
答：前者影响建库时每点接入边的搜索深度，决定图质量与建库耗时；后者影响查询时候选扩散宽度，是在线的召回-延迟旋钮。
答：防止节点邻居全来自同一簇导致图局部"孤岛"、贪心搜索困在局部最优；它强制邻居在方向上互相远离，保证路由多样性。
答：向量 2000 万×1024×4B ≈ 78 GB；图约 2000 万×64×4B ≈ 4.8 GB；合计 80 GB 以上——这是后续引入量化的动机。
与其他知识点的关系
kp-009 是本篇的实操续篇（调参步骤与排错）；kp-010 是树形对照方案；kp-013 的 Vamana 是"单层+可控长边"的图变体；kp-011/012 提供向量压缩与图组合。
延伸阅读
Malkov & Yashunin, "…Hierarchical Navigable Small World graphs"（IEEE TPAMI 2018）——分层、启发式剪枝与全部参数的原始定义，本篇之纲。