一、两类检索，两套解法

做后端的同学应该都有体会：检索这件事，本质上分两种。

第一种是精确检索——"查 id = 10086 的记录"、"查工资在 1万~2万之间的员工"。结果必须一个不多、一个不少，错了就是事故。

第二种是近似检索——"找和这段文字意思最像的文档"、"找长得最像的这张脸"。结果只要**"差不多"就行**，漏掉一两个冷门候选完全可以接受，但速度必须快到毫秒级。

这两种需求，各自催生了各自的事实标准：

  • 精确检索 → B+ 树（MySQL InnoDB、PostgreSQL、SQLite 的默认索引结构）
  • 近似检索 → HNSW（Milvus、Weaviate、Qdrant、FAISS 的主流索引结构）

它们名字里都带个"树"或"图"，但设计哲学天差地别。这篇把它们放一起掰开揉碎地对比——搞清楚它们各自解决什么问题、为什么长成这样、什么时候该用哪个。

二、B+ 树：为磁盘而生的"多路平衡树"

2.1 它长什么样

B+ 树是 B 树（Bayer & McCreight, 1972）的改良版，1973 年由 Knuth 正式命名。它的结构一句话概括：

内部节点只存"导航"信息（键 + 指针），所有数据都放在叶子节点，叶子节点之间用指针连成有序链表。

1
2
3
4
5
6
7
8
9
10
11
                 ┌─────────┐
                 │  [50]   │          ← 内部节点：只导航，不存数据
                 └────┬────┘
            ┌─────────┴─────────┐
       ┌────┴───┐          ┌────┴───┐
       │ [20]   │          │ [80]   │      ← 内部节点
       └───┬────┘          └───┬────┘
    ┌──────┼──────┐      ┌──────┼──────┐
┌───┴──┐ ┌─┴───┐ ┌┴───┐ ┌┴───┐ ┌┴───┐ ┌┴────┐
│10 15 │→│20 35│→│50 60│→│80 90│→│...  │→│...  │  ← 叶子：存数据 + 链表
└──────┘ └─────┘ └────┘ └────┘ └────┘ └─────┘

两个关键设计：

1. 高扇出（fan-out）压树高。 每个节点能装很多键（InnoDB 默认 16KB 一页，能装上千个键），所以树极矮——三层就能装数亿行数据。查找复杂度 O(log N)，而且 log 的底数很大，实际就是"走 3~4 步"。

2. 叶子链表支撑范围查询。 要查"工资 1万~2万"，找到起点后顺着链表往后扫就行，不用回溯树——这是 B+ 树相对 B 树最大的改进。

2.2 为什么它是数据库的事实标准？

特性 对数据库的意义
磁盘友好 节点大小对齐磁盘页（4KB/16KB），一次 I/O 读一整页
矮树 = 少 I/O 3~4 次 I/O 找到任意数据，磁盘随机访问的昂贵被压到最低
有序性 天然支持范围查询、排序、去重、聚合（GROUP BY）
平衡性 所有叶子同深度，最坏情况也是 O(log N)，性能可预期
局部更新 插入/删除只需分裂/合并少量节点，写放大可控

B+ 树的一切设计，都是围绕一个物理现实展开的：磁盘随机读太贵了，必须让"找到数据"这件事只花几次 I/O。

三、HNSW：为内存而生的"分层小世界图"

3.1 它长什么样

HNSW（Hierarchical Navigable Small World，分层可导航小世界图）由 Malkov & Yashunin 在 2018 年提出（论文《Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs》）。它解决的问题是：在几十亿个高维向量里，找到与查询向量"最接近"的 K 个。

它的结构一句话概括：

把数据组织成多层图：底层包含所有节点，越往上节点越稀疏（顶层只有少数"枢纽"），查询从顶层开始，贪心地往"更近的邻居"跳，逐层下探。

1
2
3
4
5
第2层 (最稀疏)     [A]──────────────────────[C]
                   │                        │
第1层          [A]──[B]──[C]─────────────[E]
               │    │    │               │
第0层 (全部)   [A]──[B]──[C]──[D]──[E]──[F]──[G]──[H]──[I]

查询流程（比如找 q 的最近邻）：

1
2
3
1. 从顶层入口点 A 开始，贪心移动到最近的邻居（在顶层：A → C）
2. 下探到第 1 层，继续贪心（C → E）
3. 下探到第 0 层，用候选队列（efSearch）精细搜索，返回 top-K

"小世界"来自社会网络研究的"六度分隔"现象：真实世界的图里，任意两点之间存在很短的路径，所以贪心跳跃能快速逼近目标，而不是遍历全图。

3.2 为什么它是向量检索的事实标准？

