理解Mysql索引原理及特性 | 京东物流技术团队

原创
2023/12/13 09:46
阅读数 2.1K

作为开发人员,碰到了执行时间较长的sql时,基本上大家都会说”加个索引吧”。但是索引是什么东西,索引有哪些特性,下面和大家简单讨论一下。

1 索引如何工作,是如何加快查询速度

索引就好比书本的目录,提高数据库表数据访问速度的数据库对象。当我们的请求打过来之后,如果有目录,就会快速的定位到章节,再从章节里找到数据。如果没有目录,如大海捞针一般,难度可见一斑。这就是我们经常碰到的罪魁祸首,全表扫描。

一条索引记录中包含的基本信息包括:键值(即你定义索引时指定的所有字段的值)+逻辑指针(指向数据页或者另一索引页)。通常状况下,由于索引记录仅包含索引字段值(以及4-9字节的指针),索引实体比真实的数据行要小许多,索引页相较数据页来说要密集许多。一个索引页可以存储数量更多的索引记录,这意味着在索引中查找时在I/O上占很大的优势,理解这一点有助于从本质上了解使用索引的优势,也是大部分性能优化所需要切入的点。

1)没有索引的情况下访问数据:

2)使用平衡二叉树结构索引的情况下访问数据:

第一张图没有使用索引我们会进行顺序查找,依照数据顺序逐个进行匹配,进行了5次寻址才查询出所需数据,第二张图用了一个简单的平衡二叉树索引之后我们只用了3次,这还是数据量小的情况下,数据量大了效果更明显,所以总结来说创建索引就是为了加快数据查找速度;

2 索引的组成部分和种类

常见的索引的实现方式有很多种,比如hash、数组、树,下面为大家介绍下这几种模型使用上有什么区别

2.1 hash

hash思路简单,就是把我们插入的key通过hash函数算法(以前一般是取余数,就好比hashmap的计算方式移位异或之类的),计算出对应的value,把这个value放到一个位置,这个位置叫做哈希槽。对应磁盘位置指针放入hash槽里面。一句话总结hash索引,就是存储了索引字段的hash值和数据所在磁盘文件指针。

但是不可避免的是,无论什么算法,数据量大了之后难免会出现不同的数据被放在一个hash槽里面。比如字典上的 “吴”和”武”就是同音,你查字典的时候到这里只能顺序往下去找了。索引的处理也是这样,会拉出一个链表,需要的时候顺序遍历即可。

  • 缺点:无序索引,区间查询性能低,因为区间查询会造成多次访问磁盘,多次io耗时是很难接受的。
  • 优点:insert迅速,只需往后补就行
  • 场景:等值查询, 比如memcached 。不适用大量重复数据的列,避免hash冲突
  • 总结:想成java的hashmap即可

2.2 有序数组

如果我们需要区间查询的时候,hash索引的性能就不尽如人意了。这个时候有序数组的优势就能体现出来了。

当我们需要从一个有序数组里取A和B之间的值时,只需要通过二分法定位到A的位置,时间复杂度O(log(N)),接着从A遍历到B即可,论速度的话,基本上可以说是最快的了。但是当我们需要更新的时候,需要进行的操作就很多了。如果需要插入一条数据,你需要挪动数据之后的所有数据,浪费性能。所以总结来说,只有不怎么变化的数据适合有序数组结构的索引。

  • 缺点:insert新数据的时候,需要改变后续所有数据,成本略高。
  • 优点:查询速度很快,理论最大值。
  • 场景:归档查询,日志查询等极少变化的
  • 总结:就是顺序排的数组

2.3 二叉搜索树

基本原则是树的左节点都小于父节点,右节点都大于父节点

这里我们就能看出来,二叉搜索树的查询效率原则上是O(log(N)),为了保证是平衡二叉树,更新效率也是O(log(N))。但是数据很多的情况树的高度会达到很高,过多次访问磁盘,是不可取的。并且极端情况下,树退化成链表,查询的复杂度会被拉成O(n)。

