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