B+树

一、定义

B+树是B树的变体，广泛用于数据库索引和文件系统。

m 阶 B+树的定义

• 每个结点最多 m 棵子树，m 个关键字
• 每个非根结点至少有 $\lceil m/2 \rceil$ 棵子树，$\lceil m/2 \rceil$ 个关键字
• 根结点至少有 2 棵子树
• 叶子结点包含全部关键字，用链表连接
• 非叶子结点只起索引作用，不存储数据

二、结点结构

非叶子结点（索引结点）

┌──┬──┬──┬──┬──┬──┐
│P0│K1│P1│K2│P2│K3│P3│
└──┴──┴──┴──┴──┴──┘

• $n$ 个关键字，$n$ 棵子树
• $K_i$ 是第 i 棵子树中最大（或最小）关键字

叶子结点

┌──┬──┬──┬──┬──┬──┬──┐
│K1│D1│K2│D2│K3│D3│P │
└──┴──┴──┴──┴──┴──┴──┘

• 包含全部关键字和数据指针
• 叶子之间用链表连接

三、B+树 vs B树

四、B+树的查找

1. 从根开始查找

• 在非叶子结点中找关键字确定子树方向
• 最终到达叶子结点

2. 顺序查找（范围查询）

• 通过叶子链表顺序遍历
• 支持范围查询

查找特点

• 每次查找都到叶子：路径长度相同
• 支持范围查询：叶子链表
• 查找效率稳定：所有查找深度相同

五、B+树的插入

算法

1. 找到插入位置（叶子结点）
2. 插入关键字
3. 若叶子结点满（关键字数 $> m-1$），分裂：
   • 左结点：前 $\lceil m/2 \rceil$ 个
   • 右结点：后 $\lfloor m/2 \rfloor$ 个
   • 右结点的最小关键字复制到父结点
4. 若父结点也满，递归分裂

六、B+树的删除

情况 1：删除叶子结点关键字

• 若删除后关键字数 $\geq \lceil m/2 \rceil$，直接删除
• 若不够，从兄弟借或合并
• 更新父结点索引

情况 2：删除非叶子结点关键字

• 实际上只需更新索引
• 不影响叶子结点

例 1：3 阶 B+树插入

依次插入：1, 2, 3, 4, 5

1. 插入 1：叶子 [1]
2. 插入 2：叶子 [1,2]
3. 插入 3：叶子 [1,2,3] → 分裂
   • 左叶子 [1,2]，右叶子 [3]
   • 复制 3 到父结点

         3
        / \
      [1,2]  [3]

4. 插入 4：右叶子 [3,4]
5. 插入 5：右叶子 [3,4,5] → 分裂
   • 左叶子 [3,4]，右叶子 [5]
   • 复制 5 到父结点

         3   5
        / | \
      [1,2][3,4][5]

例 2：B+树范围查询

叶子链表：[1,2] → [3,4] → [5,6] → [7,8]

查询关键字 $\geq 4$：

• 先找到叶子 [3,4]
• 从 4 开始沿链表遍历：4, 5, 6, 7, 8

例 3：B+树高度计算

100 个关键字的 3 阶 B+树，最大高度？

• 叶子结点至少 $\lceil 3/2 \rceil = 2$ 个关键字，最少叶子数 $\lceil 100/2 \rceil = 50$
• 根至少 2 棵子树，其余非叶子结点至少 $\lceil 3/2 \rceil = 2$ 棵子树
• 高度为 $h$ 时关键字数至少为 $2^h$
• 由 $2^h \leq 100$ 得 $h \leq \log_2 100 \approx 6.64$
• 高度为整数，故最大高度为 6（高度 7 至少需 $2^7=128$ 个关键字，超过 100）