进化成多叉树,也就是多个子节点的时候,会大大的减少树的高度,降低访问磁盘。

  • 缺点:数据量大的时候,树会过高,导致多次访问磁盘
  • 优点:进化成多叉树,会降低树高,访问磁盘次数。
  • 场景:适用很多场景
  • 总结:左小右大的树

2.4 B树

在每个节点存储多个元素,在每个节点尽可能多的存储数据。每个节点可以存储1000个索引(16k/16=1000),这样就将二叉树改造成了多叉树,通过增加树的叉树,将树从高瘦变为矮胖。构建1百万条数据,树的高度只需要2层就可以(1000*1000=1百万),也就是说只需要2次磁盘IO就可以查询到数据。磁盘IO次数变少了,查询数据的效率也就提高了。

这种数据结构我们称为B树,B树是一种多叉平衡查找树

2.5 B+树

B+树和B树最主要的区别在于非叶子节点是否存储数据的问题。

  • B树:非叶子节点和叶子节点都会存储数据。
  • B+树:只有叶子节点才会存储数据,非叶子节点至存储键值。叶子节点之间使用双向指针连接,最底层的叶子节点形成了一个双向有序链表。

正是因为B+树的叶子节点是通过链表连接的,所以找到下限后能很快进行区间查询,比正常的中序遍历快

3 索引的维护

当你insert一条数据的时候,索引需要做出必要的操作来保证数据的有序型。一般自增数据直接在后面加就行了,特殊情况下如果数据加到了中间,就需要挪动后面所有的数据,这样效率比较受影响。

最糟糕的情况,如果当前的数据页(页是mysql存储的最小单位)存满了,需要申请一个新的数据页,这个过程被称为页分裂。如果造成了页分裂的话,势必会造成性能的影响。但是mysql并不是无脑的数据分裂,如果你是从中间进行数据分裂的话,对于自增主键,会导致一半的性能浪费。mysql会根据你的索引的类型,和追踪插入数据的情况决定分裂的方式,一般都存在mysql数据页的head里面,如果是零散的插入,会从中间分裂。如果是顺序插入,一般是会选择插入点开始分裂,或者插入点往后几行导致的。决定是否从中间分裂,还是从最后分裂。

如果插入的是不规则的数据,没法保证后一个值比前一个大,就会触发上面说的分裂逻辑,最后达到下面的效果

所以绝大多数情况下,我们都需要使用自增索引,除非需要业务自定义主键,最好能保证只有一个索引,且索引是唯一索引。这样可以避免回表,导致查询搜索两棵树。保证数据页的有序性,可以更好的使用索引。

4 回表

通俗的讲就是,如果索引的列在 select 所需获得的列中(因为在 mysql 中索引是根据索引列的值进行排序的,所以索引节点中存在该列中的部分值)或者根据一次索引查询就能获得记录就不需要回表,如果 select 所需获得列中有大量的非索引列,索引就需要先找到主键,再到表中找到相应的列的信息,这就叫回表。

要介绍回表自然就得介绍聚集索引和非聚集索引
InnoDB聚集索引的叶子节点存储行记录,因此, InnoDB必须要有,且只有一个聚集索引:

  • 如果表定义了主键,则PK就是聚集索引;
  • 如果表没有定义主键,则第一个非空唯一索引(not NULL unique)列是聚集索引;
  • 否则,InnoDB会创建一个隐藏的row-id作为聚集索引;

当我们使用普通索引查询方式,则需要先搜索普通索引树,然后得到主键 ID后,再到 ID 索引树搜索一次。因为非主键索引的叶子节点里面,实际存的是主键的ID。这个过程虽然用了索引,但实际上底层进行了两次索引查询,这个过程就称为回表。也就是说,基于非主键索引的查询需要多扫描一棵索引树。因此,我们在应用中应该尽量使用主键查询。或者有高频请求时,合理建立联合索引,防止回表。

5 索引覆盖

一句话表达的话,是只需要在一棵索引树上就能获取SQL所需的所有列数据,无需回表,速度更快。落实到sql上的话,只要执行计划里面的输出结果Extra字段为Using index时,能够触发索引覆盖。

