B树与B+树的插入与删除操作详解 一、问题描述 B树和B+树是平衡多路搜索树，广泛应用于数据库和文件系统中，用于高效管理磁盘数据。它们的核心特性是每个节点可包含多个键和子节点，通过保持树的高度较低来减少磁盘I/O次数。插入和删除操作需维护树的平衡性（如节点键数范围约束），本文将逐步分析这两种操作的执行逻辑与平衡策略。 二、B树的插入操作 1. 基本规则 B树定义：度为 \( t \) 的B树满足以下性质： 根节点至少包含1个键（除非为空树）。 非根节点至少包含 \( t-1 \) 个键，至多包含 \( 2t-1 \) 个键。 节点键数超出上限时需 分裂 。 2. 插入步骤 步骤1：定位插入位置 从根节点开始，递归向下查找待插入键 \( k \) 应属的叶子节点。查找过程中若遇到已满节点（键数 = \( 2t-1 \)），先进行 预分裂 ，避免回溯分裂。 步骤2：叶子节点插入 在叶子节点中插入 \( k \)，保持键值有序（类似有序数组插入）。 步骤3：处理节点溢出 若插入后节点键数 > \( 2t-1 \)，则进行分裂： 将节点分为三部分： 左半部分：前 \( t-1 \) 个键 中间键：第 \( t \) 个键 右半部分：后 \( t-1 \) 个键 将中间键上提至父节点，左、右部分作为两个新子节点。 若父节点也因此溢出，则递归向上分裂，可能使树高增加（根节点分裂时）。 示例 （以 \( t=2 \) 的B树为例，键范围 [ 1,3 ]）： 初始树：根节点 [10, 20] 插入 5 ： 根节点已满，先分裂根节点（若需要，但此处直接插入叶子节点？需明确场景）。实际插入需从根向下查找，假设叶子节点 [5, 8] 已满，则分裂后上提中间键到父节点。 三、B树的删除操作 1. 核心挑战 删除键可能导致节点键数低于下限（ \( t-1 \) ），需通过 借键 或 合并 修复。 2. 删除步骤 情况1：删除键在叶子节点 直接删除键。 若删除后键数 < \( t-1 \)： 若左或右兄弟节点有富余键（键数 > \( t-1 \)），向兄弟 借一个键 （通过父节点中转）。 若兄弟节点键数均 = \( t-1 \)，与一个兄弟节点 合并 ，并删除父节点中对应的分隔键。合并可能使父节点键数不足，需递归向上修复。 情况2：删除键在内部节点 找到键的前驱（左子树最大键）或后继（右子树最小键），将其值复制到待删除键的位置，然后 删除前驱/后继 （转化为叶子节点删除问题）。 示例 （ \( t=2 \) ）： 树：根节点 [10] ，左子节点 [5, 8] ，右子节点 [15, 20] 删除 10 （内部节点）： 用前驱 8 替换 10 ，变为删除叶子节点中的 8 。 叶子节点 [5] 删除 8 后剩 [5] （键数 =1 ≥ \( t-1 \)），无需修复。 四、B+树的插入与删除差异 1. 结构特点 B+树所有数据存储在叶子节点，内部节点仅存键和指针；叶子节点通过指针链接成有序链表。 2. 插入操作 类似B树，但分裂时： 叶子节点分裂：复制中间键到父节点（B树是移动），叶子节点保留所有键。 内部节点分裂：中间键上提至父节点（同B树）。 3. 删除操作 若键在叶子节点：直接删除。若键数不足，借键或合并逻辑同B树，但需更新父节点中的键（可能用右兄弟最小键替换）。 若键在内部节点：删除后无需替换（因数据仅在叶子节点），但需确保父节点键仍能正确索引子树。 五、关键要点总结 插入核心 ：预分裂避免回溯，分裂后中间键上提。 删除核心 ：借键优先于合并，内部节点删除转化为叶子节点删除。 B+树优势 ：叶子链表支持范围查询，内部节点更紧凑。 平衡维护 ：所有操作保证节点键数满足 \( [ t-1, 2t-1 ] \)，树高均衡。 通过以上步骤，B树/B+树在动态增删数据时始终保持低高度，适合磁盘存储场景。