B树、B+树、B*树

墨蓝 2022-04-10 06:36 654阅读 0赞

### 简介 ###

**[B-tree][]树即[B树][B]**，B即Balanced，平衡的意思。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是另一种树。而事实上是，**B-tree就是指的B树**。特此说明。

### 先介绍下二叉搜索树 ###

![二叉搜索树][1.JPG] 二叉搜索树

1.  所有非叶子结点至多拥有两个儿子（Left和Right）；
2.  所有结点存储一个关键字；
3.  非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；

二叉搜索树的搜索，从根结点开始，如果查询的关键字与结点的关键字相等，那么就命中；  
       否则，如果查询关键字比结点关键字小，就进入左儿子；如果比结点关键字大，就进入右儿子；如果左儿子或右儿子的指针为空，则报告找不到相应的关键字；  
       如果二叉搜索树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变二叉搜索树结构

（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数级开销；

如：

![2.JPG][]

但二叉搜索树在经过多次插入与删除后，有可能导致不同的结构：

![31.JPG][]

上图右边也是一个二叉搜索树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的树结构索引；所以，使用二叉搜索树还要考虑尽可能让B树保持左图的结构，和避免右图的结构，也就是所谓的“平衡”问题；

实际使用的二叉搜索树都是在原二叉搜索树的基础上加上平衡算法，即“平衡二叉树”；如何保持树结点分布均匀的平衡算法是平衡二叉树的关键；平衡算法是一种在二叉搜索树中插入和删除结点的策略；

### B树（B-树） ###

B树是一种平衡的多路搜索树，B树由于是多叉结构，对于元素数量非常多的情况下，树的深度不会像二叉结构那么大，可以保证查询效率。

**一颗m阶的B-树满足一下特性：**

1.  树中每个结点最多含有m个孩子（m>=2）；
2.  除根结点和叶子结点外，其它每个结点至少有ceil(m / 2)个孩子（其中ceil(x)是一个向上取整的函数）；
3.  根结点至少有2个孩子（除非B树只包含一个结点：根结点）；
4.  所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息(可以看做是外部结点或查询失败的结点，指向这些结点的指针都为null)；（注：叶子节点只是没有孩子和指向孩子的指针，这些节点也存在，也有元素。类似红黑树中，每一个NULL指针即当做叶子结点，只是没画出来而已）。
5.  每个非终端结点中包含有n个关键字信息： (n，P0，K1，P1，K2，P2，......，Kn，Pn)。其中：  
    a) Ki (i=1...n)为关键字，且关键字按顺序升序排序K(i-1)< Ki。  
    b) Pi为指向子树根的结点，且指针P(i-1)指向子树种所有结点的关键字均小于Ki，但都大于K(i-1)。  
    c) 关键字的个数n必须满足： ceil(m / 2)-1 <= n <= m-1。比如有j个孩子的非叶结点恰好有j-1个关键码。

![一颗3阶B-树][3_B-]  一颗3阶B-树![Related image][] 《数据结构（C语言版）》中的例子：一颗4阶B-树

关于

B-树的搜索，从根结点开始，对结点内的关键字（有序）序列进行二分查找，如果命中则结束，否则进入查询关键字所属范围的儿子结点；重复，直到所对应的儿子指针为空，或已经是叶子结点；

其最低搜索性能为：

![0.JPG][]

其中，M为设定的非叶子结点最多子树个数，N为关键字总数；  
       所以B-树的性能总是等价于二分查找（与M值无关），也就没有B树平衡的问题；  
       由于M/2的限制，在插入结点时，如果结点已满，需要将结点分裂为两个各占M/2的结点；  
       删除结点时，需将两个不足M/2的兄弟结点合并；

### **B+树** ###

B+树是B-树的变体，也是一种平衡的多路搜索树。

一颗m阶的B+树和m阶的B-树的差异在于：

1.  非叶子结点的子树个数与关键字个数相同
2.  所有叶子节点包含全部关键字信息，及指向含有这些关键字记录的指针，且叶子节点中关键字进行有序链接
3.  非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）对应的data数据的数据层，非叶子节点中含有其子树中最大关键字。
4.  B+树非叶子节点不存储data数据，而B-树相反，每个非叶子节点都会存储Data数据

