B+树

概述

B+树是B树的重要变体，所有数据（或数据指针）仅存储在叶节点中，内部节点只存储索引关键字用于路由。叶节点通过链表连接，支持高效的范围查询。B+树是现代数据库系统和文件系统中使用最广泛的索引结构。

定义

B+树的严格定义

一棵最小度为 $t$ 的B+树满足以下性质：

1. 内部节点：每个内部节点有 $[t,2t]$ 个子节点，存储 $[t-1,2t-1]$ 个索引关键字（不关联数据）
2. 叶子节点：每个叶子节点存储 $[t,2t]$ 个数据关键字（关联实际数据或数据指针）
3. 叶子链表：所有叶子节点通过指针按关键字顺序连接成双向链表
4. 所有叶子同层：与B树相同，所有叶子节点位于同一层
5. 内部节点的关键字是子树中最大（或最小）关键字的副本

与B树的结构对比

B树：                          B+树：
  [3 | 7 | 15]                   [7 | 15]
  /   |    |   \                 /    |    \
[1,2] [3,5,6] [7,9,12] [15,20]  [1,3,5,6] [7,9,12] [15,17,20]
  ↑ 数据在各层                    ↑ 数据只在叶子层
                                  叶子: [1,3,5,6] ↔ [7,9,12] ↔ [15,17,20]
                                         ↑ 链表连接

核心性质

1. 内部节点与叶子节点的分离

特性	B树	B+树
数据存储位置	所有节点	仅叶子节点
内部节点内容	关键字 + 数据指针	仅索引关键字
叶子节点链表	无	有（双向链表）
内部节点关键字	数据的关键字	子树中最大/最小关键字的副本
范围查询	需要中序遍历	沿链表顺序扫描

2. 范围查询优势

B+树最大的工程优势在于范围查询：

范围查询对比

查询 $[5,12]$ 范围内的所有记录：

B树：

1. 搜索到 $5$ 所在的节点
2. 执行中序遍历，需要在树的各层之间反复跳转
3. 每次跳转可能涉及不同的磁盘页，I/O不可预测

B+树：

1. 搜索到 $5$ 所在的叶子节点（$O(h)$ 次I/O）
2. 沿叶子链表顺序扫描到 $12$（连续的磁盘I/O，可利用预读优化）
3. 总I/O次数 = $O(h)+O(\text{范围内记录数}/\text{每页记录数})$

3. 内部节点更小

由于内部节点不存储数据，只存储索引关键字，每个内部节点可以容纳更多的索引项：

• 更大的分支因子 $\Rightarrow$ 更低的树高 $\Rightarrow$ 更少的I/O次数
• 典型场景中，B+树比同参数的B树矮一层

4. 查询性能的一致性

在B+树中，无论查找哪个关键字，都需要从根遍历到叶子节点，I/O次数恒为 $O(h)$。

在B树中，某些关键字可能在内部节点就被找到，I/O次数可能少于 $O(h)$，但这种不均匀性使得性能预测更困难。

工程应用

MySQL InnoDB

MySQL InnoDB 存储引擎使用 B+树 作为索引结构：

参数	值
页大小	16KB
主键索引（聚簇索引）	叶子节点存储完整行数据
二级索引	叶子节点存储主键值（再通过主键索引回表查询）
叶子链表	双向链表，支持正向和反向范围扫描

聚簇索引（Clustered Index）是 InnoDB 的重要设计：表的数据按主键顺序物理存储在 B+树的叶子节点中，因此主键查询只需一次 B+树查找即可获取完整行数据。

PostgreSQL

PostgreSQL 也使用 B+树 作为默认索引类型：

• 支持唯一索引、多列索引、表达式索引
• 叶子节点存储指向堆表元组的物理位置指针（CTID）
• 支持并发B+树（ Lehman & Yao 算法）

其他应用

• 文件系统：NTFS、ext4、XFS 等使用 B+树 或其变体管理目录和文件元数据
• 键值存储：LevelDB、RocksDB 的 MemTable 使用跳表，SSTable 使用 B+树 索引
• 内存数据库：Redis 的某些实现使用 B+树 管理排序集合

参见

• B树 — B+树的基础结构
• B树节点的磁盘表示 — B+树同样遵循磁盘页对齐的设计思想
• 最小度 — B+树中内部节点和叶子节点可能有不同的最小度参数