《MySQL中级系列教程-第五章-索引底层原理》

布满荆棘的人生 2023-01-02 11:27 45阅读 0赞

# 《MySQL中级系列教程-第五章-索引底层原理》 #

# 一、索引概述 #

索引是帮助数据库快速查询数据的一种数据结构，在数据库中，数据库系统除了存储数据之外还维护着一种特殊的数据结构，这种数据结构以某种方式指向数据，这样就可以在这种数据结构上实现高级算法来查询数据，这种数据结构就是索引。

> 索引是啥？索引就是帮助我们快速查找数据的一种**数据结构**！没毛病！

*  索引示意图：

我们来直观的感受一下，有建立索引和没有建立索引的直观感觉

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70]  
如图所示，索引能够帮我们快速的定位到数据的具体位置，高效查询。一般来说，索引本身也很大，不可能全部存储在内存当中，因此索引往往以索引文件的形式存储在磁盘上。索引是用来提供高性能数据库的常用工具。

# 二、索引的数据结构 #

*  `B-Tree`：常见的索引类型，B+Tree就是在此数据结构上做的优化
 *  `Hash`：是基于哈希表实现的，只有精确匹配索引所有列的查询才会生效。对于每一行数据，存储引擎都会对所有的索引列计算一个hash code,并将有的hash code存储在索引中，同时在哈希表中保存指向每个数据行的指针。
 *  `R-Tree`：R-Tree是B-tree在高维空间的扩展，也叫空间索引，主要用于地理空间数据类型，存储高维数据的平衡树。
 *  `Full-text`：Full-text索引就是我们常说的全文索引，它的存储结构也是B-Tree。主要是为了解决当须要用like查询时的低效问题。

**索引是在MySQL的存储引擎层中实现的，而不是在服务器层实现的。所以每种存储引擎的索引都不一定完全相同，也不是所有的存储引擎都支持所有的索引类型的。**

MyISAM、InnoDB、Memory三种存储引擎对各种索引类型的支持：

<table> 
 <thead> 
  <tr> 
   <th>索引</th> 
   <th>InnoDB</th> 
   <th>MyISAM</th> 
   <th>Memory</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>B-Tree</td> 
   <td>支持</td> 
   <td>支持</td> 
   <td>支持</td> 
  </tr> 
  <tr> 
   <td>Hash</td> 
   <td>不支持</td> 
   <td>不支持</td> 
   <td>支持</td> 
  </tr> 
  <tr> 
   <td>R-Tree</td> 
   <td>不支持</td> 
   <td>支持</td> 
   <td>不支持</td> 
  </tr> 
  <tr> 
   <td>Full-text</td> 
   <td>5.6版本之后支持</td> 
   <td>支持</td> 
   <td>不支持</td> 
  </tr> 
 </tbody> 
</table>

## 2.1 B+Tree数据结构 ##

B+Tree是从最早的平衡二叉树演化而来的。在讲B+Tree之前必须先了解二叉查找树、平衡二叉树（AVLTree）和平衡多路查找树（B-Tree），B+Tree即由这些树逐步优化而来。

关于数据结构的演变，大家可以来到这个网站：[Data Structure Visualization][]

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

### 2.1.1 二叉树 ###

*  特点：左子树的键值小于右子树的键值

我们按照顺序依次插入：`4 2 6 1 3 5 7`，得出如下二叉树：  
![在这里插入图片描述][20200723122637921.png]  
对该二叉树的节点进行查找发现深度为1的节点的查找次数为1，深度为2的查找次数为2，深度为n的节点的查找次数为n，因此其平均查找次数为 (1+2+2+3+3+3+3) / 7 = 2.428次

**二叉查找树是可以任意地构造的**，谁规定我必须按照`4 2 6 1 3 5 7`的顺序插入呢？同样是`1,2,3,5,6,7`这六个数字，我的插入顺序为：`1,2,3,4,6,5,7`，得到如下二叉树：

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

计算这颗树的平均查找次数：(1+2+3+4+5+6+6)/7=3.857次

这棵二叉树的查询效率明显就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——**平衡二叉树**，或称AVL树。

### 2.1.2 平衡二叉树 ###

平衡二叉树（AVL树）在符合二叉查找树的条件下，**还满足任何节点的两个子树的高度最大差为1**。

我们按顺序插入`6,3,7,2,4,1,5`等数据，观察AVL树与普通二叉树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70 2]

平衡二叉树对于二叉树来说相对较为规则，有效的减少了数据的检索次数，提高了查询效率。

