是一种平衡树。设阶数 （即 叉树），则每个节点含 个元素。
插入时都是加在叶子节点内。当一个节点超过 个元素，取中间一个向上推，左右两边分开作为儿子。
这保证了每个节点至少含有 个元素，较为“饱满”。同时这个分裂操作保证左右形态是对称的，维持树高在 log 级。
而对于删除操作，如果删除的元素位于非叶子（internal）节点，可以与其前驱或后继交换，转换为删除叶子上元素。
在删除后，若“至少含有 个元素”的限制被打破，可以从同层级的左右节点移元素过来；若左右节点也不足，则该节点与左右节点之一合并。
左节点、父亲、当前节点的大小分别有如下上界：
故合并之后的节点不多于 个元素。
以上的做法维持了 B-Tree 的两条限制：节点大小、树形态。于是可以证明复杂度是 log 的。
B-Tree 算法比我之前见到的平衡树有趣，但似乎竞赛中少有使用。在工业界 B-Tree 有所应用，如文件系统和数据库等。
好难写。唉，DS。