深入理解MySQL索引

前言

当提到MySQL数据库的时候，我们的脑海会经常想起几个关键字：索引、事务、数据库锁等，索引是MySQL的灵魂，是平时进行查询的利器，也是面试中的重中之重。
可能我们了解MySQL的底层是b+树，会加快查询，也会在表中建立索引，但是这是远远不够的，下面我们来列举几个面试中常见的索引问题：

  • 索引为什么要用b+树这种数据结构？
  • 聚集索引和非聚集索引的区别
  • 索引什么时候会失效，最左原则是什么？
    当遇到这些问题的时候，可能会发现自己对索引还是一知半解，今天我们一起学习MySQL的索引。

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

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

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

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

1.2 查询缓存

接着数据库服务器会先去查询是否有该SQL语句的缓存，key是查询的语句，value是查询的结果。如果存在缓存，即你查询的结果直接命中，就会直接从缓存中拿出value返回给客户端。
注：这个查询过程中，查询不会被解析，不会生成查询计划，不会被执行

1.3 查询优化处理，执行查询计划

如果没有存在缓存，则执行此步骤

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

1.4将查询结果返回给客户端

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


image.png

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

二 索引概述

先简单了解以下索引的相关概念

2.1 索引是什么

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

2.2 索引分类

1）从存储结构上来划分

  • Btree索引（B+tree，B-tree）
  • 哈希索引
  • full-index 全文索引
  • Rtree
    2）从应用程序上来划分
  • 普通索引：即一个索引只包含单个列，一个表可以有多个单列索引
  • 唯一索引：索引列的值必须唯一，但允许有空值
  • 复合索引：一个索引包含多个列
    3）从表记录的排列顺序和索引的排列顺序是否一致来划分
  • 聚集索引：表记录的排列顺序和索引的排列顺序一致
  • 非聚集索引：表记录的排列顺序和索引的排列顺序不一致

2.3 聚集索引和非聚集索引

1）简单概述

  • 聚集索引：以主键创建的索引
  • 非聚集索引：以非主键创建的索引（也叫二级索引）
    2）详细概括
  • 聚集索引
    聚集索引表记录的排列顺序和索引的排列顺序一致，所以查询效率快，因为只要找到第一个索引值记录，其余连续性的记录在物理表中也会连续存放，一起就可以查询到。
    缺点：新增比较慢，因为为了保证表中记录的物理顺序和索引顺序一致，在记录插入的时候，会对数据页进行重新排序
  • 非聚集索引
    索引的逻辑顺序与磁盘上行的物理存储顺序不同，非聚集索引在叶子节点存储的是主键和索引列，当我们使用非聚集索引查询数据时，需要拿到叶子节点上的主键再去表中查找想要的数据。这个过程就是我们所说的回表。
    3）聚集索引和非聚集索引的区别
  • 聚集索引再叶子节点中，存储的是表中的数据
  • 非聚集索引在叶子节点存储的是主键和索引列
    举个例子
    比如汉语字典，想要查「阿」字，只需要翻到字典前几页，a开头的位置，接着「啊」「爱」都会出来。也就是说，字典的正文部分本身就是一个目录，不需要再去查其他目录来找到需要找的内容。我们把这种正文内容本身就是一种按照一定规则排列的目录称为==聚集索引==。
    如果遇到不认识的字，只能根据“偏旁部首”进行查找，然后根据这个字后的页码直接翻到某页来找到要找的字。但结合部首目录和检字表而查到的字的排序并不是真正的正文的排序方法。
    image.png

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

2.4MySQL如何添加索引

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

ALTER TABLE 'tableName' ADD PRIMARY KEY ('column')

2）添加UNIQUE（唯一索引）

ALTER TABLE 'tableName' ADD UNIQUE('column')

3）添加INDEX（普通索引）

ALTER TABLE 'tableName' ADD INDEX indexName ('column')

4）添加FULLTEXT （全文索引）

ALTER TABLE 'tableName' ADD FULLTEXT('column')

5）添加多列索引

ALTER TABLE `tableName` ADD INDEX indexName (`column1`,`column2`,`column3`)

索引底层数据结构

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

3.1哈希索引

