MySQL面试：最左前缀匹配原则

Bertha 。 2022-09-16 12:22 208阅读 0赞

>  *  如果为每一种查询都设计一个索引，索引是不是太多了。如果我需要按照市民的身份证号去查询他的家庭地址呢？虽然这个查询需求在业务中出现的概率不高，但总不能让它走全表扫描吧？反过来说，单独为一个不频繁的请求创建一个索引有感觉有点浪费。应该怎么做呢？
>  *  这就是“最左前缀索引”的应用场景：B+树这种索引结构，可以利用索引的“最左前缀”，来定位记录

# 回答 #

*  首先，需要明确的是：**最左前缀原则是发生在复合索引上的，只有复合索引才会有所谓的左和右之分**
 *  在MySQL建立联合索引时会遵守最左前缀匹配原则，即最左优先，**在检索数据时从联合索引的最左边开始匹配**

mysql 建立多列索引（联合索引）有最左前缀的原则，即最左优先，如：

*  如果有一个 2 列的索引 (col1, col2)，则已经对 (col1)、(col1, col2) 上建立了索引；
 *  如果有一个 3 列索引 (col1, col2, col3)，则已经对 (col1)、(col1, col2)、(col1, col2, col3) 上建立了索引；

当 select \* from T where a = 1 and b = 3 的时候， 数据库系统可以直接从索引文件中直接二分法找到 A = 1 的记录，然后再 B = 3 的记录

但如果你 where b = 3 则需要遍历这个索引表的全部

有一个复合索引：INDEX(a, b, c)
    
    使用方式 能否用上索引
    select * from users where a = 1 and b = 2 能用上a、b
    select * from users where b = 2 and a = 1 能用上a、b（有MySQL查询优化器）
    select * from users where a = 2 and c = 1 能用上a
    select * from users where b = 2 and c = 1 不能
    
    解释：其实就像是闯关，只有第一关打通了，才能打第二关，第一关和第二关都过了才能打第三关，所以在设计索引的时候要把最常用的放在最左边

## 原理 ##

*  B+树的数据项是复合的数据结构，比如 (name,age,sex) 的时候，B+树是按照从左到右的顺序来建立索引树的，比如当(张三,20,F) 这样的数据来检索的时候，B+树就优先比较name来确定下一步的搜索方向，如果name相同则再依次比较age和sex，最后得到检索到的数据；但当（20，F）这样的没有name的数据来的时候，B+树就不知道第一步应该检查哪个节点，因为建立搜索树的时候name就是第一个比较因子，必须要先根据name来搜索才能知道下一步去哪里查询
 *  比如当（张三，F）这样的数据来检索时，b+树可以用name来指定搜索方向，但下一个字段age的缺失，所以只能把名字等于张三的数据来找到，然后再匹配性能是F的数据了，这个是非常重要的性质，即索引的最左匹配特性。（这种情况无法用到联合索引）

> 索引的底层原理

要想理解联合索引的最左匹配原则，先来理解下索引的底层原理。**索引的底层是一颗B+树，那么联合索引的底层也就是一颗B+树，只不过联合索引的B+树节点中存储的是键值**。**由于构建一棵B+树只能根据一个值来确定索引关系，所以数据库依赖联合索引最左的字段来构建**。

举例：创建一个（a, b）的连接索引，那么它的索引树就是下面这个样子：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_16_color_FFFFFF_t_70_g_se_x_16]  
可以看到a的值是有顺序的，1，1，2，2，3，3，而b的值是没有顺序的1，2，1，4，1，2。但是我们又可以发现a在等值的情况下，b值又是按照顺序排列的，但是这种顺序是相对的。这是因为**MySQL创建联合索引的规则是首先会对联合索引的最左边第一个字段排序，在第一个字段的排序基础上，然后对第二个字段进行排序**。所以b=2这种查询条件没有办法利用索引。

## mysql ##

如果建立的索引是(name, cid)。而查询的语句是 cid=1 AND name=’小红’。为什么还能利用到索引？

当按照索引中的所有列进行精确匹配（“=” 或 “IN”）时，索引可以被用到，并且type为const。理论上索引对顺序是敏感的，但是由于MySQL的查优化器会自动调整where子句的条件顺序以使用合适的索引，所以MySQL不存在where子句的顺序问题而造成索引失效

