AI 年度盘点与2025发展趋势展望,50+案例解析亮相AICon 了解详情
写点什么

深入理解 MySQL 索引

  • 2020-03-22
  • 本文字数:5953 字

    阅读完需:约 20 分钟

深入理解MySQL索引

前言

当提到 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


2020-03-22 10:0018317

评论 1 条评论

发布
用户头像
getconf
2021-09-17 10:03
回复
没有更多了
发现更多内容

沟通视窗:改善人际沟通

石云升

28天写作 职场经验 管理经验 3月日更 沟通模型

redis分布式锁实现

Sakura

28天写作 3月日更

甲方日常 93

句子

工作 随笔杂谈 日常

源码分析 -Netty:多线程在Netty中的应用

程序员架构进阶

Java 源码分析 Netty 28天写作 3月日更

《3%法则》读书笔记

boshi

读书笔记 七日更

对产品经理的一些思考

ES_her0

28天写作 3月日更

种春草肥禾,织数字天下

脑极体

为什么在做微服务设计的时候需要DDD?

xcbeyond

微服务 DDD 3月日更

2021年金三银四全新版互联网大厂Java面试题,分类65份PDF,累计2340页

Java 架构 面试

Mac Os下搭建Hadoop运行环境

白贺BaiHe

大数据 数仓 hadoo

去年,蚂蚁一面的一道笔试题,中等难度

yes

面试

团队开发工具之一——Wiki

吴脑的键客

wiki

第一天(VBA, Python最最最基础入门)

橙橙橙橙汁丶

自学 办公自动化 python excel IT蜗壳教学 vba

BI币掌柜量化自动交易机器人开发

#区块链#

如何在子线程中使用Toast显示消息

Geek_416be1

算法攻关 - 从上到下打印二叉树2 (O(n))_offer32

小诚信驿站

刘晓成 小诚信驿站 28天写作 算法攻关 从上到下打印二叉树

基于SparkMLlib智能课堂教学评价系统-相关研究及文献分析(二)

大数据技术指南

大数据 智能时代 28天写作 3月日更

Android源码分析笔记:(2021-3-13)事件分发

Geek_416be1

翻译:《实用的Python编程》05_02_Classes_encapsulation

codists

Python

Wireshark数据包分析学习笔记Day10

穿过生命散发芬芳

Wireshark 数据包分析 3月日更

复盘读书笔记

lenka

3月日更

使用Hadoop相关框架进行网站流量日志分析

五分钟学大数据

大数据 hadoop 28天写作 3月日更

Web安全之XSS

架构精进之路

Web 安全 3月日更

冒泡插入选择排序以及PHP实现

一个大红包

3月日更

竞价实例一小时亏损21万

jinjin

阿里云 抢占式实例 竞价实例 spot

第六次作业

秦挺

5年Java开发,面试4大厂(阿里、拼多多、字节、美团)后,我总结出大厂高频面试真题及解析

Java架构之路

Java 程序员 架构 面试 编程语言

马特量化炒币机器人APP系统开发详情介绍

#区块链#

币BI掌柜量化交易策略APP开发(系统案例)

量化合约跟单交易系统开发软件

#区块链#

如何使用标准稳压器输出几百毫伏极低直流电压?

不脱发的程序猿

28天写作 电路设计 3月日更 电源电路 标准稳压器

深入理解MySQL索引_数据库_杨亨_InfoQ精选文章