B 树和 B+ 树适用于频繁的 I/O 操作，广泛应用于文件存储系统以及数据库系统中。

转载自 https://www.jianshu.com/p/cf7dba86c391

B 树

定义

B 树（B-tree）是一种平衡的多路查找树，结点最大的孩子数目称为 B 树的阶（Order）。

多路查找树（Multi-way search tree）：每一个结点的孩子树可以多于两个，且每个结点可以存储多个元素。

一个 m 阶的 B 树具有如下属性：

根结点至少有两个子女
每个非根节点所包含的关键字个数 j 满足： $\lceil m/2 \rceil - 1 \le j \le m - 1$
除根结点以外的所有结点（不包括叶子结点）的度数正好是关键字总数加 1，故 内部子树 个数 k 满足： $\lceil m/2 \rceil \le k \le m$
所有的叶子结点都位于同一层
所有分支结点包含下列信息数据 $( n, A_0, K_1, A_1, K_2, A_2, …, K_n, A_n )$ $(n, A_{0}, K_{1}, A_{1}, K_{2}, A_{2}, \dots, K_{n}, A_{n})$ ，其中：
- $K_i$ 为关键字，且 $K_i < K_{i-1}$
- $A_i$ 为指向子树的根结点的指针，且指针 $A_{i-1}$ 所指向的子树中所有结点的关键字均小于 $K_i$ ， $A_n$ 所指子树中所有结点的关键字均大于 $K_n$
- n ( $\lceil m/2 \rceil - 1 \le j \le m - 1$ ) 为关键字的个数（或 n+1 为子树的个数）

2-3 树

以 B 树的一个特例：2-3树作为切入点，来看看一个B树是如何构建和操作的。

2-3树是这样的一棵多路查找树：其中的每一个结点都具有两个孩子（称为2结点）或三个孩子（称为3结点）。

2-3 树具有如下属性：

一个2结点包含一个元素和两个孩子（或没有孩子），和二叉排序树一致，左子树包含的元素小于该元素，右子树包含的元素大于该元素。但是这个2结点要么有两个孩子，要么没有孩子，不能只有一个孩子。
一个3结点包含两个元素和三个孩子（或没有孩子），左子树、较小元素、中间子树、较大元素和右子树也按照从小到大排序。一个3结点要么有三个孩子，要么没有孩子。
2-3树的所有叶子结点都在同一层次上。

一棵正确的 2-3 树如下：

插入

下面我们通过构造一棵2-3树来演示它的增删过程，假定初始数据为：{1, 7, 4, 9, 15, 13, 6, 5, 8, 10, 3, 12, 14, 2, 11}。现在树为空，要把1插入进去只需要构建一个2结点即可，如下所示：

接下来插入元素 7，只要把当前结点升级为 3 结点即可，如下所示：

接下来插入 4，发现根结点已经无法升级，只能把根结点拆开，变为 3 个 2 结点，如下所示：

插入 9 时，因为 9 比 4 大，所以插入到右侧，而 7 所在结点可以升级为3结点，所以插入结果如下所示：

接下来要插入 15，因为 9 所在结点已经是 3 结点，但是它的父结点 4 是 2 结点，所以可以把 4 所在结点升级，因为 3 结点必须有三个孩子，所以 7 和 9 所在结点需要拆分，如下所示：

接下来插入 13 和 6 时，对应节点都可以升级，所以插入结果如下：

接下来插入 5 时，发现 6 所在结点已经是 3 节点了，而父结点也是 3 结点，因此只能再次拆分。首先，5、6、7 中间的数是 6，我们把它提出来，它应该位于 4 和 9 中间，如下所示：

因为 3 结点只能有两个元素，所以根结点也必须拆分，结果如下：

可以发现，根结点拆分后使得树的高度增加了。接下来插入 8，10，3 也是重复步骤，结果如下：

至此，再插入元素 12、14、2 时也变得十分简单了，结果如下：

最后插入 11，可以发现它在 10 和 12 之间，而父结点也是 3 结点，所以 10 和 12 要拆分，9 和 13 也要拆分，11 应该和 6 一起升级为 3 结点，结果如下：