## 注意事项 ##

> 范围查询

mysql会一直向右匹配直到遇到范围查询（>、<、between、like）就停止匹配。范围列可以用到索引，但是范围列后面的列无法用到索引。即，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引

> like语句的索引问题

如果通配符 % 不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀  
在 like “value%” 可以使用索引，但是 like “%value%” 不会使用索引，走的是全表扫描

> 不要在列上进行运算

如果查询条件中含有函数或者表达式，将导致索引失效而进行全表查询。

例如`select * from user where YEAR(birthday) < 1990`  
可以改造成`select * from users where birthday <’1990-01-01′`

> 索引不会包含NULL值的列

只要列中包含有 NULL 值都将不会被包含在索引中，复合索引中只要有一列含有 NULL 值，那么这一列对于此复合索引就是无效的。**所以在数据库设计时不要让字段的默认值为 NULL**

> 尽量选择区分度高的列作为索引

区分度的公式是 count(distinct col)/count(\*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是 1，而一些状态、性别字段可能在大数据面前区分度就是 0。一般需要 join 的字段都要求区分度 0.1 以上，即平均 1 条扫描 10 条记录

## 问题：在建立联合索引的时候，如何安排索引内的字段顺序 ##

这里我们的评估标准是，索引的复用能力。因为可以支持最左前缀，所以当已经有了(a，b)这个联合索引之后，一般就不需要单独在 a 上建立索引了。因此，**第一原则是，如果通过调整顺序，可以少维护一个索引，那么这个顺序往往就是需要优先考虑采用的**。

那么，如果既有联合查询，又有基于a、b各自的查询呢？查询条件里面只有b的语句，是无法使用（a，b）这个联合索引的，这时候就需要维护另外一个索引，也就是说你需要同时维护 (a,b)、(b) 这两个索引。

这时候，我们要考虑的原则就是空间了。比如市民表中，name 字段是比age 字段大的 ，因此建议创建一个（name,age) 的联合索引和一个 (age) 的单字段索引。

# 实例 #

## 准备 ##

由于整个过程是基于explain结果分析的，那接下来在了解下explain中的type字段和key\_lef字段。

*  type：联接类型。下面给出各种联接类型,按照从最佳类型到最坏类型进行排序:（重点看ref,rang,index）
    
     *  system：表只有一行记录（等于系统表），这是const类型的特例，平时不会出现，可以忽略不计
     *  const：表示通过索引一次就找到了，const用于比较primary key 或者 unique索引。因为只需匹配一行数据，所有很快。如果将主键置于where列表中，mysql就能将该查询转换为一个const
     *  eq\_ref：唯一性索引扫描，对于每个索引键，表中只有一条记录与之匹配。常见于主键 或 唯一索引扫描。
     *  ref：非唯一性索引扫描，返回匹配某个单独值的所有行。本质是也是一种索引访问，它返回所有匹配某个单独值的行，然而他可能会找到多个符合条件的行，所以它应该属于查找和扫描的混合体。
     *  range：只检索给定范围的行，使用一个索引来选择行。key列显示使用了那个索引。一般就是在where语句中出现了bettween、<、>、in等的查询。这种索引列上的范围扫描比全索引扫描要好。只需要开始于某个点，结束于另一个点，不用扫描全部索引。
     *  index：Full Index Scan，index与ALL区别为index类型只遍历索引树。这通常为ALL块，应为索引文件通常比数据文件小。（Index与ALL虽然都是读全表，但index是从索引中读取，而ALL是从硬盘读取）
     *  ALL：Full Table Scan，遍历全表以找到匹配的行

*  key\_len：显示MySQL实际决定使用的索引的长度。如果索引是NULL，则长度为NULL。如果不是NULL，则为使用的索引的长度。所以通过此字段就可推断出使用了那个索引。计算规则：
    
     *  定长字段，int占用4个字节，date占用3个字节，char(n)占用n个字符。
     *  变长字段varchar(n)，则占用n个字符+两个字节。
     *  不同的字符集，一个字符占用的字节数是不同的。Latin1编码的，一个字符占用一个字节，gdk编码的，一个字符占用两个字节，utf-8编码的，一个字符占用三个字节。
     *  对于所有的索引字段，如果设置为NULL，则还需要1个字节。

