B树和B+树的详解讲解

左手的ㄟ右手 2024-03-30 11:18 54阅读 0赞

## 1.B树 ##

前面我们已经学习了[二叉查找树][Link 1]、2-3树以及它的实现[红黑树][Link 2]。2-3树中，一个结点做多能有两个key，它的实现红黑树中使用对链接染色的方式去表达这两个key。接下来我们学习另外一种树型结构B树，这种数据结构中，一个结点允许多于两个key的存在。  
**B树是一种树状数据结构，它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。**

### 2.1 特性 ###

> B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：  
> 每个结点最多有M-1个key，并且以升序排列；  
> 每个结点最多能有M个子结点；  
> 根结点至少有两个子结点；

![在这里插入图片描述][8e581070cade4eaab66af563f683e491.png]

### 2.2 存储数据 ###

若参数M选择为5，那么每个结点最多包含4个键值对，我们以5阶B树为例，看看B树的数据存储。  
![在这里插入图片描述][0a88bb0234fe41ccbb8022b6a1ac86cf.png]

### 2.3 B树的应用 ###

在我们的程序中，不可避免的需要通过IO操作文件，而我们的文件是存储在磁盘上的。计算机操作磁盘上的文件是通过文件系统进行操作的，在文件系统中就使用到了B树这种数据结构。

## 2.B+树 ##

### 2.1 B+树和B树区别 ###

**B+树是对B树的一种变形树，它与B树的差异在于：**

1.  非叶结点仅具有索引作用，也就是说，非叶子结点只存储key，不存储value；
2.  树的所有叶结点构成一个有序链表，可以按照key排序的次序遍历全部数据。

### 2.2 B+树存储数据 ###

若参数M选择为5，那么每个结点最多包含4个键值对，我们以5阶B+树为例，看看B+树的数据存储。  
![在这里插入图片描述][4098970af61d430b9bea1777b888ffb1.png]

### 2.3 B+树和B树的对比 ###

**B+ 树的优点在于：**  
1.由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够存放更多的key。 2.B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。  
**B树的优点在于：**  
由于B树的每一个节点都包含key和value，因此我们根据key查找value时，只需要找到key所在的位置，就能找到value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶子结点的深度，才能找到value。

### 2.4B+树的应用 ###

应用在数据库中。  
在数据库的操作中，查询操作可以说是最频繁的一种操作，因此在设计数据库时，必须要考虑到查询的效率问题，在很多数据库中，都是用到了B+树来提高查询的效率；在操作数据库时，我们为了提高查询效率，可以基于某张表的某个字段建立索引，就可以提高查询效率，那其实这个索引就是B+树这种数据结构实现的。  
例：

> 执行select \* from user where id>=12 and id<=18 ,如果有了索引，由于B+树的叶子结点形成了一个有序链表，  
> 所以我们只需要找到id为12的叶子结点，按照遍历链表的方式顺序往后查即可，效率非常高。  
> ![在这里插入图片描述][9865b1a5e1a24c15b05b23f62ca85616.png]

参考：黑马程序员Java数据结构与java算法

[Link 1]: https://blog.csdn.net/weixin_45428910/article/details/128403857?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22128403857%22,%22source%22:%22weixin_45428910%22%7D
[Link 2]: https://blog.csdn.net/weixin_45428910/article/details/128403872?csdn_share_tail=%7B%22type%22:%22blog%22,%22rType%22:%22article%22,%22rId%22:%22128403872%22,%22source%22:%22weixin_45428910%22%7D
[8e581070cade4eaab66af563f683e491.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/792de47815a541378324bf00d523612f.png
[0a88bb0234fe41ccbb8022b6a1ac86cf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/8594a49198f645b5b45aa5412a821399.png
[4098970af61d430b9bea1777b888ffb1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/c76000b794b84f939db5b95086083bb4.png
[9865b1a5e1a24c15b05b23f62ca85616.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/7468b7d4e33e4453bfd4a718d70b64a1.png