一、概念

1. Binary Tree（二叉树）：二叉树的每个节点最多有两个子节点
2. Binary Search Tree（二叉搜索树）：二叉搜索树每个节点只存储一个键值，并且左子树（如果有）所有节点的值都要小于根节点的值，右子树（如果有）所有节点的值都要大于根节点的值。
3. B-Tree（Balanced Tree）：也就是今天要说的B-树，这里的-不是minus的意思，而是作为连接符的横杠，而我们也经常把B-树直接翻译为B树，所以B树与B-树通常是指一个概念，B代表的是Balance，而不是Binary。而B+树和B*树则是B-树的基础上正对不同场景的优化版本，将会在后文中有所介绍。

在大规模数据存储中，二叉查找树的深度会过大，当内存无法存储所有节点数据时，需要读取磁盘，进行IO操作，从而树的高度越高，I/O操作次数越多，效率也就越低。所以诸如之前所讲的红黑树，AVL树 因为树的高度太高而不适合这种需要大量IO操作的查询。所以，B树通过多叉的实现来降低树的高度，从而减少IO操作的次数。

二、B树（B-树）

为方便描述，下面一律用B树这个名称。B树是一种多路平衡搜索树（非二叉），若其是M路，则：

1. 任意非叶子节点最多可以有M个子女，且M>2；
2. 根节点的子女数为[2,M]；
3. 除了根节点以外的非叶子节点的子女数目为M/2（取上整）个到M个；
4. 每个节点存放至少M/2-1（取上整）和至多M-1个键值（至少两个）；
5. 非叶子节点的关键字个数=指向子女的指针个数-1；
6. 非叶子节点的关键字K[1],K[2],…,K[M-1]且有K[i]<K[i+1]；
7. 非叶子节点的指针P[1],P[2],…,P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其他P[i]指向关键字属于(K[i-1],K[i])的子树；
8. 所有叶子节点都位于同一层。

B树与二叉搜索树的最大区别在于其每个节点可以存不止一个键值，并且其子女不止两个，不过还是需要满足键值数=子女数-1。因此，对于相同数量的键值，B树比二叉搜索树要更加矮一些，特别是当M较大时，树高会更低。

上图中是一个简单的B树，在实际应用中，M可以取到很大，比如大于1000。一般情况下M的取值会使得每个磁盘盘块可以正好存放一个B数节点。上图中的35节点，35是一个key（或者说是索引，比如磁盘文件的文件名），而小黑块则代表的是该key所指向的内容在磁盘中实际的存储位置，是一个指针（比如35这个文件在硬盘中的位置）。

B树的搜索

B树的搜索与二叉搜索树类似，只不过需要在节点内部进行一次搜索查找。从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

B树的插入

B树的插入首先查找插入所在的节点，若该节点未满，插入即可，若该节点以及满了，则需要将该节点分裂，并将该节点的中间的元素移动到父节点上，若父节点未满，则结束，若父节点也满了，则需要继续分裂父节点，如此不断向上，直到根节点，如果根节点也满了，则分裂根节点，从而树的高度+1。

下面是B树插入的一个演示动画，往B树中一次插入的元素为6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4。

B树的删除

B树的删除首先要找到删除的节点，并删除节点中的元素，如果删除的元素有左右孩子，则上移左孩子最右节点或右孩子最左节点到父节点，若没有左右孩子，则直接删除。删除后，若某节点中元素数目不符合B树要求（小于M/2-1取上整），则需要看起相邻的兄弟节点是否有多余的元素，若有，则可以向父节点借一个元素，然后将最丰满的相邻兄弟结点中上移最后或最前一个元素到父节点中（有点类似于左旋）。若其相邻兄弟节点没有多余的元素，则与其兄弟节点合并成一个节点，此时也需要将父节点中的一个元素一起合并。

三、B+树

B+树是B树的一个变种，其也是一种多路平衡搜索树，其与B树的主要区别是：

