深入理解MySQL索引

标签: 理解 mysql 索引 | 发表时间:2020-03-22 10:00 | 作者:杨亨
出处:https://www.infoq.cn

前言

当提到MySQL数据库的时候,我们的脑海里会想起几个关键字:索引、事务、数据库锁等等, 索引是MySQL的灵魂,是平时进行查询时的利器,也是面试中的重中之重

可能你了解索引的底层是b+树,会加快查询,也会在表中建立索引,但这是远远不够的,这里列举几个索引常见的面试题:

1、索引为什么要用b+树这种数据结构?

2、聚集索引和非聚集索引的区别?

3、索引什么时候会失效,最左匹配原则是什么?

当遇到这些问题的时候,可能会发现自己对索引还是一知半解,今天我们一起学习MySQL的索引。

一、一条查询语句是如何执行的

首先来看 在MySQL数据库中,一条查询语句是如何执行的,索引出现在哪个环节,起到了什么作用

1.1 应用程序发现SQL到服务端

当执行SQL语句时,应用程序会连接到相应的数据库服务器,然后服务器对SQL进行处理。

1.2 查询缓存

接着数据库服务器会先去查询是否有该SQL语句的缓存,key是查询的语句,value是查询的结果。如果你的查询能够直接命中,就会直接从缓存中拿出value来返回客户端。

注:查询不会被解析、不会生成执行计划、不会被执行。

1.3 查询优化处理,生成执行计划

如果没有命中缓存,则开始第三步。

  • 解析SQL:生成解析树,验证关键字如select,where,left join 等)是否正确。
  • 预处理:进一步检查解析树是否合法,如 检查数据表和列是否存在,验证用户权限等。
  • 优化SQL决定使用哪个索引,或者在多个表相关联的时候决定表的连接顺序。紧接着, 将SQL语句转成执行计划

1.4 将查询结果返回客户端

最后,数据库服务器将查询结果返回给客户端。(如果查询可以缓存,MySQL也会将结果放到查询缓存中)

这就是一条查询语句的执行流程,可以看到索引出现在优化SQL的流程步骤中,接下来了解索引到底是什么?

二、索引概述

先简单地了解一下索引的基本概念。

2.1 索引是什么

索引是帮助数据库高效获取数据的数据结构。

2.2 索引的分类

1)从存储结构上来划分

  • Btree索引(B+tree,B-tree)
  • 哈希索引
  • full-index全文索引
  • RTree

2)从应用层次上来划分

  • 普通索引:即一个索引只包含单个列,一个表可以有多个单列索引。
  • 唯一索引:索引列的值必须唯一,但允许有空值。
  • 复合索引:一个索引包含多个列。

3)从表记录的排列顺序和索引的排列顺序是否一致来划分

  • 聚集索引:表记录的排列顺序和索引的排列顺序一致。
  • 非聚集索引:表记录的排列顺序和索引的排列顺序不一致。

2.3 聚集索引和非聚集索引

1)简单概括

  • 聚集索引:就是以主键创建的索引。
  • 非聚集索引:就是以非主键创建的索引(也叫做二级索引)。

2)详细概括

  • 聚集索引

聚集索引表记录的排列顺序和索引的排列顺序一致,所以查询效率快,因为只要找到第一个索引值记录,其余的连续性的记录在物理表中也会连续存放,一起就可以查询到。

缺点:新增比较慢,因为为了保证表中记录的物理顺序和索引顺序一致,在记录插入的时候,会对数据页重新排序。

  • 非聚集索引

索引的逻辑顺序与磁盘上行的物理存储顺序不同,非聚集索引在叶子节点存储的是主键和索引列,当我们使用非聚集索引查询数据时,需要拿到叶子上的主键再去表中查到想要查找的数据。这个过程就是我们所说的回表。

3)聚集索引和非聚集索引的区别

  • 聚集索引在叶子节点存储的是表中的数据。
  • 非聚集索引在叶子节点存储的是主键和索引列。

举个例子

比如汉语字典,想要查「阿」字,只需要翻到字典前几页,a开头的位置,接着「啊」「爱」都会出来。也就是说, 字典的正文部分本身就是一个目录,不需要再去查其他目录来找到需要找的内容。我们 把这种正文内容本身就是一种按照一定规则排列的目录称为==聚集索引==

