MySQL索引相关原理解析

柔光的暖阳◎ 2022-01-21 10:35 260阅读 0赞

### MySQL索引相关原理解析 ###

*  概述
 *  MySQL索引的数据结构
 *   *  B-Tree和B+Tree
     *   *  B-Tree
         *  B+Tree
         *  总结一下B+Tree和B-Tree
     *  哈希索引
     *  结构特点
     *   *  InnoDB支持哈希索引吗？
     *  聚簇索引和非聚簇索引
     *   *  概念：
         *  回表
         *  覆盖索引
         *  索引树
         *  InnoDB引擎下的表是索引组织表
 *  索引的最左匹配原则
 *   *  复合索引
     *  最左匹配原则
 *  总结

# 概述 #

索引的种类有`聚簇索引`和`聚簇索引`，MySQL中的索引有主键索引、唯一索引、普通索引、全文所以、组合索引，使用索引能够大大提高检索数据行的速度，但是过多的索引又会导致插入删除操作在维护索引上的开销过高。为什么呢？看下文。

# MySQL索引的数据结构 #

理解索引的数据结构至关重要，它决定了索引的特性。在MySQL中索引的实现使用的是B+Tree。

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

## B-Tree和B+Tree ##

*  **概念：** B+Tree中的B是balance，指的是平衡，它叫平衡多路查找树。它是为`磁盘`等外设设备设计的一种`平衡查找树`，磁盘的I/O一直是数据库的瓶颈所在，针对一次增删改查，越少的磁盘I/O就越有利于性能。B+Tree是对B-Tree的一种改进。
 *  **科普一下磁盘的读取机制：** 操作系统将数据的逻辑地址传给磁盘，磁盘解析出物理地址，然后进行寻道，旋转磁盘，将对应的扇区旋转到磁头下，接着开始读取，磁盘每次读取的大小为`页(4k)的整数倍`，内存与磁盘以页为单位交换数据。
 *  **InnoDB中的页：** InnoDB中也有页的概念，InnoDB中默认每个页的大小为16kb，可以通过设置参数innodb\_page\_size来将页的大小设置为4k、8k、16k，即为磁盘页大小的整数倍。

### B-Tree ###

三阶B-Tree（内容参考和图片来自：[https://blog.csdn.net/qq\_21993785/article/details/80576642）][https_blog.csdn.net_qq_21993785_article_details_80576642]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70]

*  图中，磁盘块1，磁盘2…表示的是`InnoDB中的“页”`，在磁盘中的表现形式为连续地址的磁盘页（例如InnoDB中设置页大小为8kb，那么在磁盘中就是两个连续地址的磁盘页）
 *  在B-Tree中，每个非叶子节点磁盘块中存放有

> **指针：** 指向子节点的磁盘地址。  
> **键值对：** key = 记录的主键，value = 表中除了主键以外的数据。

模拟查找主键=75的记录的过程：

> 1.  读取根节点，载入内存。 **【第一次磁盘IO】**
> 2.  比较主键的大小，不为17，不为35，且大于35，获得指向磁盘块4的指针。
> 3.  读取磁盘块4，载入内存。 **【第二次磁盘IO】**
> 4.  比较主键的大小，不为65，不为87，且大于35小于87，获得指向磁盘块10的指针。
> 5.  读取磁盘块10，载入内存。 **【第三次磁盘IO】**
> 6.  比较主键大小，找到主键=75的记录。

B-Tree中的键值对存储了主键和对应的行记录，那么如果行记录中的数据较大，每个磁盘块中能够存储的主键范围就越广，导致整颗B-Tree的深度变大，那么磁盘的IO次数也就会增多，导致性能的下降。  
  
假设每个非叶子磁盘块能存3个键值对时的结构：三阶B-Tree  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 1]当每行记录的数据变大时，假设只能存2两个键值对了，那么可能会多出一层到两层，也就多了一次或两次IO操作。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 2]

### B+Tree ###

