MySQL之索引树

迈不过友情╰ 2022-12-18 00:55 133阅读 0赞

今天是1024程序员节，祝大家节日快乐！

> **关键词：**索引    二叉查找树    平衡二叉查找树    B树    B+树

--------------------

推荐一个可以在线演示各种树的插入过程的网站，帮助学习和理解各种树：

[https://www.cs.usfca.edu/~galles/visualization/Algorithms.html][https_www.cs.usfca.edu_galles_visualization_Algorithms.html]

学习MySQL中索引，避免不了B+树。B+树是由二叉查找树到平衡二叉查找树到B树演变而来的，所以一步步从二叉查找树开始了解，对B+树的学习更有帮助。

关于数据结构-树，可以理解成是一种特殊的键值对结构。（就像jdk1.8中，HashMap使用了红黑树来存储数据）

关于索引的知识，请戳这里[《MySQL之索引》][MySQL]。

--------------------

# **█ 名词解释** #

首先介绍下树中的几个名词，这些名词对所有的树都共用。

*  **根节点：**树结构中最顶层的节点
 *  **子节点：**其他节点（父节点）指向的节点
 *  **父节点：**指向其他节点（子节点）的节点
 *  **叶子节点：**没有子节点的节点，在树结构的最底层
 *  **内部节点：**所有的非叶子节点，包括根节点
 *  **外部节点：**即叶子节点
 *  **左子树：**父节点左边分支所组成的树
 *  **右子树：**父节点右边分子所组成的树

（这里的左右，是从我们看过去的角度来说的，而不是父节点自身的角度）

*  **树的深度：**也叫层级，根节点到叶子节点的路径长度

--------------------

# **█** 二叉查找树 #

二叉查找树，Binary Search Trees，简称BST。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70][]

如上图所示，就是一棵二叉查找树，其中：

根节点：27

子节点：对于27来说，14和35是其子节点

父节点：14的父节点是27

叶子节点：10、19、31、42

内部节点：27、14、35

外部节点：10、19、31、42

左子树：对于27来说，14、10和19组成的树就是其左子树

右子树：对于27来说，35、31和42组成的树就是其右子树

**特征：**

①节点是有序的

②除叶子节点外，每个节点最多有两个分支

③当前节点的左子节点要比自己小，右子节点要比自己大

比如，图中的27节点，它的左子节点14比自己小，右子节点35比自己大。

**查找值：**

当我们在BST中搜索一个值时，我们从根节点开始，并将搜索的值与根节点的值进行比较。如果搜索值小于根节点值，我们会转到左子树。如果大于根节点的值，就到右子树，直到找到搜索的值。还有可以一直找到叶子节点都没有找到搜索的值。比如查找上图中的31，先和根节点的值27比较，31大于27，走右节点到达35。再和35比较，31小于35，走左节点到达31。比较相当返回结果。

**插入值：**

向BST添加新值就像搜索一个值一样，先要找到它应该的位置。比如插入一个新值30，30比27大，应该走右子树，30比35小，再走左子树，30比31小，再走左子树，所以最后的结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 1][]

**删除值：**

删除节点值大致分为3中情况：

①删除叶子节点。此时可以直接删除

比如上图中的10、19、30、42

②删除的节点有一个子节点

此时需要将子节点的值替换到被删除节点的位置。比如上图中的31，删除完，要将30移动到此位置。

③删除的节点有两个子节点

此时需要找到该节点右子树中最小的一个节点，将该节点的值替换到删除节点的位置。比如上图中的27，找到27的右子树中最小的值是30，将30的值替换到27所在的位置。

**发现问题：**

①基于二叉查找树的特点，当插入的数据，是从小到大或从大到小的有顺序的进行，那么二叉查找树将会变成链表。比如依次插入：1,2,3,4,5,6。此时查找的话，就是从根节点开始一个个遍历了，无疑查询效率会大大降低。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 2][]

②数据量很多的时候，树的深度就会增加，树的深度决定了查找目标值所要经历的路径，这将增加查找的效率。

**解决问题：**

二叉树存在的问题就是增加节点的时候，树的深度也会相应的增加。那可不可以伴随着节点的增加，树的深度能够自动做出调节，来减少树的深度呢？于是出现了平衡二叉查找树。

--------------------

# **█ AVL树** #

AVL树，以它的三个发明者Adelson, Velski 和 Landis命名，是一种平衡二叉查找树。AVL具有BST的特征，但是AVL树会检查每个节点的左子树和右子树的高度，确保两者的高度差异不大于1，这种差异被称为平衡因子。正是基于这个特点，AVL树能够调节节点左右子树的深度，达到的树的平衡，因此AVL叫平衡二叉树。如下图所示，就是一棵AVL树，因为满足每个节点的左右子树高度差不大于1。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 3][]

如下图就不是一棵AVL树，举个例子，12节点的左子树深度为4，右子树深度为2，之间差值大于1了。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 4][]