## 开始 ##

首先创建一个表

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

该表中对id列.name列.age列建立了一个联合索引 id\_name\_age\_index，实际上相当于建立了三个索引（id）（id\_name）（id\_name\_age）。

下面介绍下可能会使用到该索引的几种情况：

### 全值匹配查询时 ###

![在这里插入图片描述][a9508a3fc54d4a4993df75e2e24d3ea8.png]  
![在这里插入图片描述][adac1fdee71f4388bbfb346aa7ba2d29.png]  
![在这里插入图片描述][b6b7021e4d4547bbadbdec8743421100.png]

通过观察上面的结果图可知，where后面的查询条件，不论是使用（id，age，name）（name，id，age）还是（age，name，id）顺序，在查询时都使用到了联合索引，可能有同学会疑惑，为什么底下两个的搜索条件明明没有按照联合索引从左到右进行匹配，却也使用到了联合索引？

*  这是因为MySQL中有查询优化器explain，所以sql语句中字段的顺序不需要和联合索引定义的字段顺序相同，查询优化器会判断纠正这条SQL语句以什么样的顺序执行效率高，最后才能生成真正的执行计划，所以不论以何种顺序都可使用到联合索引
 *  另外通过观察上面三个图中的key\_len字段，也可说明在搜索时使用的联合索引中的（id\_name\_age）索引，因为id为int型，允许null，所以占5个字节，name为char(10)，允许null，又使用的是latin1编码，所以占11个字节，age为int型允许null，所以也占用5个字节，所以该索引长度为21（5+11+5），而上面key\_len的值也正好为21，可证明使用的（id\_name\_age）索引。

### 匹配最左边的列时 ###

![在这里插入图片描述][d5fb3a4806fd4e0e803f9c5957ba8999.png]  
　该搜索是遵循最左匹配原则的，通过key字段也可知，在搜索过程中使用到了联合索引，且使用的是联合索引中的（id）索引，因为key\_len字段值为5，而id索引的长度正好为5（因为id为int型，允许null，所以占5个字节）  
![在这里插入图片描述][518b871651aa419c946fee91ebd74e49.png]  
由于id到name是从左边依次往右边匹配，这两个字段中的值都是有序的，所以也遵循最左匹配原则，通过key字段可知，在搜索过程中也使用到了联合索引，但使用的是联合索引中的（id\_name）索引，因为key\_len字段值为16，而(id\_name)索引的长度正好为16（因为id为int型，允许null，所以占5个字节，name为char(10)，允许null，又使用的是latin1编码，所以占11个字节）。  
![在这里插入图片描述][89cb6396ca824b56b4b16f2b574bee7e.png]  
由于上面三个搜索都是从最左边id依次向右开始匹配的，所以都用到了id\_name\_age\_index联合索引。

那如果不是依次匹配呢？  
![在这里插入图片描述][7674248478824047ae3b0b6e223f9026.png]  
通过key字段可知，在搜索过程中也使用到了联合索引，但使用的是联合索引中的（id）索引，从key\_len字段也可知。因为联合索引树是按照id字段创建的，但age相对于id来说是无序的，只有id只有序的，所以他只能使用联合索引中的id索引。  
![在这里插入图片描述][9cce5903fc05402fb94e450405148186.png]  
通过观察发现上面key字段发现在搜索中也使用了id\_name\_age\_index索引，可能许多同学就会疑惑它并没有遵守最左匹配原则，按道理会索引失效，为什么也使用到了联合索引？因为没有从id开始匹配，且name单独来说是无序的，所以它确实不遵循最左匹配原则，然而从type字段可知，它虽然使用了联合索引，但是它是对整个索引树进行了扫描，正好匹配到该索引，与最左匹配原则无关，一般只要是某联合索引的一部分，但又不遵循最左匹配原则时，都可能会采用index类型的方式扫描，但它的效率远不如最做匹配原则的查询效率高，index类型类型的扫描方式是从索引第一个字段一个一个的查找，直到找到符合的某个索引，与all不同的是，index是对所有索引树进行扫描，而all是对整个磁盘的数据进行全表扫描。  
![在这里插入图片描述][937489461a3f4224aec10ecbe5b40a89.png]  
![在这里插入图片描述][b75b87c80c1e4fefa7b4150e9b94438a.png]  
这两个结果跟上面的是同样的道理，由于它们都没有从最左边开始匹配，所以没有用到联合索引，使用的都是index全索引扫描。