B+Tree正是对上一个例子中存在的问题的优化。  
（图片来自：[https://blog.csdn.net/qq\_21993785/article/details/80576642）][https_blog.csdn.net_qq_21993785_article_details_80576642]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 3]

*  **结构：** 对比B-Tree可以发现，在B+数的非叶节点中不再存储数据，所有的数据都存储在叶子节点中。并且最底层的叶子节点是一个双向链表。
 *  **优点：** 非叶子节点只存储指针和主键值以后，每个磁盘块中能够存放的主键数大大增加，那么整颗树会变“胖”，降低了深度，减少IO次数从而提高性能。
 *  **加粗样式**
 *  **推算：**

> InnoDB存储引擎中页的大小为16KB，一般表的主键类型为INT（占用4个字节）或BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree中的一个节点）中大概存储16KB/(8B+8B)=1K个键值（因为是估值，为方便计算，这里的K取值为〖10〗3）。也就是说一个深度为3的B+Tree索引可以维护103 \* 10^3 \* 10^3 = 10亿 条记录。（摘自：[https://blog.csdn.net/qq\_21993785/article/details/80576642）][https_blog.csdn.net_qq_21993785_article_details_80576642]

### 总结一下B+Tree和B-Tree ###

1.  **稳定性更好：** B-Tree中每个节点都有存储数据，那么检索的效率会有波动。B+Tree中则不会，它的数据都在叶子节点。
2.  **效率提高：** 评价一个数据结构作为索引的优劣的重要指标是它进行磁盘I/O的次数，B+Tree对B-Tree的优化在于，只在叶子节点存放数据，那么每个非叶节点能够存放的索引树会大大增加，从而降低 树的深度，减少了磁盘IO次数，从而提高了性能。

## 哈希索引 ##

## 结构特点 ##

参考：（[https://www.cnblogs.com/zengkefu/p/5647279.html）][https_www.cnblogs.com_zengkefu_p_5647279.html]  
  
哈希索引就是采用哈希算法，将主键或者索引的值换算成哈希值，哈希算法不需要像树结构的逐级查找，只需要一次哈希算法就可以立即定位。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 4]

*  与B+ 树对比，如果是通过索引的等值查询，哈希索引有明显的优势。但是如果有大量的重复的键，出现了哈希碰撞比较严重，那么就需要遍历链表，大数据下也是影响性能的。
 *  哈希索引不支持范围查询。因为有序的键在哈希算法后可能就不再连续了，只能够一个一个查询。
 *  **总结：** 总的来说哈希索引的稳定性不如B+Tree，出现了大量哈希碰撞后哈希索引的效率也是极低的。

### InnoDB支持哈希索引吗？ ###

InnoDB默认使用的是B+Tree索引，哈希索引在官方文档中表示无法主动创建，只能是由InnoDB引擎自动优化创建。

## 聚簇索引和非聚簇索引 ##

### 概念： ###

*  **聚簇索引：** 指的是主索引文件和数据文件为同一份文件。
 *  **非聚簇索引：** 指的是B+树的叶子节点上存储的数据并不是行记录中的数据，而是存放主键。  
      
    简单来说：聚簇索引是以主键创建的索引（叶子节点存放的是主键和表中的数据），非聚簇索引是以非主键创建的索引（叶子节点中存放的是索引和主键）。

### 回表 ###

上文中对B+Tree查询的举例正是聚簇索引查询的流程，现在介绍一下非聚簇索引查询的流程：

> 假设表中有id为主键，在学号上建立了唯一索引。那么根据学号查询一条学生信息的流程：
> 
> 1.  在学号索引文件中查询学号对应的主键
> 2.  根据查找到的主键到主键的索引文件中寻找对应的记录。  
>     这个过程叫做`回表`

### 覆盖索引 ###

在回表中讲到，根据非聚簇索引查询后，需要根据查询到的主键再次查找数据。那么如果情况是这样：

> student表，sno为主键，（sname，sage）组成的复合索引。  
> ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 5]

*  **情况1：**

explain select sname,sage from student where sname="bob";

使用复合索引中的sname列作为where条件，并且查询的列为sname和sage都是索引列，查询时将不会回表！而是直接从索引文件中获得所需的列值。这种情况称之为覆盖索引。  
![在这里插入图片描述][20190610111943142.png]

*  **情况二：**

explain select * from student where sname="bob";

此时查询的列为全部，查询时需要进行回表  
![在这里插入图片描述][20190610112212736.png]

*  **总结：**  
    覆盖索引本身并不是一个索引，它指的是查询的列正好与索引本身覆盖，查询时直接从索引文件中获得了值，而不需要进行回表操作。那么如果查询的列中包含了索引中不存在的列，那么就必须回表了。覆盖索引的查询效率要远优于回表，它几乎能减少一半的磁盘IO。

### 索引树 ###

创建多个单列非聚集索引时，MySQL会生成多个索引树，同时在添加删除数据或者对索引列的值进行修改时，就需要对索引文件进行维护，过多的索引会导致维护的成本提高，并且索引文件也占磁盘空间。

### InnoDB引擎下的表是索引组织表 ###

*  在InnoDB中，对表中数据的存储是根据主键的顺序组织存放的，回顾一下主键B+Tree的结构，在叶子节点中主键为Key，行记录为value存储。
 *  在创建InnoDB引擎下的表时，如果没有指定主键，InnoDB会寻找表中是否有非空唯一索引作为主键，如果没有则会自动创建一个主键列。

# 索引的最左匹配原则 #

`索引的最左匹配原则是针对复合索引的`

## 复合索引 ##

*  \*\*概念：\*\*复合索引又叫联合索引，两个或多个列组成的索引称为联合索引。
 *  **联合索引的好处：**

> 1.  `减少磁盘的占用`，建立一个联合索引（a，b，c）相当于建立了（a），（a，b），（a，b，c）三个索引，但是只有一个文件
> 2.  `覆盖索引：` 上文已经提到了
> 3.  `对数据筛选的细粒度更细：` 例如一个有1000W数据的表中执行此SQL
> 
> >     select * from table where a = 1 and b =2 and c = 3;
> 
> 如果a为普通索引，b和c为普通列，那么假设查询时查询索引表过滤出了100W条主键，接着回表根据100W个主键继续筛选b=2，c=3的数据。  
>   
> 如果建立了（a，b，c）联合索引，那么可以直接通过索引筛选出数据。

*  \*\*联合索引的结构：\*\*联合索引的数据结构和其他普通索引是相同的，依然是一颗B+Tree，但是它的键的值有多个，构建一颗B+Tree只能根据一个值来构建，这个值就是联合索引中按顺序最左的那个。假设创建一个（a，b，c）联合索引  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 6]