AVL树是怎么样去平衡节点的左右子树高度的呢？AVL树通过旋转来达到树的平衡，一般有四种旋转：

①左旋转

②右旋转

③先左旋转再右旋转

④先右旋转再左旋转

**左旋转：**

如果树变得不平衡，当一个节点插入到右子树的右子树中时，我们将执行一次左旋转。如下图，依次插入10、20、30。当插入完10和20之后，继续插入30，此时10的右子树深度是2，左子树的深度为0，差值大于1了，需要进行左旋转来平衡树之间的深度（虚线框中）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 5][]

**右旋转：**

如果树变得不平衡，如果一个节点插入到左子树的左子树中。然后树需要向右旋转。和左旋相反，依次插入30、20、10之后，需要进行右旋。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 6][]

**先左旋再右旋：**

如图，依次插入20、10、15。当插入完20和10之后，树就不平衡了。此时15先左旋（步骤2）再右旋（步骤3）。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 7][]

**先右旋再左旋：**

如图依次插入20、30、25。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 8][]

**发现问题：**

（1）虽然AVL树可以自动平衡树的深度，但数据量大的时候，避免不了树的深度会很大，而且一个节点只能存储一个值。如果一个节点能够存储多个值的话，树的深度是不是就会相对减少了呢？

（2）当插入值的时候，为了达到平衡，需要进行频繁的旋转操作。

--------------------

# **█ B树** #

B树是一个平衡树。不同于二叉树的节点仅有两个分支，B树的节点可以有多个分支，并且单个节点可以存放多个值。大部分的平衡树（比如平衡二叉树、红黑树），都是假设所有的数据都是在内存中的。但是对于MySQL来说，有可能一张表的索引数据很大很大，没办法一次性的将数据全都加载到内存中（数据量大会占用太多的内存，从而引发比如内存溢出等错误）。当数据的键很多时，即树的节点很多，可以以“块”的形式从磁盘中读取数据加载到内存中，每次访问数据都读取“块”大小的数据。但是磁盘读取数据比内存读取数据的速度要慢很多，所以如果与磁盘交互的次数多了的话，也会影响数据的读取效率。而B树既可以满足以“块”的形式从磁盘加载数据，又能减少与磁盘交互的次数。如下图所示，假定其是一颗最大度为5的B树。

![20201024174222758.png][]

**特征：**

①所有的叶子节点都在同一级别

叶子节点都在同一级别，也就是从根节点出发，每一个分支到其叶子节点的深度都一样。

②B树由最大度（degree）t 定义

这个t值由磁盘块的大小决定。t值决定了每个节点最多含有的键的个数。

③除根节点外，每个节点必须至少包含(t-1)/2个键，根节点至少要含有一个值

如果t是5，那么除根节点外，每个节点至少要含有2个键。

④所有的节点（包括根节点）最多含有t-1个键

⑤一个节点的最大子节点个数，等于它含有的键的个数+1

比如图中黄色的根节点含有一个键100，那它的子节点个数就是2，即图中2个绿色。绿色的节点含有2个键，那它的子节点个数就是3个。

其实这个也很好理解。节点含有的键的个数，那么键的前后和键与键之间就会产生n+1个间隙，每个缝隙就可以产生一个分支，即一个子节点。

比如： 35 65 90 120 ，这四个键，前后之间共有5个间隙。

⑥一个节点中的键值，都是从小到大升序排列的。两个键k1和k2之间的子键包含从k1到k2范围内的所有键。

比如上图中65和90，它们之间的子健就是70和80。

⑦与其他平衡二叉搜索树一样，搜索、插入和删除的时间复杂度为O(log n)

**查找值：**

和二叉树查找一样，都是从根节点开始查找，小于当前节点值的转向左节点查找，大于当前节点值的转向右节点查找。离根节点越近的值，查找的效率越高。比如查找上图中的140，先从根节点查找，从35一直找到120,140比120大，转向120的右子节点，再从子节点的一开始找，一直找到140为止。

**插入值：**

新的键插入总是往叶子节点插入。插入一个键既要考虑顺序，还要考虑树的平衡（因为要满足节点的键的个数要小于最大度值-1等规则）。添加一个键，需要找到键在叶子节点的位置，如果此时节点还有空间，则直接插入，树的结构和深度不会改变。比如上图中，假设最小度数是4的话，则每个节点最多存储3个键，我们添加一个值15，10-20的节点还有一个键的空间，只需要在10-20之间添加即可。

![20201024174509399.png][]

但如果想插入150，因为设定的最小度数是5，每个节点最多只能有4个键，图中最右面的节点再继续插入数据就会造成溢出。于是需要调整节点已达到平衡，将节点中间位置的键移到父节点，当前节点分裂。

![20201024174545250.png][]

