B树的插入操作

概述

B树的插入操作通过分裂满节点来维护B树性质。与二叉搜索树的插入不同，B树不能简单地在叶子节点添加新关键字——因为叶子节点可能已经满了。核心策略是提前分裂（proactive splitting）：在从根向叶子遍历的过程中，一旦遇到满节点就立即分裂，确保父节点永远不会需要分裂时才发现子节点已满。

核心操作

1. B-TREE-SPLIT-CHILD：分裂满节点

分裂操作

B-TREE-SPLIT-CHILD($x,i$)：将节点 $x$ 的第 $i$ 个子节点 $y$（$y$ 是满的，恰好有 $2t-1$ 个关键字）分裂为两个各含 $t-1$ 个关键字的节点，并将 $y$ 的中间关键字提升到 $x$ 中。

具体步骤：

1. 创建新节点 $z$
2. $y$ 的中间关键字 $k_t$ 提升到 $x$ 的第 $i$ 个位置（$x$ 的关键字和子指针相应右移）
3. $z$ 获得 $y$ 的第 $t+1$ 到 $2t-1$ 个关键字（共 $t-1$ 个）
4. $z$ 获得 $y$ 的第 $t+1$ 到 $2t$ 个子指针（共 $t$ 个）
5. $y$ 保留前 $t-1$ 个关键字和前 $t$ 个子指针
6. $x$ 的关键字数 $n_x$ 增加 $1$，$y$ 和 $z$ 的关键字数均为 $t-1$

分裂示意图

分裂前（$y$ 有 $2t-1$ 个关键字）：

x: [... | c_i=y | ...]
y: [k_1 | k_2 | ... | k_{t-1} | k_t | k_{t+1} | ... | k_{2t-1}]
                          ↑ 中间关键字

分裂后：

x: [... | k_t | c_i=y | c_{i+1}=z | ...]
y: [k_1 | k_2 | ... | k_{t-1}]          z: [k_{t+1} | ... | k_{2t-1}]

关键性质：分裂操作后，$y$ 和 $z$ 各有 $t-1$ 个关键字，满足B树的最小关键字要求（非根节点至少 $t-1$ 个关键字）。

2. B-TREE-INSERT-NONFULL：向非满节点插入

非满节点插入

B-TREE-INSERT-NONFULL($x,k$)：向非满节点 $x$ 插入关键字 $k$。

1. 如果 $x$ 是叶子节点：将 $k$ 直接插入到 $x$ 的正确位置（保持有序）
2. 如果 $x$ 是内部节点：找到 $k$ 应该插入的子节点 $c_i$
   • 如果 $c_i$ 已满：先对 $c_i$ 执行 B-TREE-SPLIT-CHILD($x,i$)，然后确定 $k$ 应该进入分裂后的哪个子节点
   • 递归地将 $k$ 插入到对应的子节点中

3. B-TREE-INSERT：完整插入流程

完整插入

B-TREE-INSERT($T,k$)：向B树 $T$ 插入关键字 $k$。

1. 设 $r=T.\text{root}$
2. 如果 $r$ 已满（$n_r=2t-1$）：
   • 创建新节点 $s$ 作为新根
   • $s$ 的唯一子节点设为 $r$
   • 对 $s$ 执行 B-TREE-SPLIT-CHILD($s,1$)，将 $r$ 分裂为两个节点
   • 树的高度增加 $1$
3. 调用 B-TREE-INSERT-NONFULL 将 $k$ 插入树中

核心性质

1. 提前分裂策略的优势

CLRS采用的是提前分裂（也称”自顶向下分裂”）策略：

• 优点：在向下遍历时就分裂满节点，保证父节点始终有空间接收提升的关键字，插入过程只需单次向下遍历
• 替代方案：也可以采用”自底向上分裂”——先插入叶子，如果溢出再向上分裂。但这种方式在最坏情况下需要两次遍历（一次向下，一次向上）

2. 分裂的传播

• 分裂可能向上传播：如果分裂导致父节点变满，父节点自身也可能需要分裂
• 但由于提前分裂策略，父节点在被需要分裂之前就已经被处理了
• 唯一例外是根节点分裂，此时树的高度增加 $1$

3. 复杂度分析

• 磁盘I/O：$O(h)$ 次
  • 向下遍历：$h$ 次 DISK-READ
  • 分裂操作：每次分裂涉及 $O(1)$ 次 DISK-READ 和 DISK-WRITE
  • 总分裂次数不超过 $h$（因为每次分裂只在一个层级发生）
• CPU时间：$O(t\cdot h)$
  • 每个节点内部的搜索和移动操作为 $O(t)$
  • 共访问 $O(h)$ 个节点

4. B树生长方向

B树从顶部向上生长（与二叉搜索树从底部向上生长不同）：

• 二叉搜索树：新节点总是作为叶子添加，树从下往上长
• B树：新关键字插入叶子，但可能触发分裂使树从上往下长（根分裂导致高度增加）

参见

• B树 — 插入操作所维护的核心数据结构
• B树的删除操作 — 与插入对称的复杂操作
• B树节点的磁盘表示 — 插入操作中 DISK-READ/WRITE 的底层实现
• 最小度 — 分裂操作的参数依据