java八股文面试[数据库]——B树和B+树的区别

ゝ一纸荒年。 2024-03-24 23:49 82阅读 0赞

![d7a8c748068e46ffa3f6448026fe5fb4.png][]

B树是一种树状数据结构，它能够存储数据、对其进行排序并允许以**O(logn)**的时间复杂度进行查找、顺序读取、插入和删除等操作。

### **1、B树的特性** ###

B树中允许一个结点中包含多个key，可以是3个、4个、5个甚至更多，并不确定，需要看具体的实现。现在我们选 择一个参数M，来构造一个B树，我们可以把它称作是M阶的B树，那么该树会具有如下特点：

*  每个结点最多有**M-1个key**，并且以升序排列；
 *  每个结点最多能有**M个子结点**；
 *  根结点至少有两个子结点；

![c6d1f8164c2dbd8533f3bc326318c290.png][]

在实际应用中B树的阶数一般都比较大（通常大于100），所以，即使存储大量的数据，B树的高度仍然比较小，这 样在某些应用场景下，就可以体现出它的优势。

### **2、B树存储数据** ###

若参数M选择为5，那么每个结点最多包含4个键值对，我们以5阶B树为例，看看B树的数据存储。

![format_png][]

### **3、B树在磁盘文件中的应用** ###

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

#### 3.1、**磁盘** ####

磁盘能够保存大量的数据，从GB一直到TB级，但是 他的读取速度比较慢，因为涉及到机器操作，读取速度为毫秒 级 。

![format_png 1][]

磁盘由盘片构成,每个盘片有两面，又称为盘面 。盘片中央有一个可以旋转的主轴，他使得盘片以固定的旋转速率 旋转，通常是5400rpm或者是7200rpm,一个磁盘中包含了多个这样的盘片并封装在一个密封的容器内 。盘片的每个表面是由一组称为磁道同心圆组成的 ，每个磁道被划分为了一组扇区 ，每个扇区包含相等数量的数据位，通常是512个子节，扇区之间由一些间隙隔开,这些间隙中不存储数据 。

#### 3.2、**磁盘IO** ####

![c1323d29ce1cec61239bec3d3e83b7c9.png][]

磁盘用磁头来读写存储在盘片表面的位，而磁头连接到一个移动臂上，移动臂沿着盘片半径前后移动，可以将磁头 定位到任何磁道上，这称之为寻道操作。一旦定位到磁道后，盘片转动，磁道上的每个位经过磁头时，读写磁头就 可以感知到该位的值，也可以修改值。对磁盘的访问时间分为 **寻道时间**，**旋转时间**，以及**传送时间**。 由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，因此为了提高效率，要尽量减少磁盘I/O，减少读写操作。 为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会**预读**，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的**局部性原理**：当一个数据被用到时，其附近的数据也通常会马上被使用。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此预读可以提高I/O效率。

**页**是计算机管理存储器的**逻辑块**，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储 块称为一页（**1024个字节**或其整数倍），预读的长度一般为页的整倍数。主存和磁盘以页为单位交换数据。当程 序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位 置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

文件系统的设计者利用了磁盘预读原理，将一个**结点的大小设为等于一个页**（1024个字节或其整数倍），这样每 个结点只需要一次I/O就可以完全载入。那么3层的B树可以容纳1024\*1024\*1024差不多**10亿个数据**，如果换成二 叉查找树，则需要**30层**！假定操作系统一次读取一个节点，并且根节点保留在内存中，那么B树在10亿个数据中查 找目标值，只需要小于3次硬盘读取就可以找到目标值，但红黑树需要小于30次，因此B树**大大提高了IO的操作效率**。

### **4、B+树** ###

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

1. 非叶结点**仅具有索引作用**，也就是说，非叶子结点只存储key，不存储value；

2. 树的所有叶结点构成一个**有序链表**，可以按照key排序的次序遍历全部数据。

#### **4.1 B+树存储数据** ####

若参数M选择为5，那么每个结点最多包含4个键值对，我们以5阶B+树为例，看看B+树的数据存储。

