Mysql索引数据结构B+树的演变

怼烎@ 2023-01-18 13:23 143阅读 0赞

> 公众号上线啦！  
> 搜一搜【国服冰】  
> 使命：尽自己所能给自学后端开发的小伙伴提供一个少有弯路的平台  
> 回复：国服冰，即可领取我为大家准备的资料，里面包含整体的Java学习路线，电子书，以及史上最全的面试题！

# 索引？ #

`MySQL`官方对索引的定义为：索引`(Index)`是帮助`MySQL`高效获取数据的数据结构。我们可以简单理解为：**快速查找排好序的一种数据结构。**

**下面是一张未做任何操作的表，Col1为自增主键，Col2为Value**

![未加索引][20210506162955180.jpg]

此时我想查找值为`22`的那一行记录，因为表中值未被排序，所以只能从头遍历`5`次才能查找到主键为`5`，值为`22`的那一行记录。**如果表中不止这7条数据，而是百万条、千万条记录呢？查询速度可想而知的慢**。

**索引数据结构：**

*  二叉排序树
 *  红黑树
 *  B树（B-Tree）
 *  B+树（B+Tree）

## 二叉排序树 ##

> 一个节点只能有两个子节点，也就是度最大为2  
> 左节点比父亲小，右节点比父亲大

![排序后][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDQyMzM1_size_16_color_FFFFFF_t_70]

此时再对`22`进行`Find`，**只需要查找一次，进行一次磁盘IO**便能找到需要的值。  
经过二叉排序树优化后，查询效率相对于之前大大提升，但是有一种情况，**如果Col2是持续递增的呢**？

![持续递增][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDQyMzM1_size_16_color_FFFFFF_t_70 1]

此时这只排序二叉树出现的**失衡**，也就是相当于变成了一条单向链表，**如果想要查询某个值时，只能从头往下遍历查找，而不能像上面的排序二叉树一样排除掉一部分值**。

## 红黑树 ##

红黑树的出现就可以解决这个问题，红黑树的特点会自动平衡树

![未平衡][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDQyMzM1_size_16_color_FFFFFF_t_70 2]

![已平衡][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDQyMzM1_size_16_color_FFFFFF_t_70 3]

左图在插入数值为3时，红黑树的算法发现有**偏向**，就会**重新调整树结构**。

那我们可以看看，之前的数据1～6持续递增的树，会变成什么样？  
![1-6红黑树][1-6]

经过红黑树自平衡后，现在查找6这个节点，只需要查找3次，有部分数据被提前排序了。红黑树很好的平衡了树的偏向问题，但红黑树问题也比较大。

1.  每次都要检查规则，再把树进行重新平衡，这个是非常消耗时间的
2.  数据量大的话，红黑树的深度会比较深，树一旦深就代表着我们读取磁盘次数就会增加

## B-Tree（多路自平衡查找树，目的降低树高，减少磁盘IO） ##

**影响数据查询时间的是树的高度，高度越高，我们需要比较的次数越多，磁盘IO操作就会越多，注意一个索引不是一次性全部加载到内存，如果索引太大比如100G一次性加载到内存也不现实，磁盘有预读机制，每次读的时候都是加载一个磁盘页（4kb）到内存里面，那我们是不是可以想办法把树的高度弄低点？那我们的B树数据结构就由此产生。**

假如当前有一颗m阶的B树（注意阶的意思是指每个节点的孩子节点的个数），那么其符合

> （1）每个节点最多有m个子节点  
> （2）除了根节点和叶子节点之外，其他的每个节点最少有m/2（向上取整）个孩子节点  
> （3）根节点至少有两个孩子节点，（除了第一次插入的时候，此时只有一个节点，根节点同时是叶子节点）  
> （4）所有的叶子节点都在同一层  
> （5）有k个子节点的父节点包含k-1个关键码  
> （6）所有的叶节点都在同一层  
> （7）每个节点中的子节点都是从左到右排序的

![B Tree][]

我们的主要目标就是把树的高度弄低，上图中，**我们可以看到之前的一个节点里面多了几个子节点**（即几阶树）**【核心点一】**，这样的设计就是把之前节点只存储1个数值，现在可以存储多个数值；

**多个子节点数值都是从左到右排序【核心点二】**，有便于快速查找；

**而且叶节点具有相同的深度，保证了每个数值查询效率一致【核心点三】**；

**图中每个节点里面都包含具体信息data【核心点四】**，`data`类似于这个值在磁盘上的一个指针引用的地址，再查询的时候找到对应的索引后，直接取出这个节点中的信息；

B树的核心思想就是把树高度弄低，**用了树节点包含多个子节点的设计思想**，上图中一个树节点包含3个子节点。

**1-6 B-Tree：**  
![1-6 B-Tree][]

## B+Tree（B-Tree变种） ##

> 非叶子结点不存储data，只存储索引（冗余），可以放更多的索引  
> 叶子结点包含所有索引字段  
> 叶子结点用指针连接，提高区间访问的性能

![B+ Tree][B_ Tree]

一个树节点我们应该尽可能的包含更多的子节点，但又不能超过一个磁盘页（4kb）的大小，所以将所有`data`信息都移动了子节点中，而且子节点和子节点之间会有个指针指向，这个也是`B+`树的核心点，这样可以大大提升范围查询效率，也方便遍历整个树。

![1-6 B+Tree][1-6 B_Tree]

[20210506162955180.jpg]: /images/20221021/a39656b6ea1a4d09ac10a212d90ca129.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDQyMzM1_size_16_color_FFFFFF_t_70]: /images/20221021/294743c18f17446da656548a3d11db99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDQyMzM1_size_16_color_FFFFFF_t_70 1]: /images/20221021/6ce52fb9da214687962441577af1c1bb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDQyMzM1_size_16_color_FFFFFF_t_70 2]: /images/20221021/bba1ff206d21448c97853f3d64e18e9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNDQyMzM1_size_16_color_FFFFFF_t_70 3]: /images/20221021/424a6fd21fb84b53a3d47b9b276cef50.png
[1-6]: /images/20221021/891bd0502bd346f68081bbdfdf394be6.png
[B Tree]: /images/20221021/15abbb13810842dea0ea6966a172da39.png
[1-6 B-Tree]: /images/20221021/a2d022d621c5442eab479f59dc6924d9.png
[B_ Tree]: /images/20221021/39a4e66530ec4e63897524cc259eaff9.png
[1-6 B_Tree]: /images/20221021/dd2bc4d1eebe4ac9b6c4de2395097942.png