B+树（B+ Tree）的原理与操作

B+树是一种平衡多路搜索树，广泛应用于数据库和文件系统的索引结构中。它与B树相似，但在内部节点不存储数据，所有数据都保存在叶子节点中，且叶子节点通过指针连接形成有序链表。

一、B+树的基本性质

1. 每个节点最多有m个子节点（m阶B+树）
2. 根节点至少有两个子节点（除非是唯一节点）
3. 内部节点（非根非叶）至少有⌈m/2⌉个子节点
4. 所有叶子节点位于同一层，形成完全平衡
5. 内部节点只存储键（索引键），不存储实际数据
6. 叶子节点存储所有键值对，并通过指针相连

二、B+树的查找操作
查找过程从根节点开始，逐层向下比较：

1. 从根节点开始，在当前节点中找到第一个大于等于目标键的位置
2. 沿着对应的子节点指针向下查找
3. 重复这个过程直到叶子节点
4. 在叶子节点中进行顺序查找或二分查找

示例：在3阶B+树中查找键值25

根节点: [10, 20, 30]  // 找到25∈[20,30)，走第二个子节点
中间节点: [20, 25, 28]  // 找到25∈[25,28)，走第一个子节点
叶子节点: [25, 26, 27]  // 找到目标键

三、B+树的插入操作
插入过程需要保持平衡，步骤包括：

1. 查找合适的叶子节点位置
2. 如果叶子节点有空间，直接插入并保持有序
3. 如果叶子节点已满（键数=m），需要进行分裂：
   a. 创建新叶子节点
   b. 将原节点的键值对平均分配
   c. 将新节点的最小键复制到父节点
   d. 如果父节点已满，递归分裂父节点

示例：向3阶B+树(m=3)依次插入10,20,5,15

初始: [10]
插入20: [10,20]  // 叶子节点未满
插入5: [5,10,20]  // 叶子节点已满，需要分裂
分裂后:
根节点: [10]
叶子节点1: [5,10] → 叶子节点2: [20]
插入15: 找到应插入的叶子节点[5,10,15]  // 再次分裂
最终结构:
根节点: [10,15]
叶子节点1: [5,10] → 叶子节点2: [15,20]

四、B+树的删除操作
删除时也需要保持平衡：

1. 查找包含目标键的叶子节点
2. 删除键值对，如果仍满足最小键数要求(≥⌈m/2⌉-1)，结束
3. 如果键数不足，考虑合并或重分配：
   a. 如果兄弟节点有富余，借一个键
   b. 否则与兄弟节点合并
   c. 更新父节点的索引键

五、B+树与B树的对比优势

1. 范围查询效率高：叶子节点链表支持顺序遍历
2. 查询更稳定：所有查询都要走到叶子节点
3. 内部节点更紧凑：相同内存可存储更多键
4. 更适合磁盘I/O：节点大小通常与磁盘页对齐

B+树通过这些特性，在需要大量磁盘操作的数据存储场景中表现出色，成为数据库索引的事实标准。