观察可以发现，a的值是有序的。b的值是无序的2,3,3,3,5,1,2。但是如果在确认a的值的情况下b的值又是有序的：（1,2），（1,3），（1，5）。在确认a和b后c也是有序的（1,3,2），（1,3,3），（1,3,6）。

## 最左匹配原则 ##

*  **概念：** 如果查询的时候查询条件精确地匹配了联合索引的从左开始的连续一列或者几列，那么就可以使用索引。
 *  **不命中索引的情况：** 条件为联合索引时，如果遇到范围查询`（>、<、between、%like向左匹配）`就不能匹配了，将会退化成线性的查找。
 *  概念晦涩，看几个例子就能明白了：
 *  test表结构：id为主键，（name，cid，addr）组成联合索引

DROP TABLE IF EXISTS `test`;
    CREATE TABLE `test` (
      `id` int(11) NOT NULL AUTO_INCREMENT,
      `name` varchar(255) DEFAULT NULL,
      `cid` int(11) DEFAULT NULL,
      `addr` varchar(255) DEFAULT NULL,
      `status` int(11) DEFAULT NULL,
      PRIMARY KEY (`id`),
      KEY `name_cid_index` (`name`,`cid`,`addr`) USING BTREE
    ) ENGINE=InnoDB AUTO_INCREMENT=7 DEFAULT CHARSET=utf8;
    
    -- ----------------------------
    -- Records of test
    -- ----------------------------
    INSERT INTO `test` VALUES ('1', 'aa', '16401', 'beijing', '1');
    INSERT INTO `test` VALUES ('2', 'bb', '16402', 'shanghai', '0');
    INSERT INTO `test` VALUES ('3', 'cc', '16403', 'shenzhen', '1');
    INSERT INTO `test` VALUES ('4', 'dd', '16404', 'hangzhou ', '0');
    INSERT INTO `test` VALUES ('5', 'ee', '16405', 'xiamen', '1');
    INSERT INTO `test` VALUES ('6', 'ff', '16406', 'guangzhou', '1');

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

