B 树

形式陈述 ​

本页采用 minimum degree $t\ge 2$ 的约定。B 树每个节点保存递增键 $k_1<\cdots <k_r$；含 $r$ 个键的内部节点有 $r+1$ 个子女，第 $i$ 个子树只含相邻分隔键所界定区间内的键。除根外，每个节点含 $t-1$ 到 $2t-1$ 个键；非叶根至少含一个键；所有叶位于同一深度。这些条件同时给出搜索次序、最低占用率与全局平衡。

查找在当前节点内定位分隔区间，再只沿一个子女下降。插入时，在进入满节点前把其中间键提升到父节点，并将余下键分成两个至少含 $t-1$ 个键的节点；若根已满，先分裂根并使树高增加一。删除下降前保证目标子女至少有 $t$ 个键：可向有富余键的相邻兄弟借位并旋转父分隔键，或把两个最小占用兄弟与父分隔键合并；空根最终由唯一子女替代。

若一个节点恰好装入一个外存块公理库外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。，树高为 $O({\log }_{t}N)$，搜索、插入和删除沿根叶路径只需同阶 I/O。节点内部比较成本另按 RAM 或比较模型报告，不能从 I/O 界中抹去。

直觉 ​

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

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

例子与边界 ​

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

删除若直接从只含 $t-1$ 个键的叶取走目标，会突破最低占用。正确算法在下降前查看兄弟：兄弟有至少 $t$ 个键时借一键；两个兄弟都最小时，把父分隔键下移后合并。若省略这一步而只写“最后再平衡”，返回路径上可能已经缺少恢复所需的局部信息。

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

推论与应用 ​

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

B+ 树把记录全部放到叶层并链接叶节点，适合范围扫描；它复用 B 树的高扇出与占用思想，却改变了内部节点和查询终点，需作为独立结构定义。

参考资料

• Rudolf Bayer and Edward M. McCreight, “Organization and Maintenance of Large Ordered Indexes,” Acta Informatica 1, 1972, pp. 173–189.
• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, Ch. 18, B-trees.