B 树的「阶」是什么？一棵 m 阶 B 树要满足哪些性质？
简化版
B 树的阶（order）m 指「一个节点最多能有多少个孩子」。一棵 m 阶 B 树的核心约束是：每个节点最多 m 个孩子、m-1 个关键字；除根外每个节点至少 ⌈m/2⌉ 个孩子（即至少 ⌈m/2⌉-1 个关键字）——这个「至少一半满」的下限保证了树不会太瘦长；所有叶子节点都在同一层，保证完美平衡。
详细版
一棵 m 阶 B 树满足：
- 每个节点最多 m 个孩子、最多 m-1 个关键字。
- 除根节点外，每个节点至少 ⌈m/2⌉ 个孩子，即至少 ⌈m/2⌉-1 个关键字。
- 若根节点不是叶子，则根至少 2 个孩子。
- 每个节点内的关键字从小到大有序排列。
- 有 k 个关键字的节点恰好有 k+1 个孩子，第 i 个孩子子树的所有值落在第 i-1 和第 i 个关键字之间。
- 所有叶子节点都在同一层（B 树是完美平衡的）。
举例：一棵 4 阶 B 树，每个节点最多 4 个孩子、3 个关键字；除根外每个节点至少 ⌈4/2⌉=2 个孩子、至少 1 个关键字。
完整版教学
一、阶 m 的含义
「阶」是描述 B 树「胖瘦」的参数，指一个节点最多容纳的孩子数。m 越大，节点越「胖」（能存越多关键字）、树越矮。实际的数据库里，m 由「一个磁盘页能装下多少关键字」决定——比如一页 16KB、每个索引项约 14 字节，那 m 就约 1000。所以阶不是随便定的，而是用磁盘页大小算出来的。
二、为什么要有「至少半满」的下限（性质 2）
性质 2「除根外每个节点至少 ⌈m/2⌉ 个孩子」是 B 树的灵魂。它规定每个节点至少半满，作用是：
- 防止树退化：如果允许节点只有 1 个孩子，B 树就可能退化成链。要求至少半满，就保证了每下降一层，规模至少缩小到 ⌈m/2⌉ 分之一，从而树高稳定在 O(logₘn)。
- 保证空间利用率：节点至少半满，空间利用率有下限（≥50%），不至于大量节点空着浪费磁盘。
插入删除时的「分裂」和「合并/借位」，本质就是为了始终维持这条「至少半满、至多全满」的约束。
三、关键字与孩子的数量关系
一个有 k 个关键字的节点，有 k+1 个孩子。因为 k 个有序关键字把数轴分成了 k+1 段区间，每段对应一个孩子子树：
关键字: [ 20 | 50 ]
/ | \
孩子: (<20) (20~50) (>50) ← 2 个关键字 → 3 个孩子这个「k 个关键字 → k+1 个孩子」的关系是 B 树查找、插入、删除时定位的基础。
四、根节点的特殊性
根节点被单独放宽（性质 3）：普通节点至少 ⌈m/2⌉ 个孩子，但根至少 2 个孩子就行（只要它不是叶子）。原因是整棵树只有一个根，无法保证它也半满——当树很小时根可能只有很少关键字。极端情况整棵树只有一个节点（既是根又是叶子），关键字数可以从 1 到 m-1。
五、阶的不同定义（避免踩坑）
要注意教材对「阶」的定义略有出入：
- 主流定义（本文采用）：m 阶 = 最多 m 个孩子。
- Knuth 定义：也有按「最多 m 个孩子」定义的，但有些资料用「每个节点最少 t 个关键字」的「最小度数 t」来描述（B 树最小度数 t 对应最多 2t 个孩子）。
面试时说清楚自己用的定义即可，核心约束（最多 m 孩子、至少半满、叶子同层）是一致的。
六、常见误区与追问
| 考点 | 正确口径 |
|---|---|
| m 阶 | 最多 m 个孩子、最多 m-1 个关键字 |
| 下限 | 非根节点至少约半满 |
| 平衡 | 所有叶子同层 |
maxChildren = m
maxKeys = m - 1
minChildren(non-root) = ceil(m / 2)B 树的“阶”描述的是节点容量上限，不是树高。
- 误区：m 阶表示每个节点必须有 m 个孩子。 m 是上限，非根节点还要满足至少半满的下限。
- 误区：关键字数量和孩子数量相等。 有 k 个关键字的内部节点通常有 k+1 个孩子。
- 误区：根节点必须和普通节点下限一样。 根节点是特殊情况，可以少于半满；非空根至少有一个 key 或两个孩子。
- 追问：为什么要至少半满？ 防止节点过稀导致树高升高，也保证空间利用率和复杂度上界。
- 追问：不同资料对阶的定义为何不同？ 有的把阶定义为最大孩子数，有的定义为最小度 t；答题时要先说明口径。
- 追问：所有叶子同层意味着什么？ 查找任意 key 的路径长度相同量级，避免某些路径过长。
七、加强记忆
m 阶 B 树的「阶」= 一个节点最多的孩子数。核心性质：最多 m 个孩子/m-1 个关键字；除根外至少 ⌈m/2⌉ 个孩子（半满，防退化、保空间利用率）；根至少 2 个孩子；关键字有序、k 个关键字对应 k+1 个孩子；所有叶子同层（完美平衡）。阶由磁盘页大小决定。注意教材对「阶」定义有差异，答题先说清定义。