科普一下explain中的几个字段的含义：

<table> 
 <thead> 
  <tr> 
   <th>字段名</th> 
   <th>值</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>type</td> 
   <td>ALL</td> 
   <td>全表扫描</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>index</td> 
   <td>扫描整颗索引树</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>range</td> 
   <td>扫描部分索引，索引的范围扫描</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>ref</td> 
   <td>使用非唯一索引或非唯一索引的前缀进行的查找</td> 
  </tr> 
  <tr> 
   <td></td> 
   <td>const</td> 
   <td>精确查找，单表中只有一个匹配行，例如主键和唯一索引的查询</td> 
  </tr> 
 </tbody> 
</table>

**情况1：**  
（name，cid，addr）组成联合索引

explain select * from test where name="bb" and cid="16402" and addr="shanghai";

![在这里插入图片描述][20190610153541175.png]按照联合索引顺序完全匹配，查询的步骤为：

> 1.  查询索引树找出name=bb的记录
> 2.  从找出的记录中查找cid=16402的记录
> 3.  再从找出的记录中查找addr=shanghaid的记录的主键
> 4.  回表，根据主键找记录。  
>     在前三步的过程中将会逐步的缩小范围。

下面几条SQL也是同样能使用联合索引

explain select * from test where name="bb" and cid="16402" ;
    explain select * from test where name="bb" ;

正是和概述中的匹配建立一个联合索引（a，b，c）相当于建立了（a），（a，b），（a，b，c）三个索引。  
`需要注意的是，如果将where中的这三个或者两个等值条件的顺序打乱，依然可以通过索引匹配，这是因为在MySQL中有查询优化器，它会纠正判断这条SQL如何执行效率最高，最后才生成执行计划`

//这两条是相同的
    explain select * from test where name="bb" and cid="16402" ;
    explain select * from test where cid="16402" and name="bb" ;

**情况2：**  
（name，cid，addr）组成联合索引

explain select * from test where  cid="16402";

![在这里插入图片描述][20190610154532757.png]执行的是全表扫描，并没有走索引！是因为B+Tree索引是只能由一个列的值来组织，条件中并没有组织树的列值，即便强行从索引树中搜索也是需要遍历整个索引树找到匹配的值的主键，再进行回表。这样的效率还不如直接遍历表数据。

explain select * from test where cid="16402" and addr="shanghai";
    explain select * from test where addr="shanghai";

同理，这两条语句也会通过全表扫描。