如果遇到不认识的字,只能根据“偏旁部首”进行查找,然后根据这个字后的页码直接翻到某页来找到要找的字。但结合 部首目录检字表 而查到的字的排序并不是真正的正文的排序方法。

比如要查“玉”字,我们可以看到在查部首之后的检字表中“玉”的页码是587页,然后是珏,是251页。很显然,在字典中这两个字并没有挨着,现在看到的连续的“玉、珏、莹”三字实际上就是他们 在非聚集索引中的排序,是字典正文中的字在非聚集索引中的映射。我们可以通过这种方式来找到所需要的字,但它需要两个过程,先找到目录中的结果,然后再翻到结果所对应的页码。我们 把这种目录纯粹是目录,正文纯粹是正文的排序方式称为==非聚集索引==

2.4 MySQL如何添加索引

1)添加PRIMARY KEY(主键索引)

  ALTER TABLE `table_name` ADD PRIMARY KEY ( `column` )

2)添加UNIQUE(唯一索引)

  ALTER TABLE `table_name` ADD UNIQUE (`column`)

3)添加INDEX(普通索引)

  ALTER TABLE `table_name` ADD INDEX index_name (`column` )

4)添加FULLTEXT(全文索引)

  ALTER TABLE `table_name` ADD FULLTEXT (`column`)

5)添加多列索引

  ALTER TABLE `table_name` ADD INDEX index_name (`column1`,`column2`,`column3`)

三、索引底层数据结构

了解了索引的基本概念后,可能最好奇的就是 索引的底层是怎么实现的呢?为什么索引可以如此高效地进行数据的查找?如何设计数据结构可以满足我们的要求? 下文通过一般程序员的思维来想一下如果是我们来设计索引,要如何设计来达到索引的效果。

3.1 哈希索引

可能直接想到的就是用哈希表来实现快速查找,就像我们平时用的hashmap一样,value = get(key) O(1)时间复杂度一步到位,确实, 哈希索引 是一种方式。

1)定义

哈希索引就是采用一定的哈希算法,只需一次哈希算法即可立刻定位到相应的位置,速度非常快。 本质上就是把键值换算成新的哈希值,根据这个哈希值来定位

2)局限性

  • 哈希索引没办法利用索引完成排序。
  • 不能进行多字段查询。
  • 在有大量重复键值的情况下,哈希索引的效率也是极低的(出现哈希碰撞问题)。
  • 不支持范围查询。

在MySQL常用的InnoDB引擎中,还是使用B+树索引比较多。InnoDB是自适应哈希索引的(hash索引的创建由 ==InnoDB存储引擎自动优化创建==,我们干预不了)。

3.2 如何设计索引的数据结构呢

假设要查询某个区间的数据,我们只需要拿到区间的起始值,然后在树中进行查找。

如数据为:

1)查询[7,30]区间的数据

当查找到起点节点10后,再顺着链表进行遍历,直到链表中的节点数据大于区间的终止值为止。 所有遍历到的数据,就是符合区间值的所有数据

2)还可以怎么优化呢?

利用二叉查找树,区间查询的功能已经实现了。但是,为了节省内存,我们只能把树存储在硬盘中。

那么, 每个节点的读取或者访问,都对应一次硬盘IO操作。每次查询数据时磁盘IO操作的次数,也叫做==IO渐进复杂度==,也就是==树的高度==

所以,我们要减少磁盘IO操作的次数,也就是 要==降低树的高度==

结构优化过程如下图所示:

这里将二叉树变为了M叉树,降低了树的高度,那么这个M应该选择多少才合适呢?

问题:对于相同个数的数据构建m叉树索引,m叉树中的m越大,那树的高度就越小,那m叉树中的m是不是越大越好呢?到底多大才合适呢?

不管是内存中的数据还是磁盘中的数据,操作系统都是按页(一页的大小通常是4kb,这个值可以通过 getconfig(PAGE_SIZE)命令查看)来读取的,一次只会读取一页的数据。

如果要读取的数据量超过了一页的大小,就会触发多次IO操作。所以在选择m大小的时候,要尽量让每个节点的大小等于一个页的大小。