删除

现在，我们已经建立了一棵 2-3 树，我们按照插入顺序，再演示删除的过程。首先删除元素 1，因为 1 是 2 结点，删除后会影响平衡，但是我们发现它的父结点是一个 3 结点，所以可以把父结点拆开，2 和 3 合并成一个 3 结点，结果如下：

现在，要删除 7，因为 7 是叶节点也是 3 结点，直接删除就可以，结果如下：

删除结点 4，因为它的左孩子是3结点，只要把它拆开就可以了，结果如下：

删除 9 时比较复杂，因为它的左右孩子都是 2 结点，首先把它的两个孩子合并为 3 结点并代替它，结果如下：

此时树是不平衡的，此时发现左侧 3 和 6 可以合并为 3 结点，结果如下：

接下来删除15，直接删除即可。

删除 13 也比较复杂，首先需要把它的两个孩子合并，然后以 11 为根结点，做类似右旋的操作，具体做法是 6 的右孩子成为 11 的左孩子，然后 6 成为 11 的父结点，这和 AVL 树等的右旋操作是一致的，结果如下：

接下来要删除的元素 6 是根结点，做法是先找到它的前驱（第一个比它小的元素）5 代替它，此时 2、3 结点需要合并，合并后左右子树不再平衡，所以还需要5和11合并，结果如下：

其余的删除操作其实和前面的都类似，这里不再演示了，感兴趣的可以自己试一试，很快就可以发现规律。

总结

2-3 树是 B 树的一个特例，B 树就是把 2-3 树的三阶扩展到了 m，它的每个结点特性和 2-3 树一致，除叶结点外每个结点的指针域和数据域都必须填充。

B 树可以大幅地减少 I/O 操作：

以一棵阶为 1001 的B树为例，每个结点可以存储1000个数据和1001个指针，那么在高度为 2 的层上，可以存储的数据是 1001X1000 个，而它的指针数量为 1001X1001 个，这些指针可以指向的数据为 1001X1001X1000 个，大概有 10 亿条数据。
这意味着：只要我们把根结点保存在内存中，访问这 10 亿条数据最多需要两次 IO 操作，这是其他结构无法比拟的。

B 树主要是保证只有少数的磁盘访问，解决数据结构不在主存中的数据存储问题。优点显然也是它的缺点，不利于遍历。

B+ 树

B+ 树在 B 树的基础上做了改进，在 B+ 树中，出现在分支结点中的元素会被当作它们在该分支结点位置的中序后继者（叶子结点）中再次列出，且每一个叶子结点都会保存一个指向后一叶子结点的指针。如下就是一棵 B+ 树：

为了简化，叶子结点的左右两侧指针域省略。

B+ 树的特点就是任何非叶子结点都会在叶结点上再次出现一次，并且所有叶子结点从左到右链接了起来。

总体来说，它也具备B树的特性，只是在两个方面有所区别：

查找元素时，即使在非叶子结点找到了目标值，它也只是用来索引的，还需要继续找到它在叶子结点的位置。
- 非叶子结点只用于索引
如果要遍历，只需要遍历一次叶子结点
- 十分适合范围查找，只需要找到范围的最小值所在位置，然后沿链表遍历即可

对比

B 树与 B+ 树都是对磁盘友好的数据结构，能 大幅降低磁盘访问次数。

B 树的优点在于数据存储在每个结点中，可以更快访问到，而不必须走到叶子结点，B 树更多的用在文件系统中。

B+ 树的每个非叶子结点都只充当索引，所以查询必须到叶子结点结束，但它十分适合“ 扫库” 和区间查找，而且因为大多结点只用于索引，所以并不会存储真正的数据，在内存上会更紧凑，相同的内存就可以存放更多的索引数据了。

比如字典的拼音和汉字是分离的，只需要几十页就能得到完整的拼音表，但是如果拼音和汉字掺杂在一起，要得到完整的索引（拼音）表就需要整个字典。