B树
B树也称B-树,它是一颗多路平衡查找树。描述一颗B树时需要指定它的阶数，阶数表示了一个结点最多有多少个孩子结点，一般用字母m表示阶数。当m取2时，就是我们常见的二叉搜索树。
一颗m阶的B树定义如下：
- 每个结点最多包含m个子结点；且M>2
- 根结点的儿子数为[2, M]
- 除根结点以外，非叶子结点的子结点数为[M/2, M]
- 每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）
- 非叶子结点的关键字个数=指向儿子的指针个数-1；
- 非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；
- 非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键字属于(K[i-1], K[i])的子树；
- 所有叶子结点位于同一层；
插入
插入在叶节点级别完成。要将项目插入B树，需要遵循以下算法。
- 遍历B树以找到可插入节点的适当叶节点。
- 如果叶节点包含少于m-1个键，则按递增顺序插入元素。
- 否则，如果叶节点包含m-1个键，则按照以下步骤操作。
- 按元素的递增顺序插入新元素。
- 将节点拆分为中间的两个节点。
- 将中值元素推送到其父节点。
- 如果父节点还包含m-1个键，则按照相同的步骤将其拆分。
删除
还在叶节点处执行删除。 要删除的节点可以是叶节点或内部节点。 需要遵循以下算法才能从B树中删除节点。
- 找到叶节点。
- 如果叶节点中有多于m/2个键，则从节点中删除所需的键。
- 如果叶节点不包含m/2个键，则通过从8个或左兄弟中获取元素来完成键。
- 如果左侧兄弟包含多于m/2个元素，则将其最大元素推送到其父元素，并将插入元素向下移动到删除键的节点。
- 如果右侧兄弟包含多于m/2个元素，则将其最小元素向上推送到父节点，并将插入元素向下移动到删除键的节点。
- 如果兄弟节点都不包含多于m/2个元素，则通过连接两个叶节点和父节点的插入元素来创建新的叶节点。
- 如果父节点的节点少于m/2，那么也应在父节点上应用上述过程。
- 如果要删除的节点是内部节点，则将节点替换为其有序后继或前一个节点。 由于后继或前任将始终位于叶节点上，因此该过程将类似于从叶节点中删除节点。
应用场景
- 查找磁盘中的大量数据。
- 数据库中的索引。
参考
B+树
B+树是B树的变体，有着更高的查询性能。