一般实际应用中,出度d(树的分叉数)是非常大的数字,通常超过100; ==树的高度(h)非常小,通常不超过3==

3.3 B树

顺着解决问题的思路知道了我们想要的数据结构是什么。目前索引常用的数据结构是B+树,先介绍一下什么是B树(也就是B-树)。

1)B树的特点:

  • 关键字分布在整棵树的所有节点。
  • 任何一个关键字 出现且只出现在一个节点中
  • 搜索有可能在 非叶子节点 结束。
  • 其搜索性能等价于在关键字全集内做一次二分查找。如下图所示:

3.4 B+树

了解了B树,再来看一下B+树,也是MySQL索引大部分情况所使用的数据结构。

下图是一个M=3阶的B+树

1)B+树基本特点

  • 非叶子节点的子树指针与关键字个数相同。
  • 非叶子节点的子树指针P[i],指向关键字属于 [k[i],K[i+1]) 的子树( 注意:区间是前闭后开)。
  • 为所有叶子节点增加一个链指针
  • 所有关键字都在叶子节点出现

这些基本特点是为了满足以下的特性。

2)B+树的特性

  • 所有的关键字 都出现在叶子节点的链表中,且链表中的关键字是有序的。
  • 搜索只在叶子节点命中
  • 非叶子节点相当于是 叶子节点的索引层,叶子节点是 存储关键字数据的数据层

3)相对B树,B+树做索引的优势

  • B+树的磁盘读写代价更低。 B+树的内部没有指向关键字具体信息的指针,所以其内部节点相对B树更小,如果把所有关键字存放在同一块盘中,那么盘中所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多, 相应的,IO读写次数就降低了
  • 树的查询效率更加稳定。B+树所有数据都存在于叶子节点,所有关键字查询的路径长度相同,每次数据的查询效率相当。而B树可能在非叶子节点就停止查找了,所以查询效率不够稳定。
  • B+树只需要去遍历叶子节点就可以实现整棵树的遍历

3.5 MongoDB的索引为什么选择B树,而MySQL的索引是B+树?

因为MongoDB不是传统的关系型数据库,而是以Json格式作为存储的NoSQL非关系型数据库,目的就是高性能、高可用、易扩展。摆脱了关系模型,所以 范围查询和遍历查询的需求就没那么强烈了

3.6 MyISAM存储引擎和InnoDB的索引有什么区别

1)MyISAM存储引擎

  • 主键索引

MyISAM的索引文件(.MYI)和数据文件(.MYD)文件是分离的,索引文件仅保存记录所在页的指针(物理位置),通过这些指针来读取页,进而读取被索引的行。

树中的叶子节点保存的是对应行的物理位置。通过该值, ==存储引擎能顺利地进行回表查询,得到一行完整记录==

同时,每个叶子也保存了指向下一个叶子的指针,从而 方便叶子节点的范围遍历

  • 辅助索引

在MyISAM中,主键索引和辅助索引在结构上没有任何区别, ==只是主键索引要求key是唯一的,而辅助索引的key可以重复==

1)Innodb存储引擎

Innodb的主键索引和辅助索引之前提到过,再回顾一次。

  • 主键索引

InnoDB主键索引中既存储了主健值,又存储了行数据。

  • 辅助索引

对于辅助索引,InnoDB采用的方式是在叶子节点中保存主键值,通过这个主键值来回表查询到一条完整记录,因此 按辅助索引检索其实进行了二次查询,效率是没有主键索引高的

四、MySQL索引失效

在上一节中了解了索引的多种数据结构,以及B树和B+树的对比等,大家应该对索引的底层实现有了初步的了解。这一节从应用层的角度出发,看一下如何建索引更能满足我们的需求,以及MySQL索引什么时候会失效的问题。

先来思考一个小问题。

问题:当查询条件为2个及2个以上时,是创建多个单列索引还是创建一个联合索引好呢?它们之间的区别是什么?哪个效率高呢?

先来建立一些单列索引进行测试:

这里建立了一张表,里面建立了三个单列索引userId,mobile,billMonth。

