概念
B树是在二叉树、平衡二叉树等基础上演变而来的，为适用于磁盘等外存存储而设计的的平衡查找树。
一个B树一般有如下特征：
- M阶B树，每个节点最多可以包含M-1个Key(Data)和M个子节点（子树）。
- 除了根节点和叶节点之外，B树中的每个节点至少包含m / 2个子节点。
- 根节点必须至少具有两个子节点。
- 所有叶子节点必须处于同一深度。
如下图就是一个B树结构。
1.png
其中每个节点中存放当前节点包含的键值（Key/Data）和指向下一个节点的指针。
B树上查找
B树中的搜索与二叉树中的搜索相似。例如，如果我们在以下B树中搜索数据49。该过程将如下所示：
- 将项目49与根节点78进行比较。由于49 <78，因此移至其左子树。
- 从40 <49 <56开始，遍历40的右子树。
- 49> 45，向右移动。比较49。
- 找到匹配项，返回。
2.png
在B树中搜索复杂度取决于树的高度。搜索算法需要O（log n）时间来搜索B树中的任何元素。
B树上插入
插入在叶节点级别完成。为了将元素插入B树，需要遵循以下算法。
- 遍历B树，以找到可以在其上插入节点的适当叶节点。
- 如果叶节点包含少于m-1个键，则按升序插入元素。
- 否则，如果叶子节点包含m-1个键，则请执行以下步骤。
- 按元素的升序插入新元素。
- 将节点拆分为中间的两个节点。
- 将中值元素推到其父节点。
- 如果父节点也包含m-1个键，请按照相同的步骤将其拆分。
示例：已有如下5阶B树结构。
3.png
将节点8插入如图结构中，插入完成后如图。
4.png
现在该节点包含5个键，因此需要分裂。将中值8上推至父节点，如图所示。
5.png
B树上删除
删除也在叶节点上执行。要删除的节点可以是叶节点或内部节点。为了从B树删除节点，需要遵循以下算法。
- 找到叶节点。
- 如果叶节点中有m/2个以上的键，则从该节点中删除所需的键。
- 如果叶节点没有 m/2个以上键，则通过从右侧或左侧同级中获取键值来完成键。
- 如果左侧同级包含m / 2个以上的元素，则将其最大元素推至其父元素，然后将中间元素向下移至删除键的节点。
- 如果右侧同级元素包含m / 2个以上的元素，则将其最小元素上移到父元素，然后将中间元素下移到删除键的节点。
- 如果两个兄弟节点均不包含m / 2个以上的元素，则通过连接两个叶节点和父节点的中间元素来创建新的叶节点。
- 如果父节点少于m / 2个节点，则也对父节点应用上述过程。
如果要删除的节点是内部节点，则用其顺序的后继节点或前继节点替换该节点。由于后继者或前任者将始终在叶节点上，因此该过程与从叶节点中删除该节点的过程类似。
示例：
从下图所示的5阶B树中删除节点53。
6.png
53位于元素49的右子元素中。将其删除。
7.png
现在，57是节点中剩余的唯一元素。每个节点中必须存的最小数量是2（5/2），所以他需要找到同级的左右节点。而同级的兄弟节点都不包含>2的元素，所以通过连接左兄弟和父节点的中间节点49再加上当前节点，共同构成新的节点。
8.png
