彻底搞定Mysql索引

Myth丶恋晨 2022-12-05 00:56 176阅读 0赞

### 彻底搞定Mysql索引 ###

*   *  1.B+树索引
     *   *  没有索引的查找
         *  在一个页中的查找
         *  在很多页中查找
     *  2. 聚簇索引
     *  3. 二级索引
     *  4. 联合索引
     *  5. 扩展
     *  6. 总结

以前写过一篇关于Mysql的文章，但是只是介绍一下索引的用法，也总结了一些mysql索引类型的区别，但是总是感觉不够详尽，也没有详细了解我们创建一个索引Mysql的存储引擎到底做了什么？下面就通过这篇文章，把Mysql索引一网打尽。

首先要知道Mysql的磁盘存储方式，如果不懂的话，那你需要先看下我的另一篇文章：[MySQL磁盘存储][MySQL]

## 1.B+树索引 ##

上一章我们已经讨论了Mysql在磁盘中的存储格式，知道了数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大顺序组成一个单项链表，每个数据页都会为存储在它里面的记录生成一个页目录（page directory）、最小记录和最大记录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。页和记录的关系示意图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center]  
其中页a、页b、页c … 页n 这些页可以不在物理结构上相连，只要通过双向链表相关联即可。

### 没有索引的查找 ###

我们先假设没有索引的概念，然后看看通过条件对某个列进行精确匹配查询的情况：

SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

### 在一个页中的查找 ###

假设目前表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：

**以主键为搜索条件**  
这个查找过程我们已经很熟悉了，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

**以其他列作为搜索条件**  
对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。

### 在很多页中查找 ###

大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：

**定位到记录所在的页。**  
**从所在的页内中查找相应的记录。**  
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，\*\*由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。\*\*因为要遍历所有的数据页，所以这种方式显然是超级耗时的，如果一个表有一亿条记录，使用这种方式去查找记录那要等到猴年马月才能等到查找结果。所以祖国和人民都在期盼一种能高效完成搜索的方法，索引同志就要亮相登台了。

## 2. 聚簇索引 ##

为了故事的顺利发展，我们先建一个表：

mysql> CREATE TABLE index_demo(
        ->     c1 INT,
        ->     c2 INT,
        ->     c3 CHAR(1),
        ->     PRIMARY KEY(c1)
        -> ) ROW_FORMAT = Compact;
    Query OK, 0 rows affected (0.03 sec)

这个新建的index\_demo表中有2个INT类型的列，1个CHAR(1)类型的列，而且我们规定了c1列为主键，这个表使用Compact行格式来实际存储记录的。为了我们理解上的方便，我们简化了一下index\_demo表的行格式示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 1]  
我们只在示意图里展示记录的这几个部分：

*  record\_type：记录头信息的一项属性，表示记录的类型，0表示普通记录、`1表示B+树目录记录（索引就是用它标记，后面会说）`、2表示最小记录、3表示最大记录
 *  next\_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，为了方便大家理解，我们都会用箭头来表明下一条记录是谁。
 *  各个列的值：这里只记录在index\_demo表中的三个列，分别是c1、c2和c3。
 *  其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

下面把一些记录放到页里边的示意图就是：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 2]  
**一个简单的索引方案**  
回到正题，我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？\*\*因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以 不得不 依次遍历所有的数据页。\*\*所以如果我们想快速的定位到需要查找的记录在哪些数据页中该咋办？还记得我们为根据主键值快速定位一条记录在页中的位置而设立的页目录么？我们也可以想办法为快速定位记录所在的数据页而建立一个别的目录，建这个目录必须完成下边这些事儿：  
**1. 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。**  
**2. 给所有的页建立一个目录项。**  
为了更直观的展示，我们为index\_demo表插入一些数据，并且假设每个数据页最多能存放3条记录，数据如下：

mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
    Query OK, 3 rows affected (0.01 sec)
    Records: 3  Duplicates: 0  Warnings: 0

那么这些记录已经按照主键值的大小串联成一个单向链表了，如图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 3]  
从图中可以看出来，index\_demo表中的3条记录都被插入到了编号为10的数据页中了。此时我们再来插入一条记录：

mysql> INSERT INTO index_demo VALUES(4, 4, 'a');
    Query OK, 1 row affected (0.00 sec)

因为页10最多只能放3条记录，所以我们不得不再分配一个新页：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 4]  
上面已经满足第一个条件也就是：**下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。**

为了数据更多，我们再接着插入几条数据，效果图如下：

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

下面来为这些数据页建立一个目录项：因为要比较大小来确定要查找的记录在哪个数据页中，所以每个目录项需要包含两部分：数据页编码+最小记录  
做好后的目录就像下面这个样子：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 6]  
这样就能通过主键值快速定位到数据所在的数据页，然后通过数据页中页目录定位到这个数据。

但是上面这样做有个问题，那就是当数据量很大时，数据页会非常多，这些目录项存在哪里呢？其实不知道你们发现了没有，目录项数据和我们自己插入的用户记录数据有什么相似之处，是的，\*\*目录项其实长得跟我们的用户记录差不多，只不过目录项中的两个列是主键和页号而已，所以可以复用之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。\*\*在InnoDB中使用record\_type来进行标识：

*  0：普通的用户记录
 *  1：目录项记录
 *  2：最小记录
 *  3：最大记录  
    哈哈，原来这个值为1的record\_type是这个意思呀，我们把前边使用到的目录项放到数据页中的样子就是这样：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 7]  
    为了更形象，我们再添加一些数据：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 8]  
    当目录项数据很多时，可以再向上扩展一层目录项，结构如下图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 9]  
    经过数据量的不断扩大，最终目录项的结构就成了下面这个样子：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 10]  
    看到这个结构你想起了吗？是不是和B+树很相似，不用怀疑，它就是B+树，**树的非叶子节点存放的是页号+主键最小值，也就是索引（其实非叶子节点就是索引页），叶子节点是数据页，存放具体的数据记录。**

