简介
简单来说，B-Tree 是针对大数据存取的平衡树，考虑了磁盘读取对查找效率的影响。
B-Tree 的主要思想是通过减少磁盘读取次数来提高数据存取性能，而磁盘读取次数与树高相关。故B-Tree 允许每个节点拥有多于 2 个的子节点来减小树高。
与二叉平衡树类似，B-Tree 中的每个节点存储若干键值（keys）以及子节点地址。
定义和性质
阶（order）：将子节点的允许最大数量定义为阶，如图 1 为 5 阶树。
$m$ 阶的 B-Tree 满足以下定义：
- 每个节点最多能有 $m$ 个子节点。
- 每个内部节点至少有 $\lceil \frac m2\rceil$ 个子节点，内部节点（Internal nodes）为除根节点和叶节点以外的节点。
- 拥有 $k+1$ 个子节点的非叶节点存有 $k$ 个键值。
- 每个节点中的键值按递增排序。
- 所有的叶节点高度一样。
操作
对于平衡🌳的操作主要就是插入（Insertion）和删除（Deletion）。
以下操作均基于键值两两不同的假设进行讨论，同时键值的数量范围定义为 $[d, 2d]$，阶 $m=2d+1$。
插入
首先找到键值归属的叶节点，插入到该节点中，节点的键值数量可能超过上限 $2d$，即当前键值数量为 $2d+1$。
此时用中位数将该节点划分成两个新的节点，每个新节点含有 $d$ 个键值，如图 2 所示。
之后将键值中位数插入到父节点中，父节点的键值数量 +1，也有可能超上限，故需要迭代更新。
删除
主要思路
将内部节点中的删除操作转移至叶节点中，然后自下而上重新平衡，达到键值数量要求。
叶节点
直接将对应的键值删除即可。
内部节点
假设当前删除键值为 $k$，则 $k$ 的前继 $prev(k)$ 为左子树中的最大键值，后继 $succ(k)$ 为右子树中的最小键值。
$prev(k)$ 和 $succ(k)$ 均可替代 $k$ 作为分割左、右子树的新键值，同时这两个键值必然在叶节点中，进而将删除操作转移到叶节点中。
重平衡
在叶节点删除键值后可能出现键值数量为 $d-1$ 导致下溢出。此时通过转移兄弟节点的键值来完成键值补充，主要分两种情况：
合并：当前节点的左、右兄弟节点均只有 $d$ 个键值，此时可与其中一个兄弟节点及父节点中的分割键值合并，新节点的键值数量为 $2d$，相当于节点分裂的逆操作。此时父节点的键值数量减 1，需要迭代重平衡。
图 3. 节点合并 旋转：假设右兄弟节点的键值大于 $d$ 个（左兄弟同理），将父节点的分割键值插入到当前节点中，右兄弟节点的第 1 个键值插入到父节点中。此时当前节点、兄弟节点和父节点的键值数量均满足键值数量要求，完成平衡操作。
图 4. 旋转操作