B树是一种平衡的多路搜索树，多用于文件系统，数据库的实现。

B树

一棵 m 阶B树是一棵平衡的 m 路搜索树。它或者是空树，或者是满足下列性质的树：

根节点至少有两个子树；
每个非根节点所包含的元素个数 j 满足：┌m/2┐ - 1 <= j <= m - 1；
除根节点以外的所有节点（不包含叶子节点）的度数正好是元素总数加1，故“内部子树”个数 k（度）满足：┌m/2┐ <= k <= m；
所有的叶子节点都位于同一层。

特点

一个节点可以存储超过两个元素，可以拥有超过两个节点。
拥有二叉搜索树的一些性质，如：平衡，每个节点的所有子树高度一致。
比较矮。
每个节点中元素从小到大排列。

m 阶 B 树的性质（m >= 2）

假设一个节点存储的元素个数为 j，则根节点：1 <= j <= m-1，非根节点：┌m/2┐ - 1 <= j <= m - 1。

如果有子节点，子节点个数 y = j + 1，则根节点的子节点个数：2 <= y <= m。非根节点的子节点个数：┌m/2┐ <= y <= m。
比如 m = 3，2 <= y <= 3，因此可以成为（2，3）树或 2-3 树；
比如 m = 4，2 <= y <= 4，因此可以成为（2，4）树或 2-3-4 树；
比如 m = 5，3 <= y <= 5，因此可以成为（3，5）树；
比如 m = 6，3 <= y <= 6，因此可以成为（3，6）树；
比如 m = 7，4 <= y <= 7，因此可以成为（4，7）树；

B树01.png
B树02.png
B树03.png

在数据库的实现中一般用 200~300 阶B树。

B树 VS 二叉搜索树

二叉搜索树 -> 3阶B树
B树05.png
B树01.png

B树和二叉搜索树，在逻辑上是等价的。拿一个二叉搜索树为例，通过多代节点合并，可以获得一个超级节点，如：
2 代合并的超级节点，最多拥有 4 个子节点（至少是 4 阶B树）；
3 代合并的超级节点，最多拥有 8 个子节点（至少是 8 阶B树）；
n 代合并的超级节点，最多拥有 2^n 个子节点（至少是 2^n 阶B树）；

m 阶B树，最多需要 log2(m) 带合并。

2 代合并：
B树06.png

搜索

步骤：

先在节点内部从小到大开始搜索元素；
如果命中，搜索结束；
如果为命中，再去对应的子节点中搜索元素，重复步骤1；

如：搜索 52
B树07.png
搜索 72：

添加

新添加的元素必定是添加到叶子节点。
假设这是一棵4阶B树：
B树09.png
添加 55：
B树10.png
添加 95：
B树11.png

上溢（overflow）

插入 98 时，最右下角的叶子节点（90、95、98、100）的元素个数超过限制，这种现象可以称之为：上溢（overflow）。
插入 98，产生上溢：
B树12.png

上溢的解决

m 阶B树上溢节点的元素个数必然等于 m。
假设上溢节点最中间元素的位置为 k，将 k 位置的元素向上与父节点合并。
将 [0, k-1] 和 [k+1, m-1] 位置的元素分裂成 2 个子节点，这 2 个子节点的元素个数必然都不会低于最低限制 ┌m/2┐ - 1。
一次分裂完毕后，有可能导致父节点上溢，依然按照上述方法解决。最极端的情况，有可能一直分裂到根节点。

假设有一个5阶B树，插入了 34 产生上溢：
从图中可以看到，上溢节点的元素个数等于5，即B树的阶数。
B树17.png
上溢节点最中间元素的位置为 2，将 2 位置的元素向上与父节点合并。
将 [0, 1] 和 [3, 4] 位置的元素分裂成2个子节点。这2个子节点的元素个数都等于2（必然都不低于最低限制┌m/2┐ - 1）。
B树18.png
分裂完毕后，导致父节点上溢。按照上述方法，将最中间位置的元素向上与父节点合并。最极端的情况是，一直分裂到根节点。
B树19.png