\*\*情况3：\*\* （name，cid，addr）组成联合索引 \`\`\`sql explain select \* from test where name="bb" and cid>"16402" and addr="guangzhou"; \`\`\` !\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20190610155409344.png)

重点分析一下这个使用了范围查询的情况。我们来模拟一下执行的过程  
![在这里插入图片描述][20190610155355809.png]

> 1.  从联合索引树中根据name="bb"这个条件寻找符合的项。
> 2.  从符合的项中过滤出cid>16402的项
> 3.  遍历过滤出的项寻找addr="guangzhou"的主键（这一步已经退化成了线性查找）
> 4.  回表，根据找到的主键搜索记录。

很显然在这条SQL中，依次命中了name，cid，无法命中addr。因为name值的确定的，那么cid是相对有序的，而语句中取了cid>16402，那么在这个范围内的addr是无序的，因此addr无法匹配索引，只能将范围内的所有值进行逐一比较。

如果还是不理解，结合一个简单的图。这是一个（a，b，c）的组合索引树 !\[在这里插入图片描述\](https://img-blog.csdnimg.cn/20190610175736495.png?x-oss-process=image/watermark,type\_ZmFuZ3poZW5naGVpdGk,shadow\_10,text\_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ==,size\_16,color\_FFFFFF,t\_70) 结合图看以下例子。 \`\`\`sql select \* from table where a>0 and b=1; \`\`\` 这样的一条语句中只有a是使用索引的，b无法使用。原因在于a>0的范围内b是无序的。结合结构图，如果需要确认B=1的记录需要遍历整个索引树，逐一对比b的值，然后再根据索引树中获得的主键回表逐一查询。

那么如果是这样一条语句：

select * from table where a=1 and b>2;

这条语句中，a和b都能够根据索引获取，原因在于确定了a的值后，b的值是有序的，那么获取索引b指定范围内的记录就十分容易了。

修改上一条的语句为：

select * from table where a=1 and b>2 and c=3;

这条语句中，a和b 可以使用索引，但是c不行，原因在于b>2的记录范围内3是无序的，需要遍历对比。

*  **like：**  
    使用like也会影响索引的匹配

//这相当于精确匹配，可以走索引
    select * from table where a like 'g';

// 匹配a列中以g开头的记录，可以走索引
    select * from table where a like 'g%';

// 匹配a列中以g结尾的记录，不走索引
    select * from table where a like '%g';

// 匹配a列中含有g的记录，不可以走索引
    select * from table where a like '%g%';

emmmm原理还没摸清

# 总结 #

*  **最做前缀原则**。回顾在本节开头时提到的遇到范围查询(>、<、between、like左匹配)后的条件就不能使用索引匹配了，本质的原因是`在遇到了这些范围查询以后的条件的列值是乱序的`，导致只能遍历所有范围内的结果。
 *  **使用区分度高的列做索引。** 重复的越少需要扫描的记录也就越少。
 *  索引列不能参与计算，尽量保持列“干净”。比如，FROM\_UNIXTIME(create\_time) = ‘2016-06-06’ 就不能使用索引，原因很简单，B+树中存储的都是数据表中的字段值，但是进行检索时，需要把所有元素都应用函数才能比较，显然这样的代价太大。所以语句要写成 ： create\_time = UNIX\_TIMESTAMP(‘2016-06-06’)。
 *  **尽可能扩展索引**，而不是添加索引，索引过多导致磁盘占用大，维护成本高。

参考资料： https://juejin.im/post/5b55b842f265da0f9e589e79\#heading-9

[https_blog.csdn.net_qq_21993785_article_details_80576642]: https://blog.csdn.net/qq_21993785/article/details/80576642%EF%BC%89
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70]: /images/20220121/23596e1f166b4efc98b2bacdaf3f0816.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 1]: /images/20220121/5fe7a956574742c1acc780e9295ca4ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 2]: /images/20220121/cbf4335f1b734d57aeeac30de88653ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 3]: /images/20220121/87708024a33846ec9d4dfe77db6b4ba6.png
[https_www.cnblogs.com_zengkefu_p_5647279.html]: https://www.cnblogs.com/zengkefu/p/5647279.html%EF%BC%89
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 4]: /images/20220121/02ed066d7c0a417386e18079b54dfa4e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 5]: /images/20220121/231fc9c1ac25470aa3914db3ef04a277.png
[20190610111943142.png]: /images/20220121/2f5eea66ce854c5197e59b7c57a1f018.png
[20190610112212736.png]: /images/20220121/461215be1a214556816fcb0557c3fd9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzE4NDc2OQ_size_16_color_FFFFFF_t_70 6]: /images/20220121/3ed6b5e8153d49119d37b53ab6204dc9.png
[20190610155349500.png]: /images/20220121/f83a72705cd44b96b4e9e86a3d6788cc.png
[20190610153541175.png]: /images/20220121/e55894eec3624c9c8bff14273094edc9.png
[20190610154532757.png]: /images/20220121/32b014bf47554fafa50a3fa7a528b9f4.png
[20190610155355809.png]: /images/20220121/14f49da3df484a77851d066e26b3f84c.png