数据库

理解 Mysql 索引原理及特性

转载:https://my.oschina.net/u/4090830/blog/10320986

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

在数据库中,索引(Index)是一种数据结构,它能够快速地定位到表中的特定行或记录。索引通常是在表上的一组列上创建的,这些列可以是表的主键、唯一键或其他重要的列。通过在这些列上创建索引,可以提高数据库的查询性能和数据检索速度。

索引通常是一个有序的数据结构,可以使用二叉树、B树、B+树等不同的数据结构实现。它存储了表中的关键字(Key)和指向表中记录的指针,通过这些指针可以快速地定位到表中满足查询条件的记录。索引可以加快查询的速度,尤其是在大型表中进行查询时,查询速度的提升尤为明显。

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 作为聚集索引;

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 条件后,如果都没索引,扫描全表。

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. 聚集索引(主键索引):在数据库里面,所有行数都会按照主键索引进行排序。
  2. 非聚集索引:就是给普通字段加上索引。
  3. 联合索引:就是好几个字段组成的索引,称为联合索引。
key 'idx_age_name_sex' ('age','name','sex')

MySQL联合索引生效的原则是遵循最左前缀原则。也就是说,联合索引在查询时,只有按照索引的最左边的列开始查询时,索引才会生效。如果不按照最左边的列开始查询,那么索引将不会被使用。

例如,对于一个联合索引 (col1, col2, col3),当查询条件中包含 col1 和 col2 时,索引会被使用;当只包含 col2 或只包含 col3 时,索引不会被使用。

此外,联合索引的顺序也很重要。对于一个联合索引 (col1, col2, col3),如果查询条件只包含 col2 和 col3,而不包含 col1,索引也不会被使用,因为查询条件没有按照索引的顺序来匹配。因此,在创建联合索引时,需要根据实际查询的情况来确定索引的顺序。

就比如说一张学生表里面的联合索引如上面所示,那么下面A,B,C,D,E,F哪个会走索引呢?

A:select * from student where age = 16 and name = '小张'
B:select * from student where name = '小张' and sex = '男'
C:select * from student where name = '小张' and sex = '男' and age = 18
D:select * from student where age > 20 and name = '小张'
E:select * from student where age != 15 and name = '小张'
F:select * from student where age = 1
 A遵从最左匹配原则,age是在最左边,所以A走索引;

 B直接从name开始,没有遵从最左匹配原则,所以不走索引;

 C虽然从name开始,但是有索引最左边的age,mysql内部会自动转成where age = '18' and name = '小张'  and sex = '男' 这种,所以还是遵从最左匹配原则;

 D这个是因为age>20是范围,范围字段会结束索引对范围后面索引字段的使用,所以只有走了age这个索引;

 E这个虽然遵循最左匹配原则,但是不走索引,因为!= 不走索引;

 F这个只走age索引,不走name索引,原因如上;

10.有哪些列子不走索引呢


表student中两个字段age,name加了索引

key 'idx_age' ('age'),
key 'idx_name' ('name')

10.1  Like这种就是%在前面的不走索引,在后面的走索引

A:select * from student where 'name' like '王%'
B:select * from student where 'name' like '%小'
A走索引,B不走索引

10.2 用索引列进行计算的,不走索引

A:select * from student where age = 10+8
B:select * from student where age + 8 = 18
A走索引,B不走索引

10.3 对索引列用函数了,不走索引

A:select * from student where  concat('name','哈') ='王哈哈';
B:select * from student where name = concat('王哈','哈');
A不走索引,B走索引

10.4 索引列用了!= 不走索引,如下:

select * from student where age != 18

11.总结


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