前面的文章，我们已经介绍过其他的几种高级的动态数据结构，典型如红黑树，跳跃表等，今天我们再来学习另外一种高级数据结构B树，我们知道树的查询时间复杂度和其树的高度有直接关系，当我们向红黑树里面插入大量的数据时，有两个问题：

（1）首先，内存是有限的不可能无止境的一直插入数据，而基于BST的平衡树如AVL树和红黑树，或者我们上一节学习的跳跃表本质上都是基于内存的数据结构。

（2）如果将AVL树，红黑树或者跳跃表直接存储到磁盘上，然后用来检索可以吗？ 答案是可以的，但问题是基于磁盘寻道查询比基于内存慢太多了，举个例子，假设现在有100万数据分布在红黑树里面，按照红黑树的平均查找性能O（logN）来计算，在N=100万时，检索任意数据平均需要20次查询，如果是在内存完全没问题，但此时红黑树是如果存在磁盘上，那就完全不一样了，按照普通硬盘或者文件系统，每次查询IO一次总耗时约10毫秒计算，那么在百万级别的数据量下，检索一次数据就需要10*20，大概就是0.2秒，假如现在数据量扩大100倍，数据总量是一亿，那么检索一次数据就需要20秒，这个性能是完全不能接受的，可以想象在这种情况下，使用二叉树是不合适的。

正是由于描述的问题，所以迫切需要一种面向磁盘或者文件系统友好的数据结构，而它就是B树，或者基于B树的扩展B+，B*树等。上面问题的根源在于树的高度太高，导致查询外存，也就是访问磁盘IO次数太多，从而大大拖慢了检索性能，那么思路就清晰了，只要想法子降低树的高度就可以了，没错B树就是这么一种m叉的多路平衡树，你可以想象它的孩子节点少则2个，多则数千个，所以就从二叉树的廋高，变成了多叉树的矮胖，正是这样才大大降低了树的高度，从而使得这种数据结构更适合存储在磁盘上，并且充分了利用了磁盘的块的预读机制（局部性访问原理），通过缓存的方式进一步提升性能，磁盘在读取某一个文件指针的时候，通常会把紧挨着的数据，也全部读到缓存，因为实践证明，当一个文件数据被访问的时候，它周边的数据很快也会被访问，这里简单说下磁盘扇区，磁盘块，磁盘也的区别：

扇区：磁盘的最小存储单位；

磁盘块：文件系统读写数据的最小单位；

页：内存的最小存储单位；

磁盘块和页的大小一般情况下为4KB，所以在B树中一个节点的最大存储数据个数的总大小一般不能超过4KB。

基于B树的结构充分利用了这一点，从而非常适合做文件系统或者数据库的索引。

假如当前有一颗m阶的B树（注意阶的意思是指每个节点的孩子节点的个数），那么其符合：

（1）每个节点最多有m个子节点

（2）除了根节点和叶子节点之外，其他的每个节点最少有m/2（向上取整）个孩子节点

（3）根节点至少有两个孩子节点，（除了第一次插入的时候，此时只有一个节点，根节点同时是叶子节点）

（4）所有的叶子节点都在同一层

（5）有k个子节点的父节点包含k-1个关键码

除了上面B树的性质外，B树还有几个特点：

1，树高平衡，所有的叶节点都在同一层

2，关键码没有重复，父节点中的关键码是其子节点的分解

3，B树把值接近的相关记录放在同一个磁盘页中，从而利用了访问的局部性原理。

4，B树保证树种至少有一部分比例的节点是满的。为什么这样说，在上面的性质2中，我们知道每个节点最少可以有 m/2个节点，注意这刚好是一半，没有太满，是因为可以给后续的添加，删除留有余地，这样以来节点不会频繁的触发不平衡，没有太空则意味着B树能够 保证降低树的高度。

如下图的一个2-3树的示例

这个例子里面m=3，那么每个节点的孩子节点个数最多是3个节点，最少是2个节点（3/2向上取整），所以关键码的范围就是1-2，这一点需要注意，这是限制B树平衡的一个条件之一，另外一个是所有的叶节点都等高。注意在实际实现过程中，B树的每个关键码都会有两个指针，一个指针指向该关键码本身的记录在磁盘上的偏移量，另一个指针指向其子树的节点在磁盘上的位置，而B+树里面则没有存储该关键码本身的记录在磁盘上的偏移量，所以理论上来说同样的数量，B+树的节点能够比B树存储更多的关键码。

从上面我们看出来一个特点，包含i个关键码的节点，它的子节点个数（也叫子树）有i+1个，注意这里存的是指针，此外关键码的值规律是： k1 < k2 k3

B树的查询与二叉树的搜索基本类似，在高度为h的B树，最多的查询次数就该树的高度，B树查询分为交替执行的两步过程：

（插入案例一） 插入找位置的过程与搜索类似，默认我们认为不支持存储重复的关键码，插入分几种情况，如下图所示，在这样一个2-3树（最大阶=3，最小阶=2，最大关键码=2，最小关键码是1）里面插入14，如下图：

我们可以直接将这个节点放在15左侧即可，其他不需要做任何改动，这就是前面我们说的，B树的节点默认只会使用50%的存储个数，这样不至于太满导致每插入一次就得维持平衡，同时也不至于太空，能够有效的降级树的高度。比如上的14插入后，插入节点没有违背B树的各个性质，所以本次效率比较高。