## 3. 二级索引 ##

上面我们讨论了聚簇索引也就是主键索引，下面我们再来看下二级索引。

大家有木有发现，上边介绍的聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该咋办呢？难道只能从头到尾沿着链表依次遍历记录么？

不，我们可以多建几棵B+树，不同的B+树中的数据采用不同的排序规则。比方说我们用c2列的大小作为数据页、页中记录的排序规则，再建一棵B+树，效果如下图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 11]  
这个B+树与上边介绍的聚簇索引有几处不同：

*  使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：
    
     *  页内的记录是按照c2列的大小顺序排成一个单向链表。
     *  各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表。
     *  存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。
 *  B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
 *  目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。

所以如果我们现在想通过c2列的值查找某些记录的话就可以使用我们刚刚建好的这个B+树了。以查找c2列的值为4的记录为例，查找过程如下：

1.  确定目录项记录页  
    根据根页面，也就是页44，可以快速定位到目录项记录所在的页为页42（因为2 < 4 < 9）。
2.  通过目录项记录页确定用户记录真实所在的页。  
    在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2 < 4 ≤ 4，所以确定实际存储用户记录的页在页34和页35中。
3.  在真实存储用户记录的页中定位到具体的记录。  
    到页34和页35中定位到具体的记录。
4.  但是这个B+树的叶子节点中的记录只存储了c2和c1（也就是主键）两个列，所以我们**必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。**

分析了二级索引的创建和查找过程我们发现有几点不同之处：  
5. **二级索引是根据需要创建的列进行排序，而不是主键**。  
6. B+树的**非叶子节点存储的记录的主键ID,而不是真实数据**，所以需要根据主键ID去聚簇索引中查一次，也就是**回表**操作。

## 4. 联合索引 ##

上面介绍了聚簇索引和二级索引，还有一种不同的索引就是联合索引，下面再来看看它是怎么实现的。  
其实还是和上面的二级索引一样，只是把排序的列从一个非主键列变成了多个非主键列，也就是同时为多个列建立索引，比方说我们想让B+树按照c2和c3列的大小进行排序，这个包含两层含义：

*  先把各个记录和页按照c2列进行排序。
 *  在记录的c2列相同的情况下，采用c3列进行排序  
    为c2和c3列建立的索引的示意图如下：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 12]  
    如图所示，我们需要注意一下几点：
 *  每条目录项记录都由c2、c3、页号这三个部分组成，各条记录先按照c2列的值进行排序，如果记录的c2列相同，则按照c3列的值进行排序。
 *  B+树叶子节点处的用户记录由c2、c3和主键c1列组成。

千万要注意一点，以c2和c3列的大小为排序规则建立的B+树称为联合索引，它的意思与分别为c2和c3列分别建立索引的表述是不同的，不同点如下：

*  建立联合索引只会建立如上图一样的1棵B+树。
 *  为c2和c3列分别建立索引会分别以c2和c3列的大小为排序规则建立2棵B+树。

到这里我们可以就可以知道，**联合索引其实和二级索引相似，只是在排序的时候引入了多个列参加排序而已。**

## 5. 扩展 ##

通过上面的介绍大家都明白了InnoDB索引的实现原理，那你能想象到MyISM的索引是怎么实现的吗？  
其实是类似的，不同的是MyISM没有聚簇索引，它是把数据都存入一个数据文件中，索引记录的都是这个记录在数据文件中的位置，也就是说MyISM的索引其实都是二级索引。

## 6. 总结 ##

1.对于InnoDB存储引擎来说，在单个页中查找某条记录分为两种情况：

*  以主键为搜索条件，可以使用Page Directory通过二分法快速定位相应的用户记录。
 *  以其他列为搜索条件，需要按照记录组成的单链表依次遍历各条记录。

2.没有索引的情况下，不论是以主键还是其他列作为搜索条件，只能沿着页的双链表从左到右依次遍历各个页。

3.InnoDB存储引擎的索引是一棵B+树，完整的用户记录都存储在B+树第0层的叶子节点，其他层次的节点都属于内节点，内节点里存储的是目录项记录。InnoDB的索引分为两大种：

*  聚簇索引  
    以主键值的大小为页和记录的排序规则，在叶子节点处存储的记录包含了表中所有的列。
 *  二级索引  
    以自定义的列的大小为页和记录的排序规则，在叶子节点处存储的记录内容是列 + 主键。

4.MyISAM存储引擎的数据和索引分开存储，这种存储引擎的索引全部都是二级索引，在叶子节点处存储的是列 + 页号。

[MySQL]: https://blog.csdn.net/jiang18238032891/article/details/108475393
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/913fb1c74d8840c7aab1913bf692bd01.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/bd886a945d1140828ed6cc90b1aba0de.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/959c08114d69443c9a787858646b1064.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/ae0d9faa8f824bf19ceff401210ab7d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/55b28fd524c349268bfcfc8b9afa87bc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/2def5f014b6a400ba8415abec7137513.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221123/5174ccb4c4f5465ca883b8e916fbc3b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221123/a66f89057a034f99b9b4f480cf119784.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221123/bb9a7387bf11426db364fb2b43c72218.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221123/1b89301751a24b4898e24fbca89730bd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221123/756cd0afc30443b09c04e54ee4cdeb84.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221123/907e4348ca5945f6a2205b852c5ce166.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ppYW5nMTgyMzgwMzI4OTE_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221123/29144bf3b0b845049a33c82b8786a4cc.png