常见的优化手段,就是上面提到的,将查询的字段都建到索引里面,至于dba愿不愿意让你建,那就需要你们自己battle了。

一般索引覆盖适用的场景包括 全表count查询优化、列查询回表、分页回表。高版本的mysql已经做了优化,当命中联合索引的其中一个字段,另外一个是id的时候,会自动优化,无需回表。因为二级索引的叶子上存了primary key,也算索引覆盖,无需额外成本。

6 最左匹配原则

简单来说,就是你使用 ‘xx%’的时候,符合条件的话也会使用索引。
如果是联合索引的话,我举个例子,创建一个(a,b)的联合索引

可以看到a的值是有顺序的,1,1,2,2,3,3,而b的值是没有顺序的1,2,1,4,1,2。但是我们又可发现a在等值的情况下,b值又是按顺序排列的,但是这种顺序是相对的。这是因为MySQL创建联合索引的规则是首先会对联合索引的最左边第一个字段排序,在第一个字段的排序基础上,然后在对第二个字段进行排序。所以b=2这种查询条件没有办法利用索引。举个例子,我弄一个索引,
KEY idx_time_zone (time_zone,time_string) USING BTREE
执行第一条sql,全表扫描

执行第二条sql,可以看到使用了索引。

再看两条sql,建立的索引是 KEY idx_time_zone (time_zone,time_string) USING BTREE

按照正常逻辑来说,第二条sql是不符合索引字段的顺序的,应该不能使用索引才对,但是实际情况却和我们期望的不太一样,这是为啥呢?

从mysql被oracle收购以后,mysql加入了很多oracle以前的技术,高版本mysql自动优化了where条件的先后顺序。简单来说就是查询优化器做了这一步操作,sql会做预处理,那一条能更好的查询就会使用那种规则。

顺便提一下mysql的查询优化器能帮忙干的一些事

6.1 条件转化

例如where a=b and b=2,可以得到a=2,条件传递。最后的sql是 a=2 and b=2 > < = like 都可以传递

6.2 无效代码的排除

例如 where 1=1 and a=2, 1=1永远是正确的,所以最后会优化成 a=2
在比如 where 1=0 永远是false的,这样的也会被排除掉,整sql无效
或者非空字段 where a is null ,这样的也会被排除

6.3 提前计算

包含数学运算的部分,例如 where a= 1+2 会帮你算好,where a=3

6.4 存取类型

当我们评估一个条件表达式,MySQL判断该表达式的存取类型。下面是一些存取类型,按照从最优到最差的顺序进行排列:

  • system系统表,并且是常量表
  • const 常量表
  • eq_ref unique/primary索引,并且使用的是’=’进行存取
  • ref 索引使用’=’进行存取
  • ref_or_null 索引使用’=’进行存取,并且有可能为NULL
  • range 索引使用BETWEEN、IN、>=、LIKE等进行存取
  • index 索引全扫描
  • ALL 表全扫描

经常看执行计划的,一眼就能看出来这是啥意思,举个例子

where index_col=2 and normal_col =3 这里就会选用index_col=2 会作为驱动项。驱动项的意思是指一个sql选定他的执行计划的时候,可能有多条执行路径,一个是全表扫描,再过滤是否符合索引字段及非索引字段的值。另一种是通过索引字段,键值=2找到对应的索引树,过滤后的结果,再比较是否符合非索引字段的值。一般情况下,走索引都比全表扫描需要读取磁盘的次数少,所以称它为更好的执行路径,也就是通过索引字段,作为其驱动表达式

6.5 范围存取

简单来说,a in(1,2,3) 和 a=1 or a=2 or a=3 是一样的,between 1 and 2 和 a>1 and a<2也是一样的, 无需可以优化。

6.6 索引存取类型

避免使用相同前缀的索引,也就是一个字段不要在多个索引上有相同的前缀。比如一个字段已经建立了唯一索引,这个时候如果再给他建立一个联合索引,会导致优化器并不知道你要使用哪个索引。或者你建了前缀相同的一个单索引,一个联合索引,就算你写上了条件,也不一定能用上联合索引。当然,可以force,这就另说了。