## 匹配列前缀 ##

如果id是字符型，那么前缀匹配用的是索引，中坠和后缀用的是全表扫描。

select * from staffs where id like 'A%';//前缀都是排好序的，使用的都是联合索引
    select * from staffs where id like '%A%';//全表查询
    select * from staffs where id like '%A';//全表查询

## 匹配范围值 ##

![在这里插入图片描述][3fd5f827976c422bb8000771e120f0a0.png]  
在匹配的过程中遇到<>=号，就会停止匹配，但id本身就是有序的，所以通过possible\_keys字段和key\_len 字段可知，在该搜索过程中使用了联合索引的id索引（因为id为int型，允许null，所以占5个字节），且进行的是rang范围查询。  
![在这里插入图片描述][643c75928f504aa8af876a05e1ca9270.png]  
由于不遵循最左匹配原则，且在id<4的范围中，age是无序的，所以使用的是index全索引扫描。

![在这里插入图片描述][f79425d4b9104335adb619446381563c.png]  
不遵循最左匹配原则，但在数据库中id<2的只有一条（id），所以在id<2的范围中，age是有序的，所以使用的是rang范围查询。

![在这里插入图片描述][5c259c6e50b34bc1b5be6ce0ffd2cec1.png]  
不遵循最左匹配原则，而age又是无序的，所以进行的全索引扫描

## 准确匹配第一列并范围匹配其他某一列 ##

![在这里插入图片描述][cfe6400f2a0748e895e3afa7f05d00a0.png]  
由于搜索中有id=1，所以在id范围内age是无序的，所以只使用了联合索引中的id索引。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/adaa947bc7f14e639cea38adcbac1ec5.png
[dec2234212264a699017e8a3f484b661.png]: /images/20220828/d1401248b32a4093aaf2fce546b7268f.png
[a9508a3fc54d4a4993df75e2e24d3ea8.png]: /images/20220828/61d0b68817a547fdb0d710286ac61568.png
[adac1fdee71f4388bbfb346aa7ba2d29.png]: /images/20220828/3105def567414c87901a40a81615c650.png
[b6b7021e4d4547bbadbdec8743421100.png]: /images/20220828/f590584335b24c0d910ea2960cdf08c9.png
[d5fb3a4806fd4e0e803f9c5957ba8999.png]: /images/20220828/fa62ba891daf4c8182200af77ef57c99.png
[518b871651aa419c946fee91ebd74e49.png]: /images/20220828/eb2fa6273b5a4c758489a43c29a4ad2d.png
[89cb6396ca824b56b4b16f2b574bee7e.png]: /images/20220828/2e8ea26adafa4be1b398509f1d345d91.png
[7674248478824047ae3b0b6e223f9026.png]: /images/20220828/01abd1316d3e410d8fe387203d3e3332.png
[9cce5903fc05402fb94e450405148186.png]: /images/20220828/3d9adeb813914ca09828341302408847.png
[937489461a3f4224aec10ecbe5b40a89.png]: /images/20220828/510269ba2b804f6c9236371536b4c40c.png
[b75b87c80c1e4fefa7b4150e9b94438a.png]: /images/20220828/c3d72a8e3977415ea2a3c0018cdc5f48.png
[3fd5f827976c422bb8000771e120f0a0.png]: /images/20220828/3584f773127b4d0dba07be6bb2863c8c.png
[643c75928f504aa8af876a05e1ca9270.png]: /images/20220828/22f41ed885e24bd9af51d07a0932cc60.png
[f79425d4b9104335adb619446381563c.png]: /images/20220828/6946f2c4446945329bf64f4c943e7f0b.png
[5c259c6e50b34bc1b5be6ce0ffd2cec1.png]: /images/20220828/5552649708184d96a9ba026986f7a9fa.png
[cfe6400f2a0748e895e3afa7f05d00a0.png]: /images/20220828/2d33a604c2a841cf9c7b960376d17c99.png