B树

一、定义

B树（B-Tree）是一种多路平衡查找树，适用于磁盘等外部存储。

m 阶 B树的定义

1. 每个结点最多有 m 棵子树，m-1 个关键字
2. 每个非根结点至少有 $\lceil m/2 \rceil$ 棵子树，$\lceil m/2 \rceil - 1$ 个关键字
3. 根结点至少有 2 棵子树（除非只有根一个结点）
4. 所有叶子结点在同一层（平衡）
5. 结点结构：$n, P_0, K_1, P_1, K_2, P_2, ..., K_n, P_n$
   • $n$：关键字个数
   • $K_i$：关键字，$K_1 < K_2 < ... < K_n$
   • $P_i$：指向子树的指针

结点结构示意图

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

对于 3 阶 B树（2-3 树）：

• 每个结点最多 2 个关键字，3 棵子树
• 每个非根结点至少 1 个关键字，2 棵子树

二、B树的高度

高度下界

高度 h 的 m 阶 B树至少有：

$$N_{min} = 2 \lceil m/2 \rceil^{h-1} - 1$$

所以：

$$h \leq \log_{\lceil m/2 \rceil} \frac{n+1}{2} + 1$$

高度上界

高度 h 的 m 阶 B树最多有：

$$N_{max} = m^h - 1$$

所以：

$$h \geq \log_m (n+1)$$

三、B树的查找

算法

1. 在结点内顺序查找关键字
2. 若找到，返回
3. 若没找到，沿指针到子树，重复

时间复杂度

• 结点内查找：$O(m)$
• 树高：$O(\log_m n)$
• 总时间：$O(m \log_m n)$

四、B树的插入

算法

1. 找到插入位置（叶子结点）
2. 插入关键字
3. 若关键字个数 $> m-1$，分裂：
   • 取中间关键字上提到父结点
   • 左右两部分作为两个子结点
4. 若父结点也满，递归分裂

分裂示例

3 阶 B树，插入关键字后结点满：[1, 3, 5]

分裂：

• 中间关键字 3 上提
• 左子结点：[1]
• 右子结点：[5]

五、B树的删除

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

• 若删除后关键字数 $\geq \lceil m/2 \rceil - 1$，直接删除
• 若不够，需要借关键字或合并

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

用前驱或后继替换，再删除前驱/后继

借关键字

• 从兄弟结点借一个关键字
• 父结点关键字下移，兄弟关键字上移

合并

• 与兄弟结点合并
• 父结点关键字下移
• 父结点关键字数减少，可能递归

例 1：3 阶 B树插入

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

1. 插入 1：[1]
2. 插入 2：[1,2]
3. 插入 3：分裂，[2] 左右 [1],[3]

       2
      / \
     1   3

4. 插入 4：[2] 左右 [1],[3,4]
5. 插入 5：[2] 左右 [1],[3,4,5] → 分裂，4 上提

       2   4
      / | \
     1  3   5

   （根结点 [2,4]，子树 [1],[3],[5]）
6. 插入 6：[2,4] 左右 [1],[3],[5,6]
7. 插入 7：[2,4] 左右 [1],[3],[5,6,7] → 分裂，6 上提；根 [2,4,6] 满，分裂，4 上提

         4
        / \
       2   6
      / \ / \
     1  3 5  7

例 2：B树高度计算

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

• $h \leq \log_2 \frac{101}{2} + 1 = \log_2 50.5 + 1 \approx 5.66 + 1 = 6.66$
• 高度为整数，故 $h \leq 6$（最大高度为 6；高度 7 至少需 $2^7-1=127$ 个关键字，超过 100）