| 性质 | 要求 |
|---|
| 子树数 | 每个节点最多 m 棵子树 |
| 关键字数 | 每个节点最多 m-1 个关键字 |
| 非根节点 | 最少 $\lceil m/2 \rceil$ 棵子树，$\lceil m/2 \rceil - 1$ 个关键字 |
| 根节点 | 最少 2 棵子树（若非叶），1 个关键字 |
| 有序性 | 节点内关键字递增排列，子树间的关键字介于相邻关键字之间 |
| 叶节点 | 所有叶节点在同一层（通过失败节点表示） |
B树示例（3 阶 B树）
[30]
/ \
[10,20] [40,50]
/ | \ / | \
[5] [15] [25] [35] [45] [55]
B树的基本操作
查找
1. 在当前节点的关键字中顺序/折半查找
2. 若找到，返回
3. 若未找到，沿着对应的子树指针向下
4. 到达叶节点的失败指针，查找失败
插入
1. 先查找插入位置（一定是叶节点层）
2. 插入关键字
3. 若节点关键字数 > m-1，则分裂：
- 取中间关键字上移到父节点
- 左右两部分作为两个子节点
4. 若父节点也溢出，继续分裂（可能传播到根）
删除
1. 若删除的是叶节点关键字，直接删除
2. 若删除的是内部节点关键字，用前驱/后继替换后再删
3. 若删除后关键字数 < ⌈m/2⌉-1：
- 兄弟够借 → 借一个（旋转）
- 兄弟不够借 → 合并
4. 合并可能导致父节点也下溢，继续处理