然后进行多列查询。

  explain select * from `t_mobilesms_11` where userid = '1' and mobile = '13504679876' and billMonth = '1998-03'

我们发现查询时只用到了userid这一个单列索引,这是为什么呢?因为这取决于 MySQL优化器的优化策略

当多条件联合查询时,优化器会评估哪个条件的索引效率高,它会选择最佳的索引去使用。也就是说,此处三个索引列都可能被用到,只不过优化器判断只需要使用userid这一个索引就能完成本次查询,故最终explain展示的key为userid。

4.1 总结

多个单列索引在多条件查询时优化器会选择最优索引策略,可能 只用一个索引,也可能将多个索引都用上

但是多个单列索引底层会建立多个B+索引树,比较占用空间,也会浪费搜索效率 所以 多条件联合查询时最好建联合索引

那联合索引就可以三个条件都用到了吗?会出现索引失效的问题吗?

4.2 联合索引失效问题

该部分参考并引用文章:一张图搞懂MySQL的索引失效( https://segmentfault.com/a/1190000021464570

创建user表,然后建立 name, age, pos, phone 四个字段的联合索引 全值匹配(索引最佳)。

索引生效,这是最佳的查询。

那么时候会失效呢?

1)违反最左匹配原则

最左匹配原则:最左优先,以最左边的为起点任何连续的索引都能匹配上,如不连续,则匹配不上。

如:建立索引为(a,b)的联合索引,那么只查 where b = 2 则不生效。换句话说:如果建立的索引是(a,b,c),也只有(a),(a,b),(a,b,c)三种查询可以生效。

这里跳过了最左的name字段进行查询,发现索引失效了。

遇到范围查询(>、<、between、like)就会停止匹配。

比如:a= 1 and b = 2 and c>3 and d =4 如果建立(a,b,c,d)顺序的索引,d是用不到索引的,因为 c字段是一个范围查询,它之后的字段会停止匹配

2)在索引列上做任何操作

如计算、函数、(手动或自动)类型转换等操作,会导致索引失效而进行全表扫描。

  explain select * from user where left(name,3) = 'zhangsan' and age =20

这里对name字段进行了left函数操作,导致索引失效。

3)使用不等于(!= 、<>)

  explain select * from user where age != 20;

  explain select * from user where age <> 20;

4)like中以通配符开头(’%abc’)

索引失效

  explain select * from user where name like ‘%zhangsan’;

索引生效

  explain select * from user where name like ‘zhangsan%’;

5)字符串不加单引号索引失效

  explain select * from user where name = 2000;

6)or连接索引失效

  explain select * from user where name = ‘2000’ or age = 20 or pos =‘cxy’;

7)order by

正常(索引参与了排序),没有违反最左匹配原则。

  explain select * from user where name = 'zhangsan' and age = 20 order by age,pos;

违反最左前缀法则,导致额外的文件排序(会降低性能)。

  explain select name,age from user where name = 'zhangsan' order by pos;

8)group by

正常(索引参与了排序)。

  explain select name,age from user where name = 'zhangsan' group by age;

违反最左前缀法则,导致产生临时表(会降低性能)。

  explain select name,age from user where name = 'zhangsan' group by pos,age;

五、总结

  • 了解一条查询语句是如何执行的,发现建立索引是一种可以高效查找的数据结构。
  • 了解了索引的各种分类情况,聚集索引和非聚集索引的区别,如何创建各种索引。
  • 通过需求一步步分析出为什么MySQL要选b+tree作为索引的数据结构,对比了btree和b+tree的区别、 MyISAM和innodb中索引的区别。
  • 了解了索引会失效的多种情况,比较重要的最左匹配原则,相应地我们可以在建索引的时候做一些优化。

希望大家能够多去使用索引进行SQL优化,有问题欢迎指出。

文章配图来源于网络

本文转载自公众号宜信技术学院(ID:CE_TECH)。

原文链接

https://mp.weixin.qq.com/s/sT-Jz67p8Gadvcft-iO-9g

相关 [理解 mysql 索引] 推荐:

深入理解MySQL索引

