B 树

B 树与二叉平衡搜索树理路平衡搜索树Balanced search tree以结构不变量保证对数高度和最坏对数搜索时间的二叉搜索树族。都控制根叶路径，B 树则以多路节点和块传输为对象，让一次读取带回许多键与子指针，用高扇出把二叉结构的多层判断压进一个外存块。半满约束保证节点不会因更新逐渐退化成稀疏长链，叶同深则让任意查找承担相近的块传输次数。

分裂、借位和合并在局部恢复节点占用不变量。插入只可能向上增加一个分隔键，删除只沿访问路径补足即将下降的子女，因此更新无需重写整棵树。

$t=2$ 时，非根节点含 $1$ 到 $3$ 个键，是常见的 2–3–4 树。若一个叶已有三个键，再插入落入该叶区间的键，就先把中键提升到父节点，左右叶各保留一个键，再进入正确一侧。分裂后父节点的区间路由仍完整，两个新叶仍与其他叶同深。

删除若直接从只含 $t-1$ 个键的叶取走目标，会突破最低占用。正确算法在下降前查看兄弟：兄弟有至少 $t$ 个键时借一键；相邻兄弟都只有 $t-1$ 个键时，选其中一个与目标节点合并，并把二者之间的父分隔键下移。

文献中的“order”有时指最大子女数，有时指最小子女数或最大键数；不固定约定便会让节点上下界相差一。重复键、卫星记录放在内部还是外部、节点内采用线性还是二分查找，均属于实现层契约。

B 树用于文件系统、数据库索引和需要外存动态有序集合的场景。块大小越大，可容纳的分隔键越多，树高通常越低；但实际扇出还受键、指针和记录大小影响。I/O 复杂度应以真实节点是否能在一块内传输为前提。

B+ 树把记录全部放到叶层并链接叶节点，适合范围扫描；内部节点负责路由，记录查询与顺序扫描在叶层完成。