6.7 转换

简单的表达式可以进行转换,比如 where -2 = a 会自动变成 where a= -2 ,但是如果牵扯到数学运算,就不能转换了 比如 where 2= -a 这时候不会自动转成 where a =-2.

第二条sql就可以使用索引

所以 我们在开发的过程中,需要注意sql的写法,自觉写成 where a=-2

6.8 and、union、order by、group by等

1)and

and条件后,如果都没索引,扫描全表。有一个存取类型更好,见5.4 ,会使用存储类型更好的索引,如果都一样,哪个索引先创建,用哪个。

2)union

union 每条语句单独优化

这里就会分别执行两条sql,用到索引,再合并结果集

3)order by

order by 会过滤无效排序,比如一个字段本来就有索引

第二条sql和第一条的查询效果是一样的

所以,写sql的时候,不要写无用排序,比如order by ‘xxx’ 这样没有意义。

4)group by

简单来说 group by 的字段,有索引会走索引,group by a order by a 这里的order by等于没写,结果集已经是排序完毕的了,参考 6.8-3 order by
select distinct col_a from table a 等价于 select col_a from a group by col_a

7 索引下推

主要的核心点就在于把数据筛选的过程放在了存储引擎层去处理,而不是像之前一样放到Server层去做过滤。

如果在一张表上,name和age都建立索引,查询条件为 where name like ‘xx%’ and age=11,在低版本的mysql(5.6 以下)的根据索引的最左匹配原则,可以得到放弃了age,只根据name过滤数据。根据name拿到所有的id之后,再根据id回表。

高版本mysql里,没有忽略age这个属性,带着age属性过滤,直接过滤掉了age为11的数据,假设不根据age过滤的数据为10条,过滤后只剩3条,就少了7次回表。减少了io会大量减少性能消耗

8 小表驱动大表

小表驱动大表,也是我们听惯了的话了,其含义主要是指小表的数据集驱动大表的数据集,减少连接次数。打个比方:

表A有1w数据,表B有100w数据,如果A表作为驱动表,处于循环的外层,那么只需要1w次的连接即可。如果B表在外层,那么则需要循环100w次。

下面我们实际测试看看,准备环境mysql 5.7+

准备两张表,一张表 ib_asn_d 数据 9175, 一张表 bs_itembase_ext_attr 数据 1584115,都在商品编码字段上有索引。

首先小表驱动大表

多次反复测试,执行时间大概7秒。
接下来看看大表驱动小表。

将近300秒,不是一个量级的。
接下来分别分析执行计划,执行计划里第一条就是驱动表。

小表驱动大表,大表用了索引,小表全表扫描,只扫描8000多行

大表驱动小表,大表全表扫描,需要扫描147w行。
经过多次测试得出了结论:

  1. 当使用left join时,左表是驱动表,右表是被驱动表 ;
  2. 当使用right join时,右表是驱动表,左表是被驱动表 ;
  3. 当使用inner join时,mysql会选择数据量比较小的表作为驱动表,大表作为被驱动表 ;
  4. 驱动表索引不生效,非驱动表索引生效

保证小表是驱动表很重要。

9 总结

  1. 覆盖索引:如果查询条件使用的是普通索引(或是联合索引的最左原则字段),查询结果是联合索引的字段或是主键,不用回表操作,直接返回结果,减少IO磁盘读写读取整行数据,所以高频字段建立联合索引是很有必要的
  2. 最左前缀:联合索引的最左 N 个字段,也可以是字符串索引的最左 M 个字符。建立索引的时候,注意左前缀不要重复,避免查询优化器无法判定如何使用索引
  3. 索引下推:name like ‘hello%’and age >10 检索,MySQL 5.6版本之前,会对匹配的数据进行回表查询。5.6版本后,会先过滤掉age<10的数据,再进行回表查询,减少回表率,提升检索速度

作者:京东物流 吴思维 
来源:京东云开发者社区 转载请注明来源

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
24 收藏
2
分享
返回顶部
顶部