#### **4.2 B+树和B树的对比** ####

**B+ 树的优点在于：**

1.由于B+树在非叶子结点上不包含真正的数据，只当做索引使用，因此在内存相同的情况下，能够**存放更多的key**。 2.B+树的叶子结点都是相连的，因此对整棵树的遍历只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要**进行每一层**的递归遍历。

**B树的优点在于：**

由于B树的**每一个节点都包含key和value**，因此我们根据key查找value时，只需要找到key所在的位置，就能找到 value，但B+树只有叶子结点存储数据，索引每一次查找，都必须一次一次，一直找到树的最大深度处，也就是叶 子结点的深度，才能找到value。

**B+树在数据库中的应用**

在数据库的操作中，查询操作可以说是最频繁的一种操作，因此在设计数据库时，必须要考虑到查询的效率问题， 在很多数据库中，都是用到了B+树来提高查询的效率；

在操作数据库时，我们为了提高查询效率，可以基于某张表的某个字段建立索引，就可以提高查询效率，那其实这 个索引就是B+树这种数据结构实现的。

###### **B-树深入**   B树由来: ######

定义：B-树是一类树，包括B-树、B+树、B\*树等，是一棵自平衡的搜索树，它**类似**普通的平衡二叉树，不同的一点是B-树允许**每个节点有更多的子节点**。  
B-树是专门为**外部存储器设计**的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中。

定义只需要知道B-树允许每个节点有更多的子节点即可（多叉树）。子节点数量一般在上千，具体数量依赖外部存储器的特性。

先来看看为什么会出现B-树这类数据结构：

传统用来搜索的平衡二叉树有很多，如 **AVL 树，红黑树**等。这些树在一般情况下查询性能非常好，但当**数据非常大**的时候它们就无能为力了。原因当数据量非常大时，**内存不够用**，大部分数据只能存放在磁盘上，只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右。速度相差了近 **5 个数量级**，磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能？减少磁盘 IO 次数，像 AVL 树，红黑树这类平衡二叉树从设计上无法“迎合”磁盘。

![6f79c39aff0a4d7ab723c5d4c00c91c8.png][]

上图是一颗简单的平衡二叉树，平衡二叉树是**通过旋转**来保持平衡的，而旋转是对**整棵树**的操作，若**只有部分加载到内存中则无法完成旋转操作**。

其次平衡二叉树的高度相对较大为 log n（底数为2），这样逻辑上很近的节点实际可能**非常远**，无法很好的利用**磁盘预读**（局部性原理），所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

**空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。**

我们从“迎合”磁盘的角度来看看B-树的设计:

索引的效率依赖与**磁盘 IO 的次数**，快速索引需要有效的减少磁盘 IO 次数，如何快速索引呢？索引的原理其实是不断的缩小查找范围，就如我们平时用字典查单词一样，先找首字母缩小范围，再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。

为了更快，B-树每次将范围分割为多个区间，区间越多，定位数据越快越精确。那么如果节点为区间范围，每个节点就较大了。所以新建节点时，直接申请页大小的空间（磁盘存储单位是按 block 分的，一般为 512 Byte。磁盘 IO 一次读取若干个 block，我们**称为一页**，具体大小和操作系统有关，一般为 4 k，8 k或 16 k），计算机内存分配是按页对齐的，这样就实现了**一个节点只需要一次 IO**。

![b5b5910910a1469a95750b06b6a14022.png][]

上图是一棵**简化的**B-树，多叉的好处非常明显，有效的降低了B-树的**高度**，为**底数很大**的 log n，底数大小与节点的子节点数目有关，一般一棵B-树的高度在 **3 层左右**。层数低，每个节点区确定的范围更精确，范围缩小的速度越快（比二叉树深层次的搜索肯定快很多）。上面说了一个节点需要进行一次 IO，那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an)，并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