### 2.1.3 B-Tree ###

B-Tree又叫**多路**平衡搜索树，一颗m叉的B-Tree特性如下：

*  树中每个节点最多包含m个孩子（m是叉数，2叉最多包含2个节点，3叉最多包含3个节点）。
 *  除根节点与叶子节点外（非根叶子节点），每个节点至少有\[ceil(m/2)\]个孩子。
 *  若根节点不是叶子节点（说明树的层级最少为2），则至少有两个孩子。
 *  所有的叶子节点都在同一层。
 *  每个非叶子节点由n个key与n+1个指针组成，**其中\[ceil(m/2)-1\] <= n <= m-1**

#### 2.1.3.1 B-Tree的演变过程 ####

我们以5叉B-Tree为例，根据公式推导\[ceil(m/2)-1\] <= n <= m-1，所以 2 <= n <=4 。当n>4时，中间节点分裂到父节点，两边节点分裂

我们依次插入：`68 78 71 65 72 69 75 81 77 70 87 76 84 90 68 80 82 88 89 83`等数字，观察B-Tree的演变过程

1）我们插入`68,78,71,65`，查看B-Tree的构成：

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

2）插入`72`，n>4，中间元素`71`向上分裂到新的节点

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

3）插入`69,75,81`不需要分裂

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

4）插入`77`，中间元素`77`向上分裂到父节点`71`

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

5）插入`70,87,76,84`不需要分裂

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

6）插入`90`，中间元素`84`向上分裂到父节点中

![在这里插入图片描述][20200723162753728.png]  
7）插入`68`，中间元素`68`向上分裂到父节点中

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

8）插入`80,82,88,89`不需要分裂

![在这里插入图片描述][20200723163010196.png]  
9）最后插入`83`，`78,80,81,82`节点n>5，中间节点`81`向上分裂，但分裂后父节点`68,71,77,84`的n>5，中间节点`77`向上分裂

![在这里插入图片描述][20200723173916787.gif]

#### 2.1.3.2 B-Tree的底层存储结构 ####

刚刚我们了解了一个B-Tree的完整演变过程，**Data Structure Visualization**这个网站并没有很好的显示B-Tree底层的一个结构情况（忽略了很多细节），例如没有显示指针、数据块、磁盘块等，我们手动画一张完整的B-Tree结构图：

我们按照顺序插入如下数据：`26 18 2 11 19 29 80 37 6 42 15 21 30 44 43 53 5 36 28 29 33 60 58 75`

**得到如下B-Tree结构：**  
![在这里插入图片描述][20200724172404718.png]  
**我们把B-Tree补充完整（指针、数据块、磁盘块等）：**

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

**每个节点都会占用一个磁盘块的磁盘空间**，当在数据检索时，会将此磁盘块加载到内存中，**每个非根节点上都有两个升序排序的键值和三个指向子树的指针**，该指针存储的是子节点所在磁盘块的内存地址

以磁盘块1为例，假设现在加载了磁盘块1到内存中，我们通过磁盘块的三个指针（P1、P2、P3）就能够判断，**P1指针指向的子树的数据范围为小于26，P2指针指向的子树的数据范围为26~37，P3指针指向的子树的数据范围为大于35**。

*  **模拟查找关键字21的过程**：

1）首先加载根节点，根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】

2）发现21比26小，根据磁盘块1中的P1指针找到对应的磁盘2，读入内存。【磁盘I/O操作第2次】

3）发现21比18大，根据磁盘块2中的P3指针找到磁盘块7，读入内存。【磁盘I/O操作第3次】

4）根据磁盘块7中的数据找到21。

观察查找过程：

![在这里插入图片描述][20200727175814380.gif]

*  **再模拟查找关键字28的过程**：

1）首先加载根节点，根据根节点找到磁盘块1，读入内存。【磁盘I/O操作第1次】

2）发现28比26大且比37小，根据磁盘块1中的P2指针找到对应的磁盘3，读入内存。【磁盘I/O操作第2次】

3）发现28比19小，根据磁盘块3中的P1指针找到磁盘块8，读入内存。【磁盘I/O操作第3次】

4）根据磁盘块8中的数据找到28。

观察查找过程：

![在这里插入图片描述][20200727180211850.gif]

### 2.1.4 B+Tree ###

