前言
当提到 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(主键索引)
ALTERTABLE`table_name`ADDPRIMARY KEY( `column` )
2)添加 UNIQUE(唯一索引)
ALTERTABLE`table_name`ADDUNIQUE(`column`)
3)添加 INDEX(普通索引)
ALTERTABLE`table_name`ADDINDEXindex_name (`column` )
4)添加 FULLTEXT(全文索引)
ALTERTABLE`table_name`ADDFULLTEXT (`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.
然后进行多列查询.
explainselect*from`t_mobilesms_11`whereuserid ='1'andmobile ='13504679876'andbillMonth ='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 *fromuserwhere left(name,3) ='zhangsan'andage =20
这里对 name 字段进行了 left 函数操作, 导致索引失效.
3)使用不等于(!= ,<>)
explain select *fromuserwhere age != 20;
explain select *fromuserwhere age <> 20;
4)like 中以通配符开头 ('%abc')
索引失效
explain select *fromuserwhere name like '%zhangsan';
索引生效
explain select *fromuserwhere name like 'zhangsan%';
5)字符串不加单引号索引失效
explain select *fromuserwhere name = 2000;
6)or 连接索引失效
explain select *fromuserwhere name = '2000'orage = 20orpos ='cxy';
7)order by
正常(索引参与了排序), 没有违反最左匹配原则.
explain select *fromuserwhere name ='zhangsan'andage = 20 order by age,pos;
违反最左前缀法则, 导致额外的文件排序(会降低性能).
explain select name,agefromuserwhere name ='zhangsan'order by pos;
8)group by
正常(索引参与了排序).
explain select name,agefromuserwhere name ='zhangsan'groupby age;
违反最左前缀法则, 导致产生临时表(会降低性能).
explain select name,agefromuserwhere name ='zhangsan'groupby pos,age;
五, 总结
了解一条查询语句是如何执行的, 发现建立索引是一种可以高效查找的数据结构.
了解了索引的各种分类情况, 聚集索引和非聚集索引的区别, 如何创建各种索引.
通过需求一步步分析出为什么 MySQL 要选 b+tree 作为索引的数据结构, 对比了 btree 和 b+tree 的区别, MyISAM 和 innodb 中索引的区别.
了解了索引会失效的多种情况, 比较重要的最左匹配原则, 相应地我们可以在建索引的时候做一些优化.
希望大家能够多去使用索引进行 SQL 优化, 有问题欢迎指出.
文章配图来源于网络
本文转载自公众号宜信技术学院(ID:CE_TECH).
来源: http://www.tuicool.com/articles/m6rmumb