点评：B树的每个节点，都是**存多个值**的，不像二叉树那样，一个节点就一个值，B树把每个节点都给了一点的范围区间，区间更多的情况下，搜索也就更快了，比如：有1-100个数，二叉树一次只能分两个范围，0-50和51-100，而B树，分成4个范围 1-25， 25-50，51-75，76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的

三、B-树的查找  
我们来看看B-树的查找，假设每个节点有 n 个 key值，被分割为 n+1 个区间，注意，每个 key 值紧跟着 data 域，这说明B-树的 key 和 data 是**聚合在一起的**。一般而言，根节点都在内存中，B-树以每个节点为一次磁盘 IO。

比如上图中，若搜索 **key 为 25** 节点的 data，首先在根节点进行二分查找（因为 keys 有序，二分最快），判断 key 25 小于 key 50，所以定位到**最左侧**的节点，此时进行一次磁盘 IO，将该节点从磁盘读入内存，接着继续进行上述过程，直到找到该 key 为止。

**B+ 树**  
B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于:

所有关键字存储在**叶子节**点出现,内部节点(非叶子节点并不存储真正的 data)。  
为所有叶子结点增加了一个**链指针**。

**简化 B+树 如下图：**

## ![063a2a63a44f4caca3bbe41c40c91b9a.png][] ##

因为内节点并不存储 data，所以一般B+树的叶节点和内节点**大小不同**，而B-树的每个节点大小一般是相同的，为一页。

![d47eac95ee734b83bc687e6ea4170814.png][]

**使用B+树的好处**  
由于B+树的内部节点**只存放键，不存放值**，因此，一次读取，可以在内存页中获取更多的键，有利于更快地缩小查找范围。

B+树的叶节点由**一条链相连**，因此，当需要进行一次全数据遍历的时候，B+树只需要使用O(logN)时间找到最小的一个节点，然后通过链进行O(N)的顺序遍历即可。而B树则需要对树的每一层进行遍历，这会需要更多的内存置换次数，因此也就需要花费更多的时间

![e3340931f2e1432eacc7536f91775af0.png][]

知识来源：

[【23版面试突击】你知道B树和B+树的区别吗？MySQL为什么使用B+树而不是B树？\_哔哩哔哩\_bilibili][23_B_B_MySQL_B_B_bilibili]

[Java数据结构算法：B树和B+树 - 知乎][Java_B_B_ -]

[B树与B+树的区别\_b树和b+树的区别\_森明帮大于黑虎帮的博客-CSDN博客][B_B_b_b_-CSDN]

[d7a8c748068e46ffa3f6448026fe5fb4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/0955098dfcd141a3be2cd3fd1ca04d29.png
[c6d1f8164c2dbd8533f3bc326318c290.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/565954e28c0a4d50a54777dc65ec09b0.png
[format_png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/fc19adf6ed8742b482e74a6e3294ef19.png
[format_png 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/495af4d7d15942caa2a3e99a81c7cce9.png
[c1323d29ce1cec61239bec3d3e83b7c9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/b13322260b3041f3adab41573ff66506.png
[6f79c39aff0a4d7ab723c5d4c00c91c8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/2662b41b2be64a5cb138bd660feeb22a.png
[b5b5910910a1469a95750b06b6a14022.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/f93bc2dbc56b487caf1188eaf9337080.png
[063a2a63a44f4caca3bbe41c40c91b9a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/473e0c4c571846e2953cb20f152a5ce8.png
[d47eac95ee734b83bc687e6ea4170814.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/f76e5cb0c58d4fe3a325804b661b7570.png
[e3340931f2e1432eacc7536f91775af0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/13/9d2d238cf79840b6a72e981ac1c2c9af.png
[23_B_B_MySQL_B_B_bilibili]: https://www.bilibili.com/video/BV1M24y1z7BR?p=179&vd_source=7ec3a2ec18181a9b64c9a3246305e511
[Java_B_B_ -]: https://zhuanlan.zhihu.com/p/541198131
[B_B_b_b_-CSDN]: https://blog.csdn.net/qq_44918090/article/details/120278339