B 树

B 树

每 $d$ 代合并为一个超级节点，每个节点中包含 $2^d－1$ 个关键码，有 $m=2^d$ 路 每次读入一个超级节点 逻辑上与 BBST 等价。 充分利用外存的批量访问，每次读入一组关键码。 实际一般取 $m=|page|/|key|$

$m$ 阶 B 树，每个节点的分叉数不超过 $m$ 内部节点各含 $n\le m-1$ 个关键码，各有 $n+1\le m$ 路 分支数：

• 根节点 $n+1\ge 2$
• 其余 $n+1\ge \lceil m/2\rceil$ 可以称作 $(\lceil m/2\rceil ,m)$ - 树，分支数范围为 $[\lceil m/2\rceil ,m]$

查找

从根节点开始，先在当前节点内顺序查找，若成功，返回，若失败，找到孩子节点，将其读入内存

$${\log }_m(N+1)\le h\le 1+\lfloor {\log }_{\lceil m/2\rceil }\frac{N+1}{2}\rfloor$$

相比 BBST，树高降低为 $1/{\log }_{2}m\sim 1/({\log }_{2}m-1)$

性能

主要由 I/O 决定，也即搜索层数，$O(\log n)$

插入

先进行查找，然后将关键码插入到节点中的对应位置，插入外部节点，检查关键码数量，若超出，进行上溢修复： 取中位数 $s=\lfloor m/2\rfloor$，以关键码 $k_s$ 为界划分为左右两个节点，$k_s$ 上升一层，以两个节点作为左右孩子。

• ! 上溢可能持续发生，可以逐层向上传播，最多上升 $O(\log n)$ 层，分裂 $O(\log n)$ 次
• 若根节点上溢，则提升的关键码自成节点，B 树高度增高一层（唯一增高情况）

删除

先进行查找，若目标关键码不在叶子节点，则找到它的中序直接后继，交换二者并删除目标关键码，若此时节点关键码数量低于 $\lceil m/2\rceil -1$ 个节点，进行下溢修复： 非根节点下溢时，必恰有 $\lceil m/2\rceil -2$ 个关键码和 $\lceil m/2\rceil -1$ 个分支。 根据其左右兄弟的规模分类处理，设当前节点为 V，父节点为 P。

• 若 L 存在且至少包含 $\lceil m/2\rceil$ 个关键码，P中的分界关键码移动到作为最小关键码，将 L 中最大关键码移动到分界关键码（该关键码的右孩子设置为 V 的最小关键码的左孩子），旋转后下溢修复完毕
• 若 R 存在且至少包含 $\lceil m/2\rceil$ 个关键码，作对称的旋转处理，旋转后下溢修复完毕
• 否则，至少存在一个兄弟（不妨设为 L），必然恰有 $\lceil x/2\rceil -1$ 个关键码，取 P 中的分界关键码，置于左右序列中间，将左右节点合并为一个节点（此时节点关键码数量必为 $m-1$ 个），此时 P 可能继续下溢
• ! 下溢可能持续发生，可以逐层向上传播，最多上升 $O(\log n)$ 层，合并 $O(\log n)$ 次
• 若由于子节点下溢后根节点中的唯一关键码用于合并两个子节点，则将根节点重新设置为合并后的唯一子节点，B 树高度下降一层（唯一降低情况）