特性 对向量检索的意义
对数复杂度 查询路径长度 ∝ log N，十亿级数据也能毫秒级响应
内存友好 数据常驻内存，靠指针跳转，无磁盘 I/O
召回率可控 efSearch 参数在"速度"与"精度"之间连续调节
动态更新 支持增量插入，无需重建索引
近似可接受 检索"足够好"即可——语义相似本就没有唯一正确答案

HNSW 的一切设计，都是围绕另一个物理现实展开的：内存里的指针跳转几乎免费，但"高维空间的相似度"没有天然顺序，必须靠图来导航。

四、核心对比：B+ 树 vs HNSW

维度 B+ 树 HNSW
本质 多路平衡搜索树 分层小世界图
查询类型 精确匹配、范围查询、排序 近似最近邻（top-K 相似）
结果精度 精确，一个不多一个不少 近似，召回率 95%+（可调）
复杂度 O(log N)，稳定可预期 O(log N) 期望，但近似
存储介质 磁盘优先（页对齐） 内存优先（指针跳转）
范围查询 ✅ 天生支持（叶子链表） ❌ 不适用
排序/去重 ✅ 天然有序 ❌ 只返回"最像的"
动态增删 ✅ 局部分裂/合并 ✅ 增量插入，删除较麻烦
显存/内存占用 低（仅键+指针） 较高（每节点多条边，还有多层）
构建成本 批量导入快 构建慢于 B+ 树，需调参
典型场景 数据库主键/二级索引 向量数据库、RAG 检索、推荐
底层数据 结构化标量（id、数值、字符串） 高维向量（embedding）
代表系统 MySQL、PostgreSQL、SQLite FAISS、Milvus、Qdrant、Weaviate

4.1 一个最容易混淆的点

很多人以为 HNSW 能"替代"B+ 树——不能。它俩解决的问题根本不同：

1
2
"工资在 1万~2万之间的员工有多少？"   → B+ 树（范围查询，必须精确）
"和这段 JD 最匹配的简历是哪 5 份？"  → HNSW（相似度检索，近似即可）

B+ 树回答**"哪些满足条件"；HNSW 回答"哪些最像"**。前者没有"像不像"的概念，后者没有"等于不等于"的概念。

4.2 但边界正在模糊

现代数据库已经在融合两者：

  • PostgreSQL 的 pgvector：用 IVFFlat / HNSW 索引做向量相似度检索，跟普通 B+ 树索引共存
  • MySQL 的 HeatWave / 向量扩展：在关系表上直接做 ANN 查询
  • 混合检索（Hybrid Search）：BM25（词法）+ 向量（语义）+ HNSW 索引，用 RRF 融合——这是 RAG 系统的标配

一个真实场景：OA 系统搜文档，"标题精确匹配"走 B+ 树索引，"内容语义相似"走 HNSW 向量索引，两路结果融合后重排。两种索引不是替代关系，是搭档关系。

五、选型决策树

判断该用哪个，三步走：

1
2
3
4
5
6
7
8
你的查询需要精确结果吗？
├── 是 → 数据是标量（id/数字/字符串）？
│       ├── 是 → B+ 树（数据库索引）
│       └── 否 → 精确匹配高维向量（如人脸 1:1 比对）→ 暴力扫描/倒排特化
│
└── 否（近似即可）→ 数据是高维向量（embedding）？
        ├── 是 → HNSW（向量数据库）
        └── 否 → 考虑 BM25 等词法检索

5.1 工程建议

  1. 别用 B+ 树做语义检索——它没有"相似度"概念，只能做精确/范围匹配
  2. 别用 HNSW 做精确查询——它是近似算法，无法回答"等于多少"或"区间是多少"
  3. 长文本检索用混合：B+ 树管结构化条件过滤（部门、时间、状态），HNSW 管语义召回，最后重排
  4. HNSW 调参记住三个数：M（每个节点边数，默认 16~32，越大召回越高越占内存）、efConstruction（构建质量）、efSearch（查询精度旋钮）
  5. 数据量小到几千条就别上 HNSW——暴力扫描就够快，构建索引的开销反而不值

六、总结：一个关于"导航"的故事

把两种索引放到一起看，会发现它们其实是同一道题的两种解法：

如何在浩如烟海的数据里，快速到达"我要的那一片"？

B+ 树的答案：用有序性导航——数据本身有顺序（数字大小、字典序），把顺序组织成矮树，每次排除一半，3~4 步到达。

HNSW 的答案：用相似性导航——数据本身没有顺序（高维向量无从比较大小），但存在"远近"，把远近组织成多层图，从粗到细贪心下探，log N 步到达。

一个靠序，一个靠近。一个是磁盘时代的纪念碑，一个是 AI 时代的里程碑。理解它们的区别，你就理解了后端检索的半壁江山。

工程师视角的一句话总结：B+ 树问"它在哪一排"，HNSW 问"它离谁最近"——前者管精确，后者管相似；现代系统从不二选一，而是让它们各司其职，把答案拼出来。