1. 非叶子节点的指针数量与关键字数量相等；
2. 非叶子节点的子树指针P[i]，指向关键字值属于[K[i],K[i+1]）的子树（B树是开区间，B+树是左闭右开，也就是说B树不允许关键字重复，而B+树允许）；
3. 所有关键字都在叶子节点出现，所有的叶子节点增加了一个链指针（稠密索引，且链表中的关键字切好是有序的）；
4. 非叶子节点相当于是叶子节点的索引（稀疏索引），叶子节点相当于是存储数据的数据层。

B+树主要是应文件系统所需而产生的。文件系统中，文件的目录是一级一级索引，只有最底层的叶子节点（文件）保存数据。非叶子节点只保存索引，不保存实际的数据，数据都保存在叶子节点中，所有的非叶子节点都可以看成是索引部分。

非叶子节点（比如[5，28，65]）只是一个key（索引，实际的数据在叶子节点上，对应于叶子节点[5,8,9]中的5，[28,30,33]中的28，[65,73,79]中的65才是真正的数据或指向真实数据的指针）。

B+树的搜索

B+的搜索与B树也是基本相同的。唯一的区别是B+树只有达到叶子结点才命中，因为只有叶节点中存放着真实数据或真实数据的指正，而B树可以在非叶子结点命中，其性能也等价于在元素全集做一次二分查找。

B+树的插入

B+树的插入与B树类似，如果节点中有多余的空间放入元素，则直接插入即可。如果节点本来就已经满了，则将其分裂为两个节点，并将其中间元素的索引放入到父节点中，在这里如果是叶子节点的话，是拷贝中间元素的索引到父节点中（因为叶子节点需要包含所有的元素），而如果是非叶子节点，则是上移节点的中间元素到父节点中。

下面是B+树插入的一个演示动画：

B+树的删除

在叶节点中删除元素，如果节点还满足B+树的要求，则okay。如果元素个数过少，并且其邻近兄弟节点有多余的元素，则从邻近兄弟节点中借一个元素，并修改父节点中的索引使其满足新的划分。如果其邻近兄弟节点也没有多余的元素，则将其和邻近兄弟节点合并，并且我们需要修改其父节点的索引以满足新的划分。并且如果父节点的索引元素太少不满足要求，则需要继续看起兄弟节点是否多余，如果没有多余则还需要与兄弟节点合并，如此不断向上，直到根节点。如果根节点中元素也被删除，则把根节点删除，并由合并来的节点作为新的根节点，树的高度减1。

四、B+树与B树的比较

B+树的非叶子节点并没有指向关键字具体信息的指针，因此其内部节点相对B树更小，如果把所有同一内部节点的关键字存放在同一盘块中，盘块所能容纳的关键字数量也越多，具有更好的空间局部性，一次性读入内存的需要查找的关键字也越多，相对的IO读写次数也就降低了。

另外对于B+树来说，因为非叶子节点只是叶子节点中关键字的索引，所以任何关键字的查找都必须走一条从根节点到叶子节点的路，所有关键字查询的路径长度相同。而若经常访问的元素离根节点很近，则B树访问更迅速，因为其不一定要到叶子节点。

数据库索引采用B+树的主要原因是B树在提高了IO性能的同时并没有解决元素遍历效率低下的问题，而也正是为了解决该问题，B+树应运而生。因为叶子节点中增加了一个链指针，B+树只需要取遍历叶子节点可以实现整棵树的遍历。而且数据库中基于范围的查询是非常频繁的，B树对基于范围的查询效率太低。

五、B*树

B*树又是B+树的变种，其与B+树的区别有：

1. B*树在B+树的非根和非叶子节点再增加指向兄弟节点的指针
2. B树规定非叶子节点的键值个数至少为(2/3)M，这样每个节点的使用率就从B+树的1/2上升到2/3，所以空间使用率更高。

B树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；B树分配新结点的概率比B+树要低，空间使用率更高；