B树的进化版----B+树

C++为什么叫C plus plus？
这是由于C++相当于继承C的语法后，增加了各方面的能力，所扩展出的一种新语法。
在软件领域中 plus 有增加的味道。在这里B +树也一样,是B树的增强版。
在学习B+树之前，最好是对B树有一定的了解。不了解的各位也没有关系，可以花费5分钟的时间读我的上一篇文章《数据库索引的基石----B树》。
我在上篇文章的最后，专门提到，由于B树的设计，导致它存在一种天然的劣势，导致典型的B树在很多方面受到了限制。
这个劣势是什么呢？（自问）
先想下，为啥我们在类磁盘的数据查找系统中，并没有使用高效的平衡二叉查找树，而设计出了B树?这是由于B树是考虑到了加载硬盘数据到内存是系统瓶颈，所以让节点变重，承载更多的关键字。但是B树在设计时，为了查找方便，节点信息除了包含关键字，还包含了data信息，这就导致每个节点所能包含的最大关键字个数被压缩了。(防盗连接：本文首发自http://www.cnblogs.com/jilodream/ )这就导致最终并没有达到每次次加载，加载的关键字是最大数目的最优方案。（自答）
基于这个原因，有人对B树进行了改良，提出了B+树（B plus tree）。
也就是下边这个样子

根据B+树的图，我们可以轻易总结出以下几个不同点：
1、在B+树中，如果一个节点包含n个关键字，那么他就有n个分支。
在B树中，含有n个关键字的节点有n+1个分支。
也就是说B+树是一个关键字对应一个分支，B树是一个关键字的空位置对应一个分支。
2、 B+树中节点的关键字个数范围比对应的B树多1。
3、 B+树的叶子节点包含全部关键字，叶子节点的指针指向关键字对应的数据。
4、 B+树的所有非叶子节点仅仅起到一个索引的作用，即节点中的每个索引项只含有对应子树的最大关键字和指向该子树的指针。不含有该关键字的所对应的数据。
在B树中，每个节点还会额外记录关键字所对应的数据。
5、 B+树中存在一个额外的指针，这个指针指向于包含最小关键字的节点。然后所有的叶子节点从小到大的串联起来，形成一个线性的链表。
最主要的不同点是4、5两点，这里着重解释下第4点：
父节点中关键字的位置是其子节点中所有的关键字中的最大值。
如图中62是子节点（56，62）的最大值96是子节点（62，78，96）的最大值。
96存在于三个节点中，但是它对应的数据只存储在叶子节点中。
而B树如果是相同数据的话，96只会存在一个节点中，而这个节点直接就包含了96对应的数据。
正是由于第4点导致了B+树的查找，系统每次可以从磁盘中加载的数据量更大，调用的IO耗时更少。
而由于第5点的存在，导致B+树在范围查找等方面有了极大的优势。
下边结合上边的B+树，我们来举几个例子：
（1）查找15
首先加载根节点（50，96），依次比较，发现15≤ 50，匹配成功。
加载50对应的子节点（15，50）。依次比较，发现15=15，匹配成功。
加载15对应的子节点（3，8，15）。依次比较，发现15=15，匹配成功。
由于（3，8，15）是叶子节点，所以可以直接取出对应数据。

（2）查找14
前边都相同，直至加载叶子节点（3，8，15）。
依次比较3，8，不匹配，比较15，发现14<15，并且当前节点是叶子节点，所以匹配失败，B+树不包含14关键字。

（3）查找满足14≤x≤57条件的所有x
同（2）场景，发现14不存在，15是满足条件的最小值，存储15。
加载下一个叶子节点（20，26，27，50），依次比较发现都满足，全部存储。
加载下一个叶子节点（56，62），依次比较发现56满足条件，62超出范围，存储56。
最终得出满足条件的所有数据是{15，20，26，27，50，56}。

由于B+树的种种优势，使得其被广泛应用于各种文件查找系统中，如mysql、MongoDB。在mysql中，你在建立索引所选取的B树，底层的实现正式B+树。另外MongoDB在官方文档中描述，索引使用B树，于是很多文章甚至面试官就想当然的提问，为什么MongoDB没使用B+树，而是使用的B树。其实作者曾经就已作出澄清，底层的实现使用的是B+树。(防盗连接：本文首发自http://www.cnblogs.com/jilodream/ )而文档写为B树，我们可以理解为B+树是B树的一个增强版。（此处可参考https://q.cnblogs.com/q/127244/）所以当有人问你，为什么mysql使用B+树，而MongoDB使用B树时，你可以给他一个惊喜。

巴特西

B树的进化版----B+树

最新文章

热门文章