数据结构中B树和B+树的区别

我不是女神ヾ 2023-02-12 11:23 8阅读 0赞

# 转载链接：[https://msd.misuland.com/pd/2884250171976189524][https_msd.misuland.com_pd_2884250171976189524] #

# B树和B+树数据结构及使用场景 #

## 1.出现的原因 ##

我们已经知道他们两是mysql索引的数据结构，为什么要使用这种数据结构呢？我们知道内存读取效率远远高于磁盘IO的效率，当数据量大而不能完全存放于内存时，只能依靠磁盘了，一次存放于磁盘页中，每个磁盘页对应一个树的节点。也就是说只要我们能减少磁盘IO的次数，那么查询效率就会显著提高。如何减少?

B树就是通过降低树的深度，将二叉树的“瘦高”变成“矮胖”：

1.每个节点存储多个元素。

2.采用多叉树。

## 2. B树 ##

这里先说下阶和度的区别：

**度数**：在树中，每个节点的子节点（子树）的个数就称为该节点的度（degree）。

**阶数**：（Order）阶定义为一个节点的子节点数目的最大值。（自带最大值属性）

**m阶的B树的规则**：

1.  根节点至少2个子树
2.  每个节点最多有m个子树
3.  每个中间节点都包含k-1个元素和k个孩子，其中ceil（m/2）<=k<=m（ceil向上取最大整数）
4.  每个叶子节点的元素范围:\[ceil(m/2)-1,m-1\]
5.  所有的叶子节点都在同一层
6.  每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分
7.  **每个节点不仅有索引的值还都保存了卫星数据，B+树不同**

**卫星数据**：指向数据库的记录（如：数据库中的行）类似于指针指向记录

示例：3阶B树（实际有很多节点没有表示出来）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70]

**查询**：

上图为例查询5

第一次磁盘ＩＯ：在内存中定位（与17、35比较），比17小，左子树； 　　第二次磁盘ＩＯ：在内存中定位（与８、12比较），比８小，左子树； 　　第三次磁盘ＩＯ：在内存中定位（与3、5比较），找到5，终止。

整个过程中，我们可以看出：比较的次数并不比二叉查找树少，尤其适当某一节点中的数据很多时，但是磁盘IO的次数却是大大减少。比较是在内存中进行的，相比于磁盘IO的速度，比较的耗时几乎可以忽略。所以当树的高度足够低的话，就可以极大的提高效率。相比之下，节点中的元素多点也没关系，仅仅是多了几次内存交互而已，只要不超过磁盘页的大小即可。

## 3.B+树 ##

B+树是B树的变种，有着比B树更高的查询效率。一般用作于mysql索引。

**m阶B+树的规则**：

1.  有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.  所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接，形成一个有序的链表。
3.  所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

**示例**：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 1]

## 卫星数据存放的位置 ##

**B树**：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 2]

**B+树**：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 3]

通过比较我们可以发现：B树中每个元素都会存放卫星数据，那么就会有这样一个缺点：同等数据下，B+树的磁盘页存放的节点会比B树的多，也就是说B+树会比B树更“矮胖”。

## 4.查询性能的比较： ##

通过单元素查询和范围查询来比较分析。

### 4.1单元素查询： ###

1.  按照上图比如查询数字3，不管B还是B+都会经历3次磁盘IO,看起来似乎都是一样的，但是B+树的磁盘页存放的节点比B树多，一旦数据量大了之后会明显降低磁盘IO。
2.  B+树比B树查询更稳定：B树要查询到匹配元素（最好情况是根节点，最坏情况是叶子节点），B+树无论匹配元素在哪都必须查询到叶子节点（数据存放在叶子节点）。

### 4.2范围查询： ###

在实际应用场景中，一般查询的都是多条数据，有可能会需要跨节点遍历查询

1.  B树的范围查找需要不断的中序遍历。首先二分查找到范围下限，在不断的通过中序遍历，直到查询到范围上限，比较耗时繁琐。
2.  B+树相比较于B树就简单许多，首先通过二分查找，找到范围下限，然后通过叶子结点的链表顺序遍历，直至范围上限，效率很高。

**B树的范围查找**：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 4]

**B+树的范围查找**：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 5]

[https_msd.misuland.com_pd_2884250171976189524]: https://msd.misuland.com/pd/2884250171976189524
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20190309100556733.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190309100540130.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20190309100657652.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190309100705758.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20190309100721381.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20190309100735950.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4MjM4Mjk2,size_16,color_FFFFFF,t_70