B-树的插入操作

描述
B-树是一种平衡多路搜索树，广泛应用于数据库和文件系统中，用于高效管理磁盘数据。与二叉搜索树不同，B-树的每个节点可以包含多个键和多个子节点指针，这减少了树的高度，从而降低了磁盘I/O次数。B-树的插入操作需要维护树的平衡性，确保每个节点（除根节点外）的键数在预定义的范围内。

B-树的性质

1. 每个节点最多有m个子节点（m阶B-树）。
2. 根节点至少有2个子节点（除非它是叶子节点）。
3. 非根非叶节点至少有⌈m/2⌉个子节点。
4. 所有叶子节点位于同一层。
5. 节点中的键按升序排列，键的数量在⌈m/2⌉-1到m-1之间（非根节点）。

插入操作步骤
假设有一个m阶B-树，插入新键k：

1. 查找叶子节点：

   • 从根节点开始，递归向下查找k应插入的叶子节点。
   • 比较k与当前节点的键，找到第一个大于或等于k的键，进入对应子节点，重复直到叶子节点。

2. 插入键到叶子节点：

   • 若叶子节点的键数小于m-1，直接将k按顺序插入到该节点，操作结束。
   • 若插入后键数等于m（溢出），需进行分裂操作。

3. 节点分裂（处理溢出）：

   • 设溢出节点为N，包含键[K₁, K₂, ..., Kₘ]（m个键）。
   • 取中间键K₍m/2₎（例如m=5，取第3个键）。
   • 分裂N为三部分：
     • 左节点：包含键[K₁, ..., K₍m/2₎-₁]
     • 中间键：K₍m/2₎
     • 右节点：包含键[K₍m/2₎+₁, ..., Kₘ]
   • 将中间键提升到父节点，并链接左、右节点到父节点。
   • 若父节点因此溢出，递归向上分裂，可能直到根节点。

4. 根节点分裂：

   • 若根节点溢出，分裂后创建新根节点，原根节点分裂为左右子节点，树高增加1。

示例（3阶B-树，键数范围[1,2]）
插入序列[5, 8, 3, 7, 1]：

1. 插入5：根节点为[5]（叶子）。
2. 插入8：根节点[5, 8]（未溢出）。
3. 插入3：根节点[3, 5, 8]（溢出，m=3）。
   • 分裂：中间键5提升为新根，左节点[3]，右节点[8]。树高增加。
4. 插入7：从根5开始，7>5进入右节点[8]，插入后为[7,8]（未溢出）。
5. 插入1：从根5开始，1<5进入左节点[3]，插入后[1,3]（未溢出）。最终树结构：

     [5]
    /   \
 [1,3]  [7,8]

关键点

• 插入始终在叶子节点进行，确保所有叶子在同一层。
• 分裂操作通过提升中间键维持平衡，递归处理可能传播到根。
• 时间复杂度O(log n)，其中n为键总数，因树高为对数级。