（插入案例二）

如下图，插入55，就破坏了B树的性质，2-3树的关键码只能是1或者2，但插入55后，就变成3了，这种情况解决方案是，对插入后序列取中位数，然后上升到父节点即可： 插入前：

插入后：

（插入案例三）

多个节点连续分裂的情况，如上图此时如果再插入19，就会形成级联分裂3级，如下：

注意如果根节点再分裂，就会新生成一个根节点，从而最终导致树的高度增加一级，如下：

注意这里可以思考一个问题，为什么B树的根节点阶是2到m，而不是其他非叶子节点的m/2 到 m，这其实从分裂过程就能看出来，因为在根节点在关键码多于2的时候分裂，分裂到最终的情况下就是从3个关键码中分裂，这样必然会新提取一个中间节点做根节点，然后剩下的两个节点充当孩子节点，所以B树的根节点是特殊的，它的限制和其他非叶子节点是不一样的。

下面我们总结下B树插入的流程：

首先最重要的是要保持B树的性质，特别是等高和阶的限制。

（1）查找插入节点的位置，找到最底层插入。

（2）若新增一个关键码后导致溢出，则节点分裂，中间关键码连同新指针插入父节点

（3）若父节点也溢出，则继续分裂，回到步骤2

（4）分裂过程中可能会传达到根节点，从而导致树升高一层

注意从磁盘已经加载过数据，默认我们认为已经缓存了，当再次读取的时候不会再访问磁盘。

删除相比插入要复杂的多，与二叉树的删除类似，如果删除的关键码不在叶节点层，先把此关键码与它在B树里的后继节点调换位置（这个与二叉树类似，可以选择左子树最大，或者右子树最小），然后再删除该关键码。

如果删除的关键码在叶节点层，删除后关键码个数不小于m/2-1，因为小于m/2，则意味着下溢出，在前面的插入过程中，会造成上溢出，注意这两种情况。如果不小于m/2，则直接删除。

如果关键码的个数小于m/2，如果兄弟节点的关键码个数不等于m/2-1，则执行借操作，从兄弟节点中移出若干个关键码到该节点中来（父节点中的一个关键码要做相应变化）

如果兄弟节点的关键码个数等于m/2-1,那么就执行合并。

如下图：

首先6阶B树子节点数限制是3-6，所以关键码的限制是2-5，在上图中删除45会出现下溢出，即破坏了性质，所以要从兄弟节点看看能不能借数据保持性质，这里的兄弟节点一般都是紧邻的左右，不会再远，上图中上面的节点也就是左兄弟的关键码刚好是2，所以不能借，而右边的兄弟关键码是3，所以可以借一个，但借是有规则的，不能直接拿过来，需要把父节点的中间码给拉下来，重新选举一个父节点，并基于父节点做分裂。如下图：

接着我们继续删除，会发现左右兄弟都不能再借了，如下图：

这个时候，要考虑合并了，可以是跟左也可以是跟右，但注意合并同样需要把父节点的关键码拉下来合并，最终结果如下：

下面我们总结下B树删除的流程：

首先最重要的还是保持性质：叶子等高和阶的上下界。

总得来说有4步：交换，删除，借关键码，合并

（1）保证所删除的位置在最底层（否则与后继关键码交换）

（2）若删除后，节点中关键码数目不够最低限（下溢出），则先看左右兄弟有无多于的关键码可借，若有则拉下父节点的分界码，与兄弟节点进行重新分割，与插入类似。

（3）若其左右兄弟中的关键码都处在下限处，则把节点和它的一个兄弟，以及父节点他两的分界关键码一起合并成一个节点，注意这个时候父节点下拉的关键码，就从父节点里面删除了。

（4）此合并过程如果传递到根节点，则树的高度下降一层。

B树相信大家已经熟悉了，还有两种B树的延伸分别是B+树和B树，类B树系的结构主要是面向磁盘文件系统数据结构，但B树的不足也显而易见，在B树里面所有的节点都存储数据，这样导致在做范围查询的时候，性能比较低，所以才出现了B+树，B+树里面每个节点存储的关键码个数相比B树存的更多，另外B+树非叶子节点不存储数据，只存储索引，索引B+树可以很好的支持范围查询，而B树与B+树主要的区别在于B树更加饱满，前面说过B+树的孩子节点个数是保持在50%的饱满程度，而B树是保持在75%的饱满程度，当然这种设计会导致算法更加复杂，有利也有弊，在实际应用中并不常见。由于B树的不足，所以B+树才是在面向文件系统索引里面最流行的数据结构。同样的对应B+树在内存里面的数据结构就是跳跃表，但跳跃表的虽然支持范围查询，但平均时间复杂度是O（logN），对于磁盘访问来说还是比较耗时的。

本篇文章主要介绍了B树相关内容，B树是面向磁盘的索引结构，B+树是基于B树的扩展，更好的支持了范围检索，常应用在主流的数据库中如MySQL，Oracle等，对B树的学习和理解是掌握数据库索引原理必须不少的基础，感兴趣的同学可以自己再去研究下。