B树与B+树的插入与删除操作详解

B树和B+树是平衡多路搜索树，广泛应用于数据库和文件系统中，用于高效管理磁盘数据。下面我们重点讲解B树和B+树的插入与删除操作，涵盖核心规则、步骤分解及实例演示。

一、B树的插入操作

核心规则：

1. 每个节点最多包含 \(m-1\) 个关键字（\(m\) 为阶数），最少需满足 \(\lceil m/2 \rceil -1\) 个关键字（根节点除外）。
2. 插入操作始终在叶子节点进行（非叶子节点仅因分裂而被动插入）。
3. 若插入后节点关键字数超过 \(m-1\)，需进行分裂。

步骤详解（以阶数 \(m=3\) 的B树为例，即2-3树）：

1. 查找插入位置：从根节点开始，根据关键字大小递归向下找到目标叶子节点。
2. 插入关键字：将新关键字按升序插入叶子节点。
   • 例：插入关键字 5，若叶子节点为 [3, 8]，插入后变为 [3, 5, 8]。
3. 检查节点溢出：若节点关键字数达到 \(m\)（本例为3），需分裂：
   • 取中间关键字 5 提升到父节点。
   • 左子节点保留 [3]，右子节点保留 [8]。
4. 递归处理父节点：若父节点因提升关键字后溢出，继续分裂，可能导致树高增长。

实例演示（初始空树，依次插入 1, 2, 3, 4, 5）：

• 插入 1, 2：根节点为 [1, 2]。
• 插入 3：根节点溢出，分裂为：

      根节点 [2]
      /      \
   [1]       [3]
  

• 插入 4：先找到叶子节点 [3]，插入后为 [3, 4]，无需分裂。
• 插入 5：叶子节点 [3, 4, 5] 溢出，分裂为 [3] 和 [5]，中间值 4 提升到父节点 [2]，父节点变为 [2, 4]。

二、B树的删除操作

核心规则：

1. 删除后需满足节点关键字数不低于 \(\lceil m/2 \rceil -1\)。
2. 若删除后关键字数不足，需通过借位或合并修复。

步骤详解（分情况讨论）：
情况1：删除叶子节点中的关键字

• 若删除后关键字数仍满足最小值，直接删除。
• 若不足：
  a. 向左兄弟借：若左兄弟关键字数充足，将父节点中分隔关键字下移，左兄弟的最大关键字上移到父节点。
  b. 向右兄弟借：类似左兄弟操作。
  c. 合并：若兄弟节点关键字数均不足，将当前节点与一个兄弟合并，并下移父节点的一个关键字。

情况2：删除非叶子节点中的关键字

• 找到该关键字的左子树最大值（或右子树最小值），替换待删除关键字，转化为删除叶子节点的问题。

实例演示（从 [2, 4] / [1] [3] [5] 中删除 4）：

1. 4在非叶子节点，用左子树最大值 3 替换，变为删除叶子节点中的 3。
2. 叶子节点 [3] 删除后为空，但需满足最小关键字数（\(m=3\) 时最小为1），故向左兄弟 [1] 借位：父节点 2 下移，左兄弟 1 上移，最终树结构变为：

        [1, 2]
       /   |   \
    []    [ ]   [5]  （实际需调整指针）
   

   （注：具体调整需根据兄弟节点实际情况，此处为简化示意）

三、B+树的插入与删除特点

与B树的主要区别：

1. 关键字分布：B+树非叶子节点仅存索引，所有关键字均出现在叶子节点，且叶子节点通过指针链接。
2. 插入操作：仅在叶子节点插入，分裂时中间关键字同时保留在左右叶子节点，并复制到父节点索引中。
3. 删除操作：
   • 若叶子节点关键字数不足，借位或合并规则与B树类似。
   • 但非叶子节点中的关键字只需在叶子节点删除后判断是否仍需保留（若叶子节点无该关键字则删除索引）。

实例对比（B+树插入 [1, 2, 3] 后分裂）：

• 叶子节点分裂为 [1, 2] 和 [2, 3]（关键字2被保留），父节点索引为 [2]。
• 删除关键字2时，仅删除叶子节点中的一个2，若叶子节点仍存在2，则索引保留。

四、关键复杂度分析

• 插入/删除时间复杂度：\(O(\log n)\)，因每次操作需遍历树高，且分裂/合并操作成本有限。
• 磁盘I/O优化：B树/B+树通过减少树高和节点大小匹配磁盘页，降低磁盘访问次数。

通过以上步骤，可以系统掌握B树和B+树的动态维护机制，理解其如何在高并发磁盘存储中保持稳定性能。