B+树

---

B+树是B树的一种变体和优化，专门为数据库索引和文件系统设计，它在B树的基础上做了关键改进，使其更适合磁盘存储和数据库查询模式。

1. B+树是什么？

B+树是一种平衡的、多路的搜索树，它专门为磁盘或其他直接存取的辅助存储设备而设计。

下面来拆解它的关键特性：

• 平衡树：从根节点到任何一个叶子节点的路径长度都是相同的。这保证了查询性能的稳定性和可预测性，不会出现某些数据查得极快，某些极慢的情况。

• 多路搜索树：一个节点可以有多个子节点（通常是上百个），这远大于二叉树（每个节点最多2个子节点）。这使得B+树非常“矮胖”，从而大大减少了磁盘I/O次数。

• 为磁盘设计：磁盘读写的特点是顺序读写快，随机读写慢。B+树的结构充分利用了磁盘块（页）的预读能力，每次读取一个完整的节点（通常大小等于一个磁盘页），从而最大化I/O效率。

2. B+树的结构详解

一棵典型的B+树包含两种类型的节点：非叶子节点（索引节点） 和 叶子节点（数据节点）。

2.1. 非叶子节点（索引节点）

• 不存储实际数据，只存储键值（Key） 和指向子节点的指针（Pointer）。

• 它的作用就像一个路由导航，告诉你下一步应该去哪个子节点继续查找。

• 假设一个节点最多可以存储 m 个键值和 m+1 个指针，那么它的结构通常是：

  [P1, K1, P2, K2, P3, ..., Pm, Km, P(m+1)]

  • 其中 K1 < K2 < ... < Km。

  • 指针 P_i 所指向的子树中，所有键值都 >= K(i-1) 且 < K_i。（具体范围定义可能略有不同，但思想一致）

2.2. 叶子节点（数据节点）

• 存储真正的数据。这里的数据有两种形式：

  1. 实际的数据行（记录）：在InnoDB的聚簇索引中，叶子节点直接存储了整行数据。

  2. 主键值：在非聚簇索引中，叶子节点存储的是索引键值和对应的主键。

• 所有叶子节点之间通过一个双向链表连接起来。

• 叶子节点的结构通常是：

  [K1, D1], [K2, D2], ..., [Km, Dm], Next_Pointer

  • [Ki, Di] 是键值-数据对。

  • Next_Pointer 指向下一个叶子节点。

2.3. 简单的B+树示例（假设m=3）

                              [根节点]
                               | 10 |
                             /       \
                            /         \
               [非叶子节点]                [非叶子节点]
            | 5 | 8 |     |         | 15 | 20 |    |
           /    |    \    |        /     |     \   |
          /     |     \   |       /      |      \  |
[叶子节点] [叶子节点] [叶子节点] [叶子节点]  [叶子节点] [叶子节点]
|1,2,4| -> |5,6,7| -> |8,9| -> |10,11,14| -> |15,17,18| -> |20,21,25|

• 所有数据都在叶子节点，并且是有序的。

• 叶子节点之间通过指针相连，形成了一个有序链表。

3. B+树的优势（为什么是它？）

与它的前身B树以及其他数据结构（如哈希、二叉树）相比，B+树在数据库索引场景下具有压倒性优势：

1. 更高效的磁盘I/O

   • B+树的节点可以存储非常多的键，使得整棵树非常“矮胖”。对于一个拥有百万级数据的表，B+树的高度可能只有3-4层。

   • 这意味着查找任何一条记录，最多只需要3-4次磁盘I/O（从根节点到叶子节点），性能极高。

2. 卓越的范围查询性能

   • 这是B+树相对于B树的核心优势。

   • 在B树中，数据遍布在所有节点，进行范围查询（如 WHERE id BETWEEN 10 AND 20）需要进行复杂的中序遍历。

   • 在B+树中，所有数据都在叶子节点，并且叶子节点形成了有序链表。一旦找到了范围的起始点（如10），只需要沿着链表向后遍历即可，效率极高。

3. 查询性能稳定

   • 由于所有查询都必须走到叶子节点才能拿到数据，所以任何一次查询的路径长度都是相同的（等于树高），性能稳定。

   • 而在B树中，如果数据在根节点，一次查询就返回；如果在叶子节点，则需要走到最下层。性能不稳定。

4. 更高的空间利用率

   • 非叶子节点只存储键值和指针，不存储数据，所以一个节点可以容纳更多的索引项。这等效于进一步增加了树的出度（子节点数），降低了树的高度。

4. B+树在数据库中的具体应用（以MySQL InnoDB为例）

• 主键索引（聚簇索引）：

  • 叶子节点存储的是完整的行数据。

  • 表数据本身就是按主键组织的B+树索引。

• 二级索引（非聚簇索引/辅助索引）：

  • 叶子节点存储的不是完整数据，而是该索引的键值和对应的主键值。

  • 当通过二级索引查询时，数据库先找到对应的主键，然后再用这个主键回到主键索引（聚簇索引） 中查找完整的行数据。这个过程称为回表。

总结

特性	解释	带来的好处
多路平衡树	节点有多个子节点，树保持平衡	树高很低，减少磁盘I/O次数
数据全在叶子节点	只有叶子节点存储数据（或指针）	查询路径等长，性能稳定
叶子节点形成链表	所有叶子节点通过指针顺序连接	范围查询效率极高，只需遍历链表
节点大小匹配磁盘页	一个节点通常设计为一次磁盘I/O的大小	充分利用磁盘预读，I/O高效

正是这些精心设计的特性，使得B+树成为关系型数据库索引事实上的标准数据结构。