什么是B+树，这下懂了... | 干货分享

 

 

 

 

B+树是很基础的概念，也是面试里面的常考题，一定要掌握。今天我们就来聊聊这个话题。

要弄明白B+数，首先要了解B-树

B-树就是B树，中间的横线不是减号。千万别念成：B减树，那就丢人现眼了

 

 

既然这样，为什么索引不直接使用二叉树来实现呢？二叉树的查询复杂度是O(logN)，性能已经足够高，难道B-树可以更快？

其实从算法上进，二叉树确实可以。但是，我们不得不考虑一个现实问题：

 

数据库索引是存储在磁盘上的，当数据量比较大时，索引的大小可能有几个G，甚至更多。

当我们利用索引查询时，不可能把索引全部加载到内存里。只能逐一加载每一个磁盘页。这里的磁盘页对应着索引树的节点。

 

如果我们使用二叉树，会怎么样呢？假设树的高度是4，要查找的值是10，那么流程如下：

 

第1次磁盘IO：

 

第2次磁盘IO：

 

第3次磁盘IO：

 

第4次磁盘IO：

 

我们可以看到：磁盘的IO次数，是由树的高度决定的

既然如此，为了减少磁盘IO次数，我们就需要把原本“瘦高”的树，变得“矮胖”一些，这就是B-树。

 

B树是一种多路平衡查找树，它的一个节点最多包含K个孩子，K称为树的阶。这里，K的大小取决于磁盘页的大小。

下面具体介绍一下B-树（Balance Tree），一个K阶的B-树具有以下几个特征：

（1）根结点至少有两个孩子。

（2）每个中间节点都包含m-1个元素和m个孩子，其中 k/2 <= m <= k

（3）每一个叶子节点都包含m-1个元素，其中 k/2 <= m <= k

（4）所有的叶子结点都位于同一层。

（5）每个节点中的元素从小到大排列，节点当中m-1个元素正好是m个孩子包含的元素的值域分划。

 

我们以一个3阶的B-数为例，来看一下B-树的具体结构。树中的具体元素和刚才的二叉树一样。

 

我们重点看一下（2, 6）这个节点。该节点有2和6两个元素。又有3个孩子：1，（3, 5）和8。其中 1 < 2，（3, 5）在2, 6之间，8大于（3, 5）。刚好符合上面的几条特征。

 

 

假设要查询的值是5：

第1次磁盘IO：

 

在内存中定位（和9比较）：

 

第2次磁盘IO：

 

在内存中定位（和2，6比较）：

 

第3次磁盘IO：

 

在内存中定位（和3，5比较）：

 

可以看出，B-树在查找中的比较次数其实不比二叉数少，尤其是当单一节点中的元素数量很多时。但是，相对比磁盘IO的速度，内存的比较耗时可以忽略不计。所以，只要数的高度足够低，IO次数足够少，就可以提高查找性能！

至于节点内部的元素数量，多一点无非是多几次内存计算，只要不超过磁盘页大小就可以。这就是B-树最核心的思想！

 

 

B-树主要应用于文件系统，另外非关系型数据库MongoDB，就使用了B-树来做索引。

而大部分关系型数据库，比如MySQL，则使用B+树来做索引，关于B+树，我们明天接着聊！