可能直接想到的就是用哈希表来实现快速查找，就像我们平时用的hashmap一样，value=get（key）O(1)时间复杂度一步到位，确实，哈希索引是一种方式
1）定义
哈希索引就是采用一定的哈希算法，只需一次哈希算法即可立刻定位到相应的位置，速度非常快。本质上就是将键值换成新的哈希值，根据这个哈希值来定位

image.png

2）局限性

  • 哈希索引没法利用索引完成排序
  • 不能进行多字段查询
  • 在有大量重复键值的情况下，哈希索引的效率是极低的（出现哈希碰撞问题）
  • 不支持范围查询。
    在MySQL常用的InnoDB引擎中，还是使用B+Tree索引比较多。InnoDB是自适应哈希索引的（哈希索引的创建由InnoDB存储引擎自动优化创建，我们干预不了）

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

假设要查询某个区间的数据，我们只需要拿到区间的起始值，然后在书中查找。如数据为：

image.png

1）查询[7,30]区间的数据
image.png

当找到起始节点10后，再顺着链表进行遍历，知道链表中的节点数据大于区间的终止值为止。所有遍历到的数据，就是符合区间值的所有数据
** 2)还可以怎么优化**
利用二叉查找树，区间查询的功能已经实现了，但是，为了节省内存，我们只能把树存储在硬盘中。
那么，每个节点的读取或者访问，都对应一次硬盘IO操作，每次查询数据时磁盘IO操作的次数，也叫做IO渐进复杂度，也就是树的高度
所以，我们要减少IO磁盘操作的次数，也就是要降低树的高度
结构优化过程如下图所示：
image.png

image.png

这里将二叉树变成了M叉树，降低了树的高度，那么这个M应该选择多少才合适呢？
问题：对于相同个数的数据构建m叉树索引，m叉树的m越大，那树的高度就越小，那么m叉树中的m是不是越大越好呢？到底多大才合适呢？
不管是内存中的数据还是磁盘中的数据，操作系统都是按页（一页的大小通常是4kb，这个值可以通过getconfig(PAGE_SIZE)命令查看）来读取的，一次只会读取一页的数据。
如果要读取的数据量超过了一页的大小，就会触发多次IO操作。所以在选择m大小的时候，要尽量让每个节点的大小等于一个页的大小。一般实际应用中，出度d（树的分叉数）是非常大的数字，通常超过100；树的高度（h）非常小，通常不超过3。

3.3 B树

顺着解决问题的思路知道了我们想要的数据结构是什么。目前索引常用的数据结构是b+树，先介绍一下什么是b树（也就是B-tree）
1）B树的特点：

  • 关键字分布在整棵树的所有节点
  • 任何一个关键字出现且只出现在一个节点中

  • 搜索可能在非叶子节点结束
    如下图所示：


    image.png

3.4 B+树

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

image.png

1）B+树的特点：

  • 非叶子节点的子树指针与关键字个数相同。
  • 非叶子节点的子树指针P[i]指向关键字属于 [k[i],K[i+1])的子树（注意：区间是前闭后开)。
  • 为所有的叶子节点增加一个链指针
  • 所有关键字都出现在叶子节点
    这些基本特点是为了满足以下的特性。
    2）B+树的特性
  • 所有的关键字都出现在叶子节点的链表中，并且链表的关键字是有序的
  • 搜索只在叶子节点中命中
  • 非叶子节点相当于叶子节点的索引层，叶子节点是存储关键字数据的数据层
    3）相对B树，B+树做索引的优势
  • B+树的读写磁盘代价更低。B+树没有具体指向关键字具体信息的指针，所以内部节点相对B树更小，如果把所有关键字存放在同一块盘中，那么盘中所容纳的关键字数量越多，一次性读入内存的需要查找的关键字也就越多，相应的，IO读写次数就降低了
  • 树的查询效率更加稳定。B+树所有数据都存储在叶子节点，所有关键字查询的路径长度相同，每次数据的查询效率想当。而B树可能在非叶子节点就停止查找了，所以查询的效率不够稳定
  • B+树只需要遍历叶子节点就可以实现整棵树的遍历

Mongo DB的索引为什么选择的是B树，而MySQL是B+树？

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

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