造成上图的原因是因为，150插入的话，150是节点中间的值，将150移动到父节点（图中的根节点），但此时又会造成父节点溢出，父节点继续取中间数值90往其父节点移动，但因为是根节点不能有父节点了，所以此时只有分裂，树的深度也增加了。当叶子节点的发生溢出了，要分裂叶子节点，如果父节点发生溢出，我们将以同样的方式分割父节点。在极端情况下，我们必须分割根节点，树的深度会增加。

**删除值：**

当我们想从b树中删除一个键时，我们会找到那个键并删除它。如果删除导致了欠流(存储在节点中的键的数量太少)，需要将节点合并在一起，这和插入键的情况正好相反。我们将把那个节点与包含最多值的相邻节点合并。如果新合并的节点包含太多值(溢出)，我们将把它分成左、中、右三部分，并重新排列树结构。

**B树在数据库索引中的应用：**

当数据库中索引结构使用B树的时候，每个节点存储3种值，第一个是索引键值，即建立索引的列的值，第二个是指向该索引键所在的行记录的指针（指向包含键值的磁盘文件块的指针），如果有子节点的话，则还有指向子节点的指针。

例如，如果索引在id列上，那么节点将包含值“7”和指向id=7的行的指针。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 9][]

如上图所示，蓝色长方形表示一个个数据块（树的节点），里面包含的白色圆圈是索引键，黑色虚线箭头表示该键指向实际的一行记录，红色箭头表示指向子节点的指针。黄色长方形表示数据所在的磁盘文件。

**发现问题：**

B树的节点存储了键值的所在行的数据指针(指向包含键值的磁盘文件块的指针)，这将会占用一部分节点空间，即磁盘块的空间。磁盘块的空间是固定值，当每个键占用的空间增加，那一个磁盘块存储的键值就会相应减少，那为了存储更多的值，树的深度就会增加，这样又会增加了查找的花销。

**解决问题：**

既然指向键值实际数据记录的指针会占用空间，那将其移除不就可以了。B+树解决了这个问题。

--------------------

# **█ B+树** #

为了解决上述B树存在的问题，B+树是通过将数据指针仅存储在树的叶节点上来解决的，这样在根节点和中间节点上能够存储更多的键数据。由于数据指针只存在于叶节点上，因此叶节点必须存储所有键值以及它们对应的指向磁盘文件块的数据指针，以便访问到具体的行数据。

![20201024174909463.png][]

**与B树相比，B+树有以下几个主要的区别：**

①内部节点只存储键值，它们不存储指向实际行的指针

②叶节点存储值和行指针（指向磁盘文件块的数据指针）

对于①②两点减少了根节点和中间节点的内部节点的大小，允许在同一内存页上存储更多节点。这样存储更多的数据时，树的高度会降低，从而导致磁盘I/O操作减少。

③B+树中的叶子节点是链接的（双向链表），所以我们可以进行一次全扫描。当我们需要找到给定范围内的所有数据时，这是非常有用的。

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

如图所示，这种方式是MyISAM存储引擎索引的结果，对于InnoDB来说，叶子节点是直接存储着主键对应的那一行数据的。（下面的两张图有点问题，MySQL的B+树中叶子节点之间是通过双向链表连接的，图中画成了单向链表。）

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 10][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 11][]

希望随着MySQL的发展，能够出现比B+树更加适合更加优越的树来构建索引结构。

[https_www.cs.usfca.edu_galles_visualization_Algorithms.html]: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[MySQL]: https://blog.csdn.net/weixin_50518271/article/details/109341236
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70]: /images/20221122/20a14562c3c0449cb5d1e0c654f007b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 1]: /images/20221122/e1808bdddb504533a1a52eb002a11c60.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 2]: /images/20221122/598997f59b9e4c15aff4f5ad2d271a2a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 3]: /images/20221122/7bcfec91d74941dc983e3256ae6c4009.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 4]: /images/20221122/fa28fc7f75a144aabc4a8a02518d555f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 5]: /images/20221122/0ab13e40e6b7433da8edc2ab18c1cbf5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 6]: /images/20221122/5916907b888b40b0948833bdb8aa8501.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 7]: /images/20221122/28d772d236664242b6cc4e387afa057c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 8]: /images/20221122/6a17f280bf07409b84442e17621247c8.png
[20201024174222758.png]: /images/20221122/e0ab4615f25d4b1c9d26f06cd66bdbcc.png
[20201024174509399.png]: /images/20221122/bc5f923c9ba24327b83c83acf83cd0cc.png
[20201024174545250.png]: /images/20221122/f0954e8bf64648ad92105f307fe5d368.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 9]: /images/20221122/010bff00365e40fe866af52f452e8e45.png
[20201024174909463.png]: /images/20221122/ec2b88d7ca614bdeaedf1597a545a910.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 10]: /images/20221122/8a6541256f0943ff849ab08476f05367.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MDUxODI3MQ_size_16_color_FFFFFF_t_70 11]: /images/20221122/6494156d570041adb5785bd5757d5408.png