B树

B树的定义

B树（B-Tree）是一种自平衡树，能够保持数据有序。这种数据结构能够让查找数据、顺序访问、插入数据及删除的动作，都在对数时间内完成。B树减少定位记录时所经历的中间过程，从而加快存取速度。B树这种数据结构可以用来描述外部存储。这种数据结构常被应用在数据库和文件系统的实现上。

在B树中，内部（非叶子）节点可以拥有设定范围内数量的子节点。当数据被插入或从一个节点中移除，它的子节点数量发生变化。为了维持在预先设定的数量范围内，内部节点可能会被合并或者分离。因为子节点数量有一定的允许范围，所以B树不需要像其他自平衡查找树那样频繁地重新保持平衡，但是由于节点没有被完全填充，可能浪费了一些空间。

B树中每一个内部节点会包含一定数量的键值。通常，键值的数量被选定在d和2d之间（即某个数值以及该数值的两倍间）。如果一个内部节点有2d个键值，那么添加一个键值给此节点的过程，将会拆分2d键值为2个d键值的节点，并把中间值节点添加给父节点。每一个拆分的节点需要最小数目的键值。相似地，如果一个内部节点和他的邻居两者都有d个键值，那么将通过它与邻居的合并来删除一个键值。删除此键值将导致此节点拥有d-1个键值;与邻居的合并则加上d个键值，再加上从邻居节点的父节点移来的一个键值。结果为完全填充的2d个键值。

B树有以下特性：

1. 所有的叶子结点都位于同一层级（即从根节点到任意一个叶子节点的路径长度均相等）。
2. 定义最小维度d，每个节点最多包含2d-1个键；除根节点外的每个节点最少包含d-1个键；根节点最少包含1个键。
3. 任意节点的子节点个数等于该节点包含键值数+1（意味着根节点至少有两个子节点，每个节点最多有2d个子节点）
4. 键值在节点中按照递增顺序排列
5. B树查询、插入和删除操作时间复杂度跟其他平衡二叉搜索树一样是O(logN)

B树的插入

• 首先根据键值找到要插入的节点位置
• 如果节点还有空间则直接插入即可
• 如果节点已满（即达到2d-1个键），则将中间的键值取出放到父节点，两侧则分裂成两个子节点，并将键值插入到相应位置
• 如果中间值放到父节点时父节点已满，则同样进行上面的分裂操作

B树的删除

假设要删除的是键x

• 如果查找到的键x在叶子节点
  1. 当叶子节点包含至少d个键时，则直接删除即可，同时如果父节点只包含d-1个键，父节点相邻的兄弟姐妹节点有同样包含d-1个键的话，这两个父节点可以合并；
  2. 当叶子节点只包含d-1个键，则查看它的相邻的兄弟姐妹节点是否有至少d个键，如果有则从父节点中取出一个键放到叶子节点，从相邻的至少有d个键的兄弟姐妹节点取出一个放到父节点上，如果相邻兄弟姐妹节点都是d-1个键，则跟其中一个合并，且这两个叶子节点的父键作为合并节点的中心键，然后删除键x。
• 如果键x在中间节点且该节点包含至少d个键：
  1. 如果键x的左子节点有包含至少d个键，则将左子节点上面最接近键x的键移到x所在节点并删除键x
  2. 如果键x的左子节点只包含d-1个键，则检查右子节点，如果右子节点键包含至少d个键，则将右子节点上最接近键x的键移到x所在节点并删除x
  3. 如果键x的左右子节点均只包含d-1个键，那么将键x的右子节点和键x一起合并到左子节点并删除键x
• 如果键x在中间节点且节点只包含d-1个键
  1. 如果该节点相邻的兄弟姐妹节点有至少d个键，则相邻兄弟姐妹节点取出最靠近父键的键替换父键，将父键放到中间节点后进行键x删除操作
  2. 如果该节点相邻的兄弟姐妹节点均只有d-1个键，那么将两个节点合并，将父键做中间键值，然后做删除键x的操作