1）MyISAM存储引擎

image
  • 主键索引

MyISAM的索引文件（.MYI）和数据文件（.MYD）文件是分离的，索引文件仅保存记录所在页的指针（物理位置），通过这些指针来读取页，进而读取被索引的行。树中的叶子节点保存的是对应行的物理位置。通过该值，存储引擎能顺利地进行回表查询，得到一行完整记录。同时，每个叶子也保存了指向下一个叶子的指针，从而方便叶子节点的范围遍历。

  • 辅助索引

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

1）Innodb存储引擎

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

  • 主键索引
image

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

  • 辅助索引
image

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

四、MySQL索引失效

在上一节中了解了索引的多种数据结构，以及B树和B+树的对比等，大家应该对索引的底层实现有了初步的了解。这一节从应用层的角度出发，看一下如何建索引更能满足我们的需求，以及MySQL索引什么时候会失效的问题。先来思考一个小问题。问题：当查询条件为2个及2个以上时，是创建多个单列索引还是创建一个联合索引好呢？它们之间的区别是什么？哪个效率高呢？先来建立一些单列索引进行测试：

image

这里建立了一张表，里面建立了三个单列索引userId,mobile,billMonth。 然后进行多列查询。

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

我们发现查询时只用到了userid这一个单列索引，这是为什么呢？因为这取决于MySQL优化器的优化策略。当多条件联合查询时，优化器会评估哪个条件的索引效率高，它会选择最佳的索引去使用。也就是说，此处三个索引列都可能被用到，只不过优化器判断只需要使用userid这一个索引就能完成本次查询，故最终explain展示的key为userid。

4.1 总结

多个单列索引在多条件查询时优化器会选择最优索引策略，可能只用一个索引，也可能将多个索引都用上。但是多个单列索引底层会建立多个B+索引树，比较占用空间，也会浪费搜索效率 所以多条件联合查询时最好建联合索引。那联合索引就可以三个条件都用到了吗？会出现索引失效的问题吗？

4.2 联合索引失效问题

该部分参考并引用文章：一张图搞懂MySQL的索引失效（https://segmentfault.com/a/1190000021464570）创建user表，然后建立 name, age, pos, phone 四个字段的联合索引 全值匹配（索引最佳）。

image

索引生效，这是最佳的查询。 那么时候会失效呢？

1）违反最左匹配原则

最左匹配原则：最左优先，以最左边的为起点任何连续的索引都能匹配上，如不连续，则匹配不上。如：建立索引为(a,b)的联合索引，那么只查 where b = 2 则不生效。换句话说：如果建立的索引是(a,b,c)，也只有(a),(a,b),(a,b,c)三种查询可以生效。
image

这里跳过了最左的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
image

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

3）使用不等于（!= 、<>）

explain select * from user where age != 20;
image
explain select * from user where age <> 20;
image

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

索引失效

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

索引生效

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

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

explain select * from user where name = 2000;
image

6）or连接索引失效

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

7）order by

正常（索引参与了排序），没有违反最左匹配原则。

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

违反最左前缀法则，导致额外的文件排序（会降低性能）。

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

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;
image

五、总结

  • 了解一条查询语句是如何执行的，发现建立索引是一种可以高效查找的数据结构。

  • 了解了索引的各种分类情况，聚集索引和非聚集索引的区别，如何创建各种索引。

  • 通过需求一步步分析出为什么MySQL要选b+tree作为索引的数据结构，对比了btree和b+tree的区别、 MyISAM和innodb中索引的区别。

  • 了解了索引会失效的多种情况，比较重要的最左匹配原则，相应地我们可以在建索引的时候做一些优化。

本文章参考了深入理解MysSQL索引

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 212,332评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 90,508评论 3赞 385
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 157,812评论 0赞 348
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 56,607评论 1赞 284
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 65,728评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,919评论 1赞 290
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,071评论 3赞 410
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,802评论 0赞 268
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,256评论 1赞 303
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,576评论 2赞 327
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,712评论 1赞 341
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,389评论 4赞 332
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,032评论 3赞 316
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,798评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,026评论 1赞 266
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,473评论 2赞 360
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,606评论 2赞 350