B 树与 B+ 树：数据库索引为什么这样设计

我真正开始理解“B 树与 B+ 树：数据库索引为什么这样设计”，不是在背完某段代码之后，而是在一次次写错之后。最明显的问题是：我以前只知道数据库索引常用 B+ 树，却说不清为什么内存里的红黑树到了磁盘上就不合适了。把这些错误重新摊开来看，我才找到比口诀更可靠的理解方式。

B 树和 B+ 树不是为了替代普通二叉搜索树，而是为磁盘、数据库索引和范围查询设计的多路平衡搜索结构。它们的核心目标是：降低树高，减少磁盘 IO。

它从哪里来

B 树由 Rudolf Bayer 与 Edward McCreight 在 1970 年前后提出，目标不是让比较次数看起来更漂亮，而是减少昂贵的磁盘访问。一个节点容纳多个键，正好可以对应一个磁盘页；B+ 树把数据集中到叶子并连接叶子，更适合范围扫描和数据库索引。

为什么需要多路树

普通二叉树每个节点最多两个孩子，如果数据量很大，树高会比较高。内存里多走几层问题不大，但数据库索引通常要落到磁盘页里，一次节点访问可能就是一次页读取。

B 树和 B+ 树让一个节点存多个 key 和多个孩子。每个节点更“宽”，树就更“矮”。

B+ 树结构

图：B+ 树内部节点负责导航，叶子节点保存完整数据并按顺序连接

B+ 树常见特点：

• 所有数据都在叶子节点。
• 非叶子节点只保存索引 key，用来决定往哪个子树走。
• 叶子节点之间通过链表连接。
• 所有叶子节点在同一层，查询路径长度稳定。

B 树与 B+ 树区别

对比点	B 树	B+ 树
数据存放	内部节点和叶子节点都可存数据	通常只在叶子节点存数据
范围查询	中序遍历多个层级	先定位起点，再扫叶子链表
单点查询	可能在内部节点结束	一般都走到叶子节点
数据库索引	可用，但范围扫描不如 B+ 树顺	更常见

查询过程

以查找 key=45 为例：

1. 从根节点开始。
2. 在节点内部用二分找到应该进入的孩子区间。
3. 继续向下，直到叶子节点。
4. 在叶子节点里查找目标 key。

如果是范围查询 [30, 70]，先定位到第一个大于等于 30 的叶子位置，然后沿叶子链表向右扫描，直到超过 70。

为什么数据库喜欢 B+ 树

数据库索引关注的不只是算法复杂度，还关注磁盘页、范围查询和缓存命中。

B+ 树适合数据库索引，主要有几个原因：

• 树高低，IO 次数少。
• 非叶子节点不存完整数据，可以放更多 key。
• 叶子节点有序连接，范围查询顺。
• 所有查询路径最终到叶子层，性能更稳定。

和红黑树的区别

红黑树适合内存中的有序 Map，例如 Java 的 TreeMap。B+ 树适合外部存储和页式管理。

如果把红黑树用于磁盘索引，节点太小、层级太深，会导致频繁随机 IO。B+ 树牺牲节点内部复杂度，换来更少的磁盘访问次数。

我的分析

学习 B+ 树时，不要只背“数据库索引用 B+ 树”。真正要理解的是：算法结构会受硬件影响。内存里我们关心比较次数；磁盘里我们更关心页读取次数。

B+ 树是一个很好的例子：它不是理论上唯一能查找的数据结构，但它在数据库这种工程环境里非常合适。

面试题

1. B+ 树为什么比二叉搜索树更适合数据库索引？
2. B 树和 B+ 树的数据存放有什么区别？
3. B+ 树为什么适合范围查询？
4. 为什么非叶子节点不存完整数据可以降低树高？
5. 红黑树和 B+ 树分别适合什么场景？