索引是数据库提供的利于快速查询的机制,索引类似于书籍目录,当查询条件那一列建立了索引之后,那么数据库会去硬盘索引文件中找到满足查询条件的(数据的)物理位置, 根据位置就可以定位并获取到数据。
2.2 索引的种类有哪些?(重点)
会开启 MySQL 慢查询,设置一个时间阈值,对耗时较长(超过设计阈 值)的 sql 语句进行优化,SQL 优化,其实就是从查询效率和消耗资源入手,核心原理就一 个,别让索引失效,避免全表扫描。
对查询进行优化,应尽量避免全表扫描,首先应考虑在 where 及 order by 涉及的列上建立索引。
优化后通过 explain 查看 SQL 优化后的效果。可以看到该 sql 的索引命中情况 (type 字段值类型为 “ALL”表明没有命中索引,进行的全表扫描;值为”where”命中索引 )
哈希索引是基于哈希表实现,哈希表是一种key-value
的数据结构,能够通过key以近乎O(1)的时间复杂度获取到value的值,因此,对于等值查询(=,in)的性能非常高。
B 树(B-Tree)是一种多路平衡查找树,它的每个节点最多可以存储 m 个关键字(m ≥ 2),并且有 m + 1 个指向子树的指针,每个节点的关键字从小到大排列,且各个关键字之间相互独立,不重复。B 树具有如下特性:
一文详解 B-树,B+树,B*树 - 知乎 (zhihu.com)
在前面我们只是简单的提了一下B+树,相信大家对B+树都有了一些了解,现在,让我们来深入探讨一下B+树。
好了,回归正题,前面我们讲了InnoDB数据页的结构,知道了在各个页之间会形成双向链表,而在页内,会以单链表的形式链接每一行
好了,说到链表,鼠鼠来打个广告,hhh
这是之前我写的关于链表的文章,感兴趣的同学可以看一看:【数据结构】异或双链表–拥有单链表的空间,效率如双链表 – Karos (wzl1.top)
要学一个东西,我们得先知道这个东西拿来干嘛的,对吧
而B+数我们主要就是用于快速查询,好了,下面我们来说一说 快速查询
在没有索引的条件下,我们使用条件对列进行精确匹配
select [列名] from 表名 where 列名 = xxx;
当表中的数据量较小的时候,我们只有一页,那么下面的查找分两种情况
哎,要是这里能够将其他列和主键更直接的建立联系就好辣
在这种情况下我们要查找得分两个步骤,如下:
在没有索引的情况下,我们得先找到所在页,所以外层暴力循环,内层二分查找加暴力,$O(n^2logn)$,
wc,太慢了,好了,马上讲讲索引优化
老规矩,先来提前说一下啊,建表
mysql> CREATE TABLE index_demo(
-> c1 INT,
-> c2 INT,
-> c3 CHAR(1),
-> PRIMARY KEY(c1)
-> ) ROW_FORMAT = Compact;
--------------------------------------
Query OK, 0 rows affected (0.03 sec)
下面是简化后的行格式示意图,其中record_type和next_record是记录头信息,c1列也是row_id,其他信息里面包含了事务ID和回滚指针和记录的其他信息,具体的可以看我之前的文章深入浅出——InnoDB记录结构详解,菜鸡看了直呼:能懂! – Karos (wzl1.top)
record_type:0 表示普通记录、 2 表示最小记录、 3 表示最大记录
next_record:到下一个记录的地址偏移量
为了节省点篇幅,在后面的内容中,我们把其他信息去掉
那么我们把多个记录放在页中的时候,结构图如下:
由于按照某个搜索条件来查找记录,而页中的记录又没有对于对应字段的普遍规律,所以我们不得不遍历所有数据页。
那么如何快速定位呢?
其实我们可以联想一下页目录,靠主键值快速定位,那么我们这里可以按照之前页目录来实现一下,实现一个建议目录,这个目录满足下面的条件
那么我们先来insert一组数据(之前在讲页结构的时候,我们提过,一页的大小最大为16kb,但是这里我们为了后面方便描述,==假设一页最多只有3条记录==)
mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)
-----------------------------------------------
Records: 3 Duplicates: 0 Warnings: 0
那么,此时的内存结构是这样:
可以看到,我们放到了10号页中(为什么是10号,而不是1号?呃呃呃,这个地方,其实页的编号是随机的,在内存中,页的地址也不是连续的,后面也是这样)
在此时如果我们要加入一条row_id为4的数据的话,就像这样
这里也好是随机的,刚才已经说过了,这里反复强调一下,hhh
但是,这里为了我们方便查找,我们还得再插入之前其实还有个步骤,所以说上面的方式是错误的。
先把row_id=5的记录放到Page28中
再将row_id=4的记录放到Page10中
这个过程表明了在对页中的记录进行增删改操作的过程中,我们必须通过一些诸如记录移动的操作来始终保 证这个状态一直成立:下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程 我们也可以称为==页分裂==。
当我们插入多条数据后,就是这样的效果:
但是这样仍然不方便管理,不知道大家有没有学过静态链表,其实这里可以用类似静态链表的方式来管理
没错,就是把记录每一个页的地址,下面说一说吧,其实你也可以认为是建了个hash
key是页的最小记录row_id,value是poage_no
然后这里怎么做呢,还是二分,哈哈哈
对目录进行按key排序
比如你要找row_id=20的数据
第一步,20和5比较,往右划分
第二步,20比12大,选择12
通过Key=12找到page_no=9,再依次遍历(实际上是对page中的slot进行二分后再遍历,具体的过程之前讲页结构的时候已经讲过)
到这里,页的建议目录就做好了,没错,它就是==索引==
woc,这就是索引?也不难嘛!
轻轻松松拿捏!
先别急,其实这个只是简单方案,存在一些问题
那么为了解决这类问题,InnoDB的开发者选择了这样一种设计方式:
呃呃呃,说了句废话,其实就是记录头信息中record_type=1
那么这时候就变成了这个样子
当然,目录项记录和用户记录除了结构上面的区别和记录类型的区别之外,还有一点,就算这个
只有存储在目录项记录的最小记录才会有这个标记。
这个图似曾相识?(可以和B+树甚至于B*树联想一下)
当数据多的时候就变成了这样
wc,那么当数据再多的时候,我们又会发现一个问题,我们有需要去记录 目录项记录的记录,或者说是索引,那么,程序员最喜欢的路子来了,套娃,没错按照之前的思想,在对目录项记录进行一个套娃
比如我们要找220,那么首先会在Page33里面进行二分,然后进入1,在里面再次二分,进入209,然后再二分找到220所在的slot,最后再遍历,找到220.
细心的话可以发现,这里是我们之前讲过的B*树,我们可以简化一下,节点中的内容直接省略,然后第二层的前驱后继有点碍眼,我们去掉,最后简化,就成为了一颗B+树
从上面可以看出,其实实际的用户记录全部存储在底层节点上,为了方便讨论,InnoDB的开发者们规定,存放用户记录的那层为第0层,出去叶子节点/叶节点和根节点意外的叫 非叶子节点/内节点 一次往上面加。
其实在真实的环境中,我们可以存储的数据量非常大
假设,假设,假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录,所有 存放目录项记录的内节点代表的数据页可以存放1000条目录项记录,那么:
如果 B+ 树只有1层,也就是只有1个用于存放用户记录的节点,最多能存放 100 条记录。
如果 B+ 树有2层,最多能存放 1000×100=100000 条记录。
如果 B+ 树有3层,最多能存放 1000×1000×100=100000000 条记录。
如果 B+ 树有4层,最多能存放 1000×1000×1000×100=100000000000 条记录。
但是,你的表里能存放 100000000000 条记录么?所以一般情况下,我们用到的 B+ 树都不会超过4层,那我们通过主键 值去查找某条记录最多只需要做4个页面内的查找(查找3个目录项页和一个用户记录页),又因为在每个页面内有所谓的 Page Directory (页目录),所以在页面内也可以通过二分法实现快速定位记录,这不是很牛么,哈哈!
在上面我们讲到,B+树,现在我们针对B+树的特点来进行分析
我们把具有这两种特性的 B+ 树称为 聚簇索引 ,所有完整的用户记录都存放在这个 聚簇索引 的叶子节点处。这 种 聚簇索引 并不需要我们在 MySQL 语句中显式的使用 INDEX 语句去创建(后边会介绍索引相关的语句)。
InnoDB 存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是,在 InnoDB 存储引擎中, 聚簇索引 就是数 据的存储方式(所有的用户记录都存储在了 叶子节点 ),也就是所谓的索引即数据,数据即索引。
通过上面的解释,不难发现,聚簇索引只有在搜索条件是主键的时候才能够使用,因为B+树是按照主键进行排序的
那么,如果我们要用其他键来查找呢,暴力遍历?
nonono!这里大不了再建几颗二叉树就可以了
但是这颗二叉树,是非聚簇索引,来看看具体的区别吧(假设这里我们是以c2列进行查询的):
为什么这里不直接存储用户数据?
答:您的空间真的大<img src="http://gd.7n.cdn.wzl1.top/typora/img/image-20230617043153032.png" alt="image-20230617043153032" style="zoom:25%;" />
具体的二分和聚簇索引差不多,这里就不再讲了,每次都要讲一遍浪费时间,这里其实拿到c2列和row_id以后,会根据row_id再到聚簇索引里面去找到完整的用户记录,这个过程叫做 回表
顾名思义,就是联合查找的时候会用到的索引。
这里按照c2、c3的大小进行排序,对了,注意最左原则,所以应该先按照c2的大小进行排序
具体的步骤如下:
这里其实也是个二级索引,只不过在记录、目录项中都加了c3字段,需要注意的是和分别对c2、c3两列进行二级索引是不同的
在之前介绍B+树的时候,我们先建立的叶子节点,在建立内节点,主要是为了方便大家理解,现在,我们来说一下,InnoDB实际建立B+树的过程:
这里其实要提一下,一个B+树的根节点在被创建之后,是不会发生移动的,这样是为了保证在以后InnoDB在用到该表的同一个索引时,不用重复创建,直接通过重复的地方取出根节点的页号,从而访问这个索引
目录项记录由c2:page_no组成,但是c2并不是主键,可能出现相同情况
如该表,为c2列建立B+树后是这样的
小蝌蚪经历二分后,来到岔路口,我到底该进Page4还是Page5呢,进不了巢啊!
为了避上述懵逼问题发生,让新插入记录能够找到自己所在页,前提是需要保证B+树同一层节点目录项记录除了页号这个字段以外是唯一的,所以二级索引内节点其实有3部分组成:
添加后也就是个这样
这时候如果还需要继续插入c2=1的值的时候,由于索引相同,那么就可以通过比较主键大小来确定最后走向。
我们前边说过一个B+树只需要很少的层级就可以轻松存储数亿条记录,查询速度杠杠的!这是因为B+树本质上
就是一个大的多层级目录,每经过一个目录时都会过滤掉许多无效的子目录,直到最后访问到存储真实数据的目
录。
那如果一个大的目录中只存放一个子目录是个啥效果呢?那就是目录层级非常非常非常多,而且最后的那个
存放真实数据的目录中只能存放一条记录。费了半天劲只能存放一条真实的用户记录?逗我呢?所以 InnoDB 的
一个数据页至少可以存放两条记录,这也是我们之前唠叨记录行格式的时候说过一个结论(我们当时依据这个结
论推导了表中只有一个列时该列在不发生行溢出的情况下最多能存储多少字节,忘了的话回去看看吧)。
MyISAM虽然也是采用的树形结构来存储,但实际,他是把索引和数据分开存储。
MyISAM记录也需要记录头信息来存储一些额外数据,以前文为例,如图
可惜的是,在我们插入数据是并没有可以按照主键大小排序,所以啊,这次不能使用二分法来进行查找辣
那么MyISAM是如何实现快速查找的呢,总不可能暴力吧。
下面我们来说一说:
这一点和 InnoDB 是完全不相同的,在 InnoDB 存储引擎中,我们只需要根据主键值对 聚簇索引 进行一次查 找就能找到对应的记录,而在 MyISAM 中却需要进行一次 回表 操作,意味着 MyISAM 中建立的索引相当于全部都是二级索引.
MyISAM的行格式有定长记录格式(Static)、变长记录格式(Dynamic)、压缩记录格式(Compres sed)。上边用到的index_demo表采用定长记录格式,也就是一条记录占用存储空间的大小是固定 的,这样就可以轻松算出某条记录在数据文件中的地址偏移量。但是变长记录格式就不行了,MyIS AM会直接在索引叶子节点处存储该条记录在数据文件中的地址偏移量。通过这个可以看出,MyISAM 的回表操作是十分快速的,因为是拿着地址偏移量直接到文件中取数据的,反观InnoDB是通过获取 主键之后再去聚簇索引里边儿找记录,虽然说也不慢,但还是比不上直接用地址去访问。
MyISAM数据文件和索引文件:
image-20230617080003602
like要详细说一下,
%x 索引失效
%x% 索引失效
x% 索引下推
索引下推的下推其实就是指将部分上层(服务层)负责的事情,交给了下层(引擎层)去处理。
MySQL大概架构在5.6之前,server层获取获取所有索引,再交给引擎层进行where判断,如图(回表这个词在后面会讲)
未使用ICP在5.6之后,MySQL推出了 索引下推来对sql进行优化
当存在索引的列做为判断条件时,MySQL server将这一部分判断条件传递给存储引擎,然后存储引擎会筛选出符合MySQL server传递条件的索引项,即在存储引擎层根据索引条件过滤掉不符合条件的索引项,然后回表查询得到结果,将结果返回给MySQL server。
使用ICP的示意图索引下推使用条件
只能用于
range
、ref
、eq_ref
、ref_or_null
访问方法; 只能用于InnoDB
和MyISAM
存储引擎及其分区表; 对InnoDB
存储引擎来说,索引下推只适用于二级索引(也叫辅助索引);索引下推的目的是为了减少回表次数,也就是要减少IO操作。对于
InnoDB
的聚簇索引来说,数据和索引是在一起的,不存在回表这一说。引用了子查询的条件不能下推; 引用了存储函数的条件不能下推,因为存储引擎无法调用存储函数。
相关系统参数
索引条件下推默认是开启的,可以使用系统参数
optimizer_switch
来控制器是否开启。查看默认状态:
mysql> select @@optimizer_switch\G; *************************** 1. row *************************** @@optimizer_switch: index_merge=on,index_merge_union=on,index_merge_sort_union=on,index_merge_intersection=on,engine_condition_pushdown=on,index_condition_pushdown=on,mrr=on,mrr_cost_based=on,block_nested_loop=on,batched_key_access=off,materialization=on,semijoin=on,loosescan=on,firstmatch=on,duplicateweedout=on,subquery_materialization_cost_based=on,use_index_extensions=on,condition_fanout_filter=on,derived_merge=on 1 row in set (0.00 sec)
切换状态:
set optimizer_switch="index_condition_pushdown=off"; set optimizer_switch="index_condition_pushdown=on";
部分内容参考于《MySQL是怎样运行的:从根儿上理解MySQL》、五分钟搞懂MySQL索引下推 - 掘金 (juejin.cn)
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。