B+Tree在原B-Tree的基础上，增加一个指向相邻叶子节点的链表指针，就形成了带有顺序指针的B+Tree，**提高区间访问的性能**。并且**B+Tree数据结构将数据全部存储在最底层的叶子节点**，这样可以保证每个磁盘块能够存储更多的指针，在一次IO磁盘开销中，查询到的数据更多。

我们按照如下顺序插入数据：`26 18 2 11 19 29 80 37 6 42 20 28`；

**得到如下B+Tree结构：**

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

**我们仔细观察B+Tree会发现，所有的数据都保存了一份到最底层的叶子节点上，其他的叶子节点上只是保存行数据的主键值**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70 4]  
**我们把B+Tree补充完整（指针、数据块、磁盘块等）**：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70 5]

在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。**这样提高了磁盘块之间的区间访问性能**

### 2.1.5 InnoDB数据页 ###

#### 2.1.5.1 操作系统的局部性原理 ####

我们知道数据最终是存储在磁盘上，当我们要做数据处理时，需要把磁盘中的数据调出到内存中来进行处理，这个过程会产生磁盘的IO（输入输出），由于磁盘IO是非常昂贵的操作，所以计算机操作系统对此做了优化。每一次IO时，不仅仅把当前磁盘地址的数据加载到内存，同时也把相邻数据也加载到内存缓冲区中

当访问一个地址数据的时候，与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页（page）。一页的大小与操作系统有关，一般为4k或者8k。这也就意味着读取一页内数据的时候，实际上发生了一次磁盘IO。

#### 2.1.5.2 InnoDB数据页管理 ####

在InnoDB中，页是其磁盘管理的最小单位。InnoDB存储引擎中默认每个页的大小为16KB，可通过参数`innodb_page_size`将页的大小设置为4K、8K、16K，在MySQL中可通过如下命令查看页的大小：

show variables like 'innodb_page_size';

而系统一个磁盘块的存储空间往往没有这么大，因此**InnoDB每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小16KB**。InnoDB在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘I/O次数，提高查询效率。

*  B-Tree：

B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。

*  B+Tree：

在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以**大大加大每个节点存储的key值数量，降低B+Tree的高度**。

InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为`10^3` ）。也就是说一个深度为3的B+Tree索引可以维护10^3 \* 10^3 \* 10^3 = 10亿 条记录。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70]: /images/20221119/c598996f67bd48698a0d2b3019b7259d.png
[Data Structure Visualization]: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70 1]: /images/20221119/4cc4b90c808d40e39997f1847928aa13.png
[20200723122637921.png]: /images/20221119/6875a68920404c3cbb5f2a6a2ff5b204.png
[20200723142558506.png]: /images/20221119/330bc65c958d40e1b03037c5c9621754.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70 2]: /images/20221119/ad6da355420543dc987a595c058ccfb5.png
[20200723161611786.png]: /images/20221119/f6186f38e5d346c5a6bb8966565df303.png
[20200723161724186.png]: /images/20221119/76cd701a7ef34cfd9a3276fe1080e695.png
[20200723162100796.png]: /images/20221119/71e1c8cf35344f399c2d50b8efad13d3.png
[2020072316220764.png]: /images/20221119/e8334bbe28fb4f23a476562427ecca3f.png
[20200723162543117.png]: /images/20221119/e4a4fdc8c5d94b79b30d62124d81bfae.png
[20200723162753728.png]: /images/20221119/b5b51f6f15b24416b5fdaa1b9aa92100.png
[20200723162842834.png]: /images/20221119/c6da5640e7ed4ada83a46535cc1dc5de.png
[20200723163010196.png]: /images/20221119/b721af2f95414b6c9a977cfe7ddcb622.png
[20200723173916787.gif]: /images/20221119/fc0ded0cc60d4747b8b7d737cb55e8e2.png
[20200724172404718.png]: /images/20221119/70d12da9268b45349817cad7d2407b21.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70 3]: /images/20221119/d04cdc5fa6e3441ca2b9d9326de78800.png
[20200727175814380.gif]: /images/20221119/3f41fc608700441bbcb92bbd4b9844e4.png
[20200727180211850.gif]: /images/20221119/4220fc65ec7e4a179f2956d05fe12f4e.png
[20200727182639753.png]: /images/20221119/107fc1b3ed134d51a61f9bfbb3d6016c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70 4]: /images/20221119/5952b940a1f9492b9355e9d9fb49ba36.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA57eR5rC06ZW35rWBKno_size_25_color_dae8fc_t_70 5]: /images/20221119/f07cfd520c8c40cf957fabd902eba3f3.png