![一颗3阶B+树][3_B] 一颗3阶B+树![1343448307_6771.jpg][] 《数据结构（C语言版）》中的例子：一颗3阶B+树

B+的搜索与B-树也基本相同。因为上文提到的B+树和B-树的第4个差异点，所以B+树只有达到叶子结点才命中（B-树可以在非叶子结点命中），其性能也等价于在关键字全集做一次二分查找；

B+的总结：

1.  所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；
2.  不可能在非叶子结点命中；
3.  非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）对应数据的数据层；
4.  更适合文件索引系统；

### **B\*树** ###

B\*是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

![6.JPG][]

B\*树定义了非叶子结点关键字个数至少为(2/3)\*M，即块的最低使用率为2/3（代替B+树的1/2）；

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

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

所以，B\*树分配新结点的概率比B+树要低，空间使用率更高；

### **小结** ###

*  二叉搜索树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；
 *   B（B-）树：平衡的多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；
 *   B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字对应的Data数据都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；
 *   B\*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；

### 为什么Mysql用B+树做索引而不用B-树 ###

先从数据结构的角度来答。B-树和B+树最重要的一个区别就是B+树只有叶节点存放数据，其余节点用来索引，而B-树是每个索引节点都会有data域。这就决定了B+树更适合用来存储外部数据，也就是所谓的磁盘数据。

从Mysql（InooDB）的角度来看，B+树是用来充当索引的，一般来说索引非常大，尤其是关系性数据库这种数据量大的索引能达到亿级别，所以为了减少内存的占用，索引也会被存储在磁盘上。

那么Mysql如何衡量查询效率呢？磁盘IO次数，B-树（B树）的特点就是每层节点数目非常多，层数很少，目的就是为了就少磁盘IO次数，当查询数据的时候，最好的情况就是很快找到目标索引，然后读取数据，使用B+树就能很好的完成这个目的，但是B-树的每个节点都有data域（指针），这无疑增大了节点大小，说白了增加了磁盘IO次数（磁盘IO一次读出的数据量大小是固定的，单个数据变大，每次读出的就少，IO次数增多，一次IO多耗时啊！），而B+树除了叶子节点其它节点并不存储数据，节点小，磁盘IO次数就少。这是优点之一。

另一个优点是什么，B+树所有的data域在叶子节点，一般来说都会进行一个优化，就是将所有的叶子节点用指针串起来。这样遍历叶子节点就能获得全部数据，这样就能进行区间访问啦。

B+树不仅减少了磁盘IO次数，而且只要遍历叶子节点就可以实现整棵树的遍历。在数据库中基于范围的查询是非常频繁的，而B树（B-树）不支持这样的操作（或者说效率太低）)

那MongoDB为什么使用B-树而不是B+树，可以从它的设计角度来考虑，它并不是传统的关系性数据库，而是以JSON格式作为存储的nosql，目的就是高性能，高可用，易扩展。首先它摆脱了关系模型，Mysql由于使用B+树，数据都在叶节点上，每次查询都需要访问到叶节点，而MongoDB使用B-树，所有节点都有data域，只要找到指定索引就可以进行访问，无疑单次查询平均快于Mysql（但侧面来看Mysql至少平均查询耗时差不多）。

总体来说，Mysql选用B+树和MongoDB选用B-树还是以自己的需求来选择的。

[B-tree]: https://baike.baidu.com/item/B-tree/6606402
[B]: https://baike.baidu.com/item/B%E6%A0%91/5411672
[1.JPG]: /images/20220402/ca05384056804061bdadff7c0e7c36c2.png
[2.JPG]: /images/20220402/cfe1f24cdbe44606958eb52f126e2953.png
[31.JPG]: /images/20220402/97dc698ae2b94fc19e47297136b08a02.png
[3_B-]: https://p-blog.csdn.net/images/p_blog_csdn_net/manesking/4.JPG
[Related image]: https://img-my.csdn.net/uploads/201207/28/1343441845_4081.jpg
[0.JPG]: /images/20220402/35e97c7e5c7a40baa713780485997a5d.png
[3_B]: https://p-blog.csdn.net/images/p_blog_csdn_net/manesking/5.JPG
[1343448307_6771.jpg]: https://img-my.csdn.net/uploads/201207/28/1343448307_6771.jpg
[6.JPG]: /images/20220402/1699b830de034be98e2bb8bbd057fc41.png