B树的删除操作

概述

B树的删除操作是B树最复杂的操作，通过借关键字和合并来修复下溢。与B树的插入操作的”提前分裂”策略类似，删除采用"提前保障"策略：在从根向叶子遍历的过程中，确保当前节点在下降到子节点之前，目标子节点至少有 $t$ 个关键字，从而避免回溯。

核心思想

删除操作的关键挑战：直接删除关键字可能导致节点关键字数低于最小值 $t-1$（即发生下溢）。为此，需要在下降过程中提前确保每个被访问的节点都有足够的关键字。

三种删除情况

情况1：关键字 $k$ 在叶子节点 $x$ 中

直接从 $x$ 中删除 $k$。由于 $x$ 是叶子，删除不影响其他节点。

前提

在下降到 $x$ 之前，已经通过提前保障策略确保 $x$ 至少有 $t$ 个关键字，因此删除后 $x$ 至少有 $t-1$ 个关键字，不会下溢。

情况2：关键字 $k$ 在内部节点 $x$ 中

需要找到替代关键字来填充 $k$ 的位置，然后递归删除替代关键字：

• 情况2a：$k$ 的前驱子节点 $c_i$（$k$ 左侧的子树）至少有 $t$ 个关键字

  • 找到 $c_i$ 中最大的关键字 $k^{\prime }$（即 $k$ 的直接前驱）
  • 用 $k^{\prime }$ 替换 $x$ 中的 $k$
  • 递归地从 $c_i$ 中删除 $k^{\prime }$

• 情况2b：$k$ 的后继子节点 $c_{i+1}$（$k$ 右侧的子树）至少有 $t$ 个关键字

  • 找到 $c_{i+1}$ 中最小的关键字 $k^{\prime }$（即 $k$ 的直接后继）
  • 用 $k^{\prime }$ 替换 $x$ 中的 $k$
  • 递归地从 $c_{i+1}$ 中删除 $k^{\prime }$

• 情况2c：$c_i$ 和 $c_{i+1}$ 都只有 $t-1$ 个关键字

  • 将 $k$ 与 $c_i$ 和 $c_{i+1}$ 合并为一个节点
  • $k$ 下移到合并后的节点中
  • 递归地从合并后的节点中删除 $k$

情况3：关键字 $k$ 不在当前内部节点 $x$ 中

确定 $k$ 应该在的子节点 $c_i$。在下降到 $c_i$ 之前，需要确保 $c_i$ 至少有 $t$ 个关键字：

• 情况3a：$c_i$ 只有 $t-1$ 个关键字，但相邻兄弟 $c_{i-1}$ 或 $c_{i+1}$ 至少有 $t$ 个关键字

  • 借关键字（旋转）：从兄弟节点借一个关键字通过父节点转移给 $c_i$
  • 例如，$c_{i-1}$ 有 $\ge t$ 个关键字时：
    • 将 $x$ 中 $c_i$ 和 $c_{i-1}$ 之间的关键字 $k_{i-1}$ 下移到 $c_i$ 的开头
    • 将 $c_{i-1}$ 的最后一个关键字上移到 $x$ 中 $k_{i-1}$ 的位置
    • 将 $c_{i-1}$ 的最后一个子指针转移到 $c_i$
  • 借关键字后，$c_i$ 有 $t$ 个关键字，可以安全下降

• 情况3b：$c_i$ 和所有相邻兄弟都只有 $t-1$ 个关键字

  • 合并：将 $c_i$ 与一个兄弟节点合并
  • 将 $x$ 中分隔两者的关键字下移到合并后的节点中
  • 合并后节点有 $2t-1$ 个关键字
  • 如果 $x$ 是根且变空，合并后的节点成为新根，树高度减 $1$

修复操作详解

借关键字（旋转）

借关键字操作是合并的逆操作，与B树的插入操作中的分裂操作具有对称性：

操作	方向	触发条件
分裂（插入）	节点 $\to$ 父节点（上移中间关键字）	节点满（$2t-1$个关键字）
借关键字（删除）	父节点/兄弟 $\to$ 节点（下移关键字）	节点下溢（$<t-1$个关键字）

合并

合并操作是分裂的逆操作：

• 分裂：一个 $2t-1$ 关键字节点 $\to$ 两个 $t-1$ 关键字节点 + 1 个关键字上移
• 合并：两个 $t-1$ 关键字节点 + 1 个关键字下移 $\to$ 一个 $2t-1$ 关键字节点

核心性质

1. 提前保障策略

与插入的提前分裂类似，删除采用提前保障策略：

• 向下遍历时：如果当前节点的目标子节点只有 $t-1$ 个关键字，立即通过借关键字或合并来修复
• 保证：到达叶子节点时，该节点至少有 $t$ 个关键字，删除后至少 $t-1$ 个，不会下溢
• 结果：只需单次向下遍历，无需回溯

2. 复杂度分析

• 磁盘I/O：$O(h)$ 次
  • 向下遍历：$h$ 次 DISK-READ
  • 借关键字/合并：每次 $O(1)$ 次 DISK-READ 和 DISK-WRITE
  • 总修复操作次数不超过 $h$
• CPU时间：$O(t\cdot h)$

3. 树高度变化

• 删除可能导致树高度减少（当根的子节点合并导致根变空时）
• 这与插入导致树高度增加恰好相反

4. 与插入操作的对称性

插入操作	删除操作
节点溢出（$2t-1$ 个关键字）	节点下溢（$<t-1$ 个关键字）
分裂（split）	合并（merge）
树可能长高	树可能变矮
提前分裂	提前保障

参见

• B树 — 删除操作所维护的核心数据结构
• B树的插入操作 — 与删除对称的操作，分裂与合并的对照
• 最小度 — 下溢判定和修复操作的参数依据