采用预拆分的偶阶B树高度是否与给定键集的插入顺序无关

你的推测是正确的：对于固定的键集合，采用预拆分（preemptive splitting）策略的偶阶B树，无论键的插入顺序如何，最终的树高始终保持一致。

核心原因说明 #

预拆分的核心规则完全消解了插入顺序对节点分裂时机的影响：

• 偶阶B树的阶数通常记为2d，规则要求每个节点最多存储2d-1个键。预拆分策略要求向已满节点插入新键之前，先将该满节点分裂为两个各存储d-1个键的节点，同时将中间键上浮到父节点；如果父节点也处于满状态，就递归向上执行分裂操作，根节点满时分裂会让树高加1。
• 该策略下节点分裂的触发逻辑只和节点当前键数是否达到上限有关，和插入的键值大小、插入位置完全无关。对于总数为N的固定键集合，树高的取值是唯一确定的，满足公式 d^h ≤ N ≤ (2d)^h - 1。

和普通B树的差异对比 #

普通无预拆分的B树只有插入后键数超过上限才会触发分裂，不同插入顺序会导致分裂时机完全不同：比如升序插入时只有最右侧节点会反复触发分裂，和随机插入的分裂次数、最终树高都可能存在差异。而预拆分强制所有节点的填充率不会超过固定阈值，不会出现单边节点反复分裂的情况，固定键集合的总分裂次数是固定值，最终树高自然唯一。

内容的提问来源于stack exchange，提问作者redrobinyum