- - InfoQ推荐
当提到MySQL数据库的时候,我们的脑海里会想起几个关键字:索引、事务、数据库锁等等, 索引是MySQL的灵魂,是平时进行查询时的利器,也是面试中的重中之重. 可能你了解索引的底层是b+树,会加快查询,也会在表中建立索引,但这是远远不够的,这里列举几个索引常见的面试题:. 1、索引为什么要用b+树这种数据结构.

理解MySQL数据库覆盖索引

- - haohtml's blog
看AUTO_INCREMENT就知道数据并不多,75万条. 很简单对不对?怪异的地方在于:. 如果换成MyISAM做存储引擎的时候,查询耗时只需要0.01s,用InnoDB却会是0.15s左右. 如果只是就这么点差距其实不是什么大不了的事,但是真实的业务需求比这个复杂,造成的差距也很大:MyISAM只需要0.12s,InnoDB则需要2.2s.,最终定位到问题症结是在这条SQL.

如何理解并正确使用 MySQL 索引

- - 文章 – 伯乐在线
索引是存储引擎用于快速查找记录的一种数据结构,通过合理的使用数据库索引可以大大提高系统的访问性能,接下来主要介绍在MySql数据库中索引类型,以及如何创建出更加合理且高效的索引技巧. 注:这里主要针对的是InnoDB存储引擎的B+Tree索引数据结构. 1、大大减轻了服务器需要扫描的数据量,从而提高了数据的检索速度.

[MySQL] B+树索引

- - CSDN博客推荐文章
B+树是一种经典的数据结构,由平衡树和二叉查找树结合产生,它是为磁盘或其它直接存取辅助设备而设计的一种平衡查找树,在B+树中,所有的记录节点都是按键值大小顺序存放在同一层的叶节点中,叶节点间用指针相连,构成双向循环链表,非叶节点(根节点、枝节点)只存放键值,不存放实际数据. 保持树平衡主要是为了提高查询性能,但为了维护树的平衡,成本也是巨大的,当有数据插入或删除时,需采用拆分节点、左旋、右旋等方法.

mysql 索引技巧

- - 小彰
MySQL索引的建立对于MySQL的高效运行是很重要的. 下面介绍几种常见的MySQL索引类型. 在数据库表中,对字段建立索引可以大大提高查询速度. 假如我们创建了一个 mytable表:. CREATE TABLE mytable(   ID INT NOT NULL,    username VARCHAR(16) NOT NULL  );   我们随机向里面插入了10000条记录,其中有一条:5555, admin.

mysql选择索引

- - CSDN博客数据库推荐文章
1、尽量为用来搜索、分类或分组的数据列编制索引,不要为作为输出显示的数据列编制索引. 最适合有索引的数据列是那些在where子句中数据列,在联结子句中出现的数据列,或者是在Group by 、Order by子句中出现的数据列. select 后的数据列最好不要用索引. 2、综合考虑各数据列的维度.

mysql 索引详解

- - 行业应用 - ITeye博客
本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题. 特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等. 为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论.

mysql索引认识

- - 数据库 - ITeye博客
数据在磁盘中是以 “块”的形式存储的,所以一张表涉及的数据可能会存在多个块中,而在磁盘中查询数据则会根据字段是否为有序与无序来区分,. 无序情况:1.数值具有唯一性则需要查找 总块数/2.                   2.无序+无唯一性则需要查找  总块数. 有序情况:1.数值唯一性:log2(总块数/2)   (log2是二分查找算法).

MySQL 索引方式

- - zzm
本文配图来自《高性能MySQL(第二版)》. 在数据库中,对性能影响最大的几个策略包括数据库的锁策略、缓存策略、索引策略、存储策略、执行计划优化策略. 索引策略决定数据库快速定位数据的效率,存储策略决定数据持久化的效率. MySQL中两大主要存储引擎MyISAM和InnoDB采用了不同的索引和存储策略,本文将分析它们的异同和性能.

MySql索引总结

- - 掘金后端
MySQL 索引底层数据结构.   Mysql索引使用的数据结构主要有 BTree索引 和 Hash索引. 对于Hash索引来说,底层数据结构就是哈希表,因此在绝大多数需求为单条记录查询的时候,使用Hash索引查询性能最快. 其余大多数场景建议使用BTree索引. 为什么索引能够提高查询速度.