五分钟搞懂什么是B-树（全程图解）

我们大家都知道动态查找树能够提高查找效率，比如：二叉查找树，平衡二叉查找树，红黑树。他们查找效率的时间复杂度O(log2n)，跟树的深度有关系，那么怎么样才能提高效率呢？当然最快捷的方式就是减少树的深度了。那么怎么减少树的深度呢？为了解答这个问题，我们慢慢来看，先看个实际问题吧。

问题背景

在大型的数据库存储中，实现索引查找，如果采用二叉查找树的查找的话，由于节点的存储数据是有限的（不可能将节点存储过多的数据，否则就变成线性的查找了），这样如果数据量很大的，就会导致树的深度过大从而造成磁盘IO操作过于频繁（你们知道磁盘IO操作是非常耗时的），就会导致效率非常低下。可能有童鞋会问了，那为什么不把节点索引加载到内存中，这样访问不就快了吗？其实这显然是不可能完成的，因为往往存储的索引可能就有好几个G了。全部加载到内存也是不现实的。能做的只有逐一加载每一个磁盘页，这里的磁盘页就相当于索引树的节点。

那怎么解决呢？就回到了前面的那个问题，可以减少树的深度。其中基本思想是：采用多叉树结构。也就是说，因为磁盘的操作费时费资源，如果过于频繁的多次查找势必效率低下。那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，那么是不是便能有效减少磁盘查找存取的次数呢？那这种有效的树结构是一种怎样的树呢？

根据平衡二叉树的启发，自然就想到了平衡多路查找树结构。也就是本文的主题B-tree，好了废话不多说了，进入正题！

B-tree的简介

B-树就是我们平常说的B树，不要读成B减树了，它在文件系统中很有用（原因之前已经介绍了），我们先来看下一个m阶的Bs树具有如下几个特性：

根节点至少有两个子女
每个中间节点都包含k-1个元素和k个孩子，其中m/2<=k<=m
每个叶子节点都包含k-1元素，其中m/2<=k<=m
所有的叶子节点都位于同一层
每个节点的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

看起来是不是很复杂，没看懂也没有关系，我们用实际例子来演示下。例子来源网络，参考：https://blog.csdn.net/qq_35644234/article/details/66969238

B-树插入

一个原始的B-树阶为3，如下图：

aHR0cDovL3AxLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MzMyNTM2NTk3OTQyMjU4YzQ2NDU5

首先，我需要插入一个关键字：30，可以得到如下的结果：

aHR0cDovL3AxLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MzMyNTM2ODQ0ODFiZDU2MDBhOWIz

再插入26，得到如下的结果：

aHR0cDovL3AzLnBzdGF0cC5jb20vbGFyZ2UvcGdjLWltYWdlLzE1MzMyNTM3MTA0MjdiYzE4ZjE3NmVj

OK，此时如图所示，在插入的那个终端结点中，它的关键字数已经超过了m-1=2，所以我们需要对结点进分裂，所以我们先对关键字排序，得到：26 30 37 ，所以它的左部分为（不包括中间值）：26，中间值为：30，右部为：37，左部放在原来的结点，右部放入新的结点，而中间值则插入到父结点，并且父结点会产生一个新的指针，指向新的结点的位置，如下图所示：