右岸 发表于 2024-3-9 23:28:03

MySQL索引底层原理相关问题自总结(难度对标18K-25K薪资,已总结80+,持续

注:以下所有内容均为自己总结的笔记,涉及底层原理,难度对标18K-25K薪资,偏理论,不保证百分百准确性。
索引查找快速的原理?

创建索引的本质是排序,排好序之后再找数据就快了。
对于B+tree索引,B+tree对数据排序后采用多路查找思想的非线性查找方案,减少了大量的查询次数,从而避免多次磁盘io,进而快速找到结果。
为什么推荐用自增id做主键?

自增id直观,且不用刻意维护这个字段,减少工作量,还能避免主键更新引起的页分裂。
举例说明页分裂:数据是存在页上的,页1存储id为1、2、5的数据,如果没有设置自增,如果突然新增了id为3、4的数据,页1无剩余空间存储,就需要将页1数据进行拆分,页1存储id为1、2、3的数据,页2存储id为4、5的数据,分裂的目的是为了排序,排序的目的是为了方便查找。分裂需要消耗计算资源用于更改数据,这种非必要发生的操作就尽量避免。
什么是链表 ,在索引中起到了什么作用?

链表是一种线性数据结构,由节点组成,每个节点包含两部分:数据和指向相邻节点的指针。
链表分单向和双向。
单向:节点只有一个指针,指向下一个节点
双向:每个节点有两个指针,一个指向前一个节点,一个指向后一个节点。
根据对链表的操作,又可以分为队列和栈。
队列:先进先出(LPush->RPop,或Ppush->Rpop)。
栈:先进后出(LPush->LPop,或RPush->RPop)。
MySQL InnoDB引擎和MyISAM引擎,都用的B+tree算法作索引,在叶子节点,每个节点间使用向左或者向右的指针,来移动指针,这也是索引支持区间查询的原因,叶子节点间组成一个链表。
什么是B+tree?

是一种通过排序,方便查找的数据结构,特别是在数据库和文件系统的实现中广泛应用。它是一种平衡树的变体。
平衡性: 所有叶子节点都位于同一层,使得在树的高度方面达到平衡,从而保持高效的查找、插入和删除操作。
有序性: B+树的叶子节点按照键值大小顺序存储,使得范围查询变得更为高效。
多路搜索: 每个非叶子节点都有多个子节点,允许更多的分支,提高搜索效率。
适用于范围查询: 由于有序性和多路搜索的特性,B+树在范围查询方面表现优秀。
在数据库系统中,B+树常被用作索引结构,用于加速对数据库表的查询操作。其设计考虑了磁盘存储的特性,使得在磁盘上的读写操作更为高效。
B+tree比二叉树好在那里?

更加平衡:二叉树在遇到一组非混乱的数据集合下,树的层级会变的很高,意味着io的次数变多,B+tree避开了这个问题。
多路搜索:二叉树为双路搜索,B+tree为多路搜索,极大提高了搜索效率。
查找方便:无论是区间查找还是定值查找,B+tree都比二叉树查找方便,二叉树需要中序遍历才能得到有序序列。
Btree与B+tree区别?

Btree:非叶子节点存放数据,叶子节点无指针,支持区间查找。
B+tree:非叶子结点不存放数据,叶子节点有指针,支持更快速的区间查找。
正因为Btree非叶子节点存放数据,查询起来无法像B+tree一样叶子节点间依靠链表进行范围查询,所以区间查询效率低。
Btree做查找,需要在叶子节点和非叶子节点之间来回跳跃搜索,来回的跳跃,意味着需要更多的磁盘io,而B+tree只需要从非叶子节点到叶子节点即可,
所以稳定性不如B+tree。
为什么MySQL采用B+tree?

查询高效:因为B+tree采用多路非线性查找思想,降低树的层级,减少磁盘io。
支持区间查询:因为数据全在叶子节点上,每个节点之间有指针做关联。
算法稳定:不会向二叉搜索树那样,层级和数据有关,查找情况时好时坏。
页根页之间怎么关联?

双向链表。
双向链表因为有序,所以可以适用二分查找。
双向链表,链的是行中存储的元数据,这归行格式管理,行格式存储的其中一项叫做record_type,有4个值,0表示普通用户记录,1表示目录项纪录,2表示当前页的最小值,3表示当前页的最大值。
使用0和1区分是目录页还是数据页。使用2和3走索引时用于定位,进行区间或等值查找。
为什么数据在页上,页本身要加索引?

虽然一个页可以存储多条数据,但是在大数据情况下,一个页不够存就需要多个页,为了避免查找数据时数据不用对大量的页挨个遍历。与是也加上了B+tree用于查找。
B+tree 叶子节点之间怎么关联

双向的指针。
什么是聚簇索引?

在InnoDB引擎中,索引的叶子节点存储的是实际的数据行,数据即索引,索引即数据。
好处就是能带来快速的查询速度,通过索引就可以找到实实在在的数据。
一般一个表只能有一个聚簇索引,一般为主键,因为数据的排列就是按照索引来的,如果一个表中有多个聚簇索引,一是不知道二级索引参考哪个,二是太占空间。
MyISAM有聚簇索引吗?

没有。
查看MyISAM的二进制文件,有.MYI(存储索引)和.MYD(存储数据)后缀结尾的文件,他们的索引和数据是分开的,不符合数据即索引,索引即数据的特点。
MyISAM的叶子结点存储的是数据的位置信息。
MyISAM中B+tree的叶子节点存储的是数据的地址,也需要类似回表的操作,为什么性能也不慢?

因为寻址的性能也挺高的,如果速度慢,就不会这么主流了。
为什么InnoDB比MyISAM有更好的并发性能,是因为索引上有什么不同之处吗?

不是,并发性和不同引擎的索引没有太多相关性。
InnoDB有更好的并发性能,是因为它支持粒度更小的行级锁,并发情况下,事务用于保持数据一致性,锁是并发控制必备的机制。
为什么InnoDB不推荐用较长的数据做主键?

大数据情况下,InnoDB引擎创建的二级B+tree索引,叶子节点是主键,较长的主键,会占用更多的位置。
而MyISAM中B+tree的叶子节点,存储的是数据的位置。
如何区分一棵B+tree是不是聚簇索引?

看这颗树的叶子节点上,存储的是实实在在的数据,还是根据当前列关联的主键。
聚簇索引的优点?

把实实在在的数据当索引,不用回表,性能很高,因为通过索引找到的那条数据,就是所在行的数据。
InnoDB引擎,MySQL 默认情况下使用自增主键作为聚簇索引,这便是主键查询快的原因。
聚簇索引的缺点?

如果插入的数据不是自增的数字id,可能引起索引分裂,降低性能。
占用较大的空间。
为什么主键查询性能很高?

InnoDB引擎,MySQL 默认情况下使用自增主键作为聚簇索引,不用回表。这便是主键查询快的原因。
具有唯一索引,定值查找,查到后不必接着找。
为什么不建议用UUID作为主键?

避免索引分裂,影响插入数据时的性能问题。
必须要明白,索引的本质是排序,索引查找的本质是根据排好序的数据进行查找。
可能后生成的uuid,根据ASCII码字典排序,会排到先生成uuid的前面,插入新值,则需要重新排序,就要破坏掉原本的索引结构,这个过程将消耗时间和算力。
c3dc38e1-8db2-4e9f-9fe4-735e88facdb4,像是这种类型的数据叫做uuid。
一般有两个好处:

[*]在分布式环境下保证唯一性,因为够长且重复概率太低,否则,A模块的id=1,可能会与B模块的id=1混淆。
[*]黑客不容易猜到相邻的uuid是什么,就算程序有越权漏洞,也不会很难根据原ID猜测其它ID。
其次是uuid,占用空间比int类型更大,使得其它二级索引,存储主键时,占用更多的空间。
用自增id就不会出现索引分裂的情况吗?

不是的。
自增的有序id,只会减少插入数据时的分裂,当大数据时的新增引起的B+tree分层,或者对数据的的插入和删除操作,都可能为了局部重建索引,触发分裂操作。
什么是非聚簇索引?

非聚簇索引则将索引与实际数据行分开存储,索引的叶子节点存储的是当前索引值与主键(MyISAM则是当前索引值与行地址),不是所在行的数据。
什么是二级索引?

级索引通常指的是除了表的主键之外创建的额外索引。
什么是辅助索引?

一般是指非聚簇索引或者二级索引。
什么是回表?

InnoDB引擎,在非聚簇的B+tree索引上,树的叶子节点存储的是当前索引字段数据和主键的值,当前的叶子节点数据与主键做逻辑上的关联,而不是存储所在行的全部数据,所以需要根据主键,再次查询一遍数据,这个过程叫回表。
因内部多了一轮的查询流程,所以性能有所降低,所以能用主键查询的场景,就不要使用其它字段。
为什么不通过像聚簇索引一样的方式避免回表?

技术上能实现,但是缺点很明显,空间换时间的代价太大。
在非聚簇的B+tree上,树的叶子节点重复存储所在行的值,会造成大量的空间浪费。
其次是更新代价太大,可能更新一小块数据,就需要对这些索引上的数据做同步更新。
所以做逻辑关联更好。
为什么插入、更新、删除数据时,非聚簇索引比聚簇索引性能略高?

插入数据引起的索引分裂问题,非聚簇索引只需要调整当前索引的位置和主键就好,而非聚簇所以需要移动整行的数据。
什么是联合索引?

组合索引、复合索引、多列索引,联合索引一个意思,多个字段组合去创建索引。
索引排序规则:先按照左边的字段进行排序,如果左边字段相同,再根据右边的字段排序。
什么是前缀索引?

MySQL 前缀索引是一种,它只对列值的前部进行索引,而不是对整个列值进行索引。
做法:alter table 表名 add index (filed_name(长度));
优点:主要用于控制索引大小,由于底层在比较时字符串长度较短,所以比较起来也比单列索引块。
缺点:有误差,所以需要在空间和产品服务方面做取舍。
评估设置长度:需要根据数据情况测试,如果count(distince left('字段名', 10)) / count(*) 等于1左右,说明截取字段前10个字符去重后的数量,等于总数,说明依照前10个字符就能辨识度很高。如果结果略小于1,说明辨识度还不够,可以取12,如果远小于1,长度取20再试试,以此类推。
补充:《阿里巴巴Java开发手册》【强制】在varchar简历索引时,必须指定索引长度,没必要对全字段建立索引,根据实际文本区分度决定索引长度。
联合索引算不算聚簇索引?

相似但不算,联合索引关联的不是所在行的全部字段,而是部分字段。
为什么单表数据不能超过2000万条

这是个粗略的理论值,很多人说超过这个数,会把B+tree的层级转为4层,其实不准的。
这个还是要看叶子节点数据的大小,如果叶子结点很大,需要更多的页,则存不了太多,如果叶子节点数据很少,有人推算,存1个亿也没问题的。
先排除一些元数据的存储:数据存储在页上,每页大小16KB,每页需要开辟一些新的空间来存储元数据(例如指向上一页下一页的指针),页头存储文件头38字节,页面头56字节,最小记录和最大记录26个字节,为了保证不出错,出现了校验和的机制,这块功能的存储被放到了页尾,占8个字节。页里的数据呢,为了方便查找每行的数据,所以包含页目录(采用二分法,把查询复杂度从O(n)优化为O(log n)),这也占空间,这些可以粗略的估计为占用了1KB。
声明代数:假设非叶子节点指向叶子节点的指针数量为X,叶子节点能够容纳的行数为Y,B+tree层数为Z,那么能存储的总行数就是Xz-1 * Y。
计算X:主键假设用bigint,占8个字节,页号这个元数据占4个字节,非叶子节点一条数据占12个字节,15KB / 12B = 1280。
计算Y:假设一个行数据为1KB,也就是说可以放15条数据。
若Z为1:12800 * 15 = 15行
若Z为2:12801 * 15 = 19200行
若Z为3:12802 * 15 = 24576000行
若Z为3:12803 * 15 = 31457280000行
但是这是理想情况,很多主键id都用无符号int,能节省4个字节,行数大小也不确定,所以这是个理论值,究竟是多少,需要根据实际情况讨论。
什么是最左匹配原则?

生效的情况:
abc创建联合索引,where a = 'v1' and b = 'v2' and c= 'v3',where顺序可以颠倒,但是必须都是and,左边的列不能包含区间查询。
失效的情况:
多字段创建联合索引,如果联合索引左边的字段的查询条件不存在,或者联合索引左边字段使用的区间查询,或者使用了or,都会导致索引失效。
注意,这里说的顺序,是联合索引的顺序,不是where条件的顺序。
底层什么原因导致最左匹配原则?

B+tree联合索引排序,是根据ASCII码的字典顺序进行从左到右依字符排序,然后依字段从左到右排序,没有其它方向的排序,这就不能兼容更多种的查询方式。
假如abc三个字段创建联合索引,where a = v1 and b = v2 and c = v3,此时字段索引的使用情况?

每个字段都能用上索引。
假如abc三个字段创建联合索引,where a = v1 or b = v2 or c = v3,此时字段索引的使用情况?

a能用上索引,b和c都无法使用索引,因为and是属于流水线式的筛选,而or是与前面的搜索条件不相关的个体,b和c都没有左边的字段配合成为联合索引。
假如abc三个字段创建联合索引,where a = v1 and b > v2 and c = v3,此时字段索引的使用情况?

a能用上索引,b能用上索引,c无法使用上索引,因为b是区间查询导致c无法按索引查询。
假如abc三个字段创建联合索引,where a = v1and c = v3,此时字段索引的使用情况?

a可以用上索引,c用不上索引,因为缺少b。
假如abc三个字段创建联合索引,where b = v1and c = v3,此时字段索引的使用情况?

b和c都用不上索引,因为缺少a。
假如abc三个字段创建联合索引,where a = v1 and b = v2 and c = v3 or c is null,此时字段索引的使用情况?

abc三个字段全部能用上索引。
假如abc三个字段创建联合索引,where a = v1 and b = v2 and c = v3 or d + 1 = 10,此时字段索引的使用情况?

用explain实测,type为all,索引用不上了,全表查,因为使用了表达式。
假如abc三个字段创建联合索引,where a = v1 and b = v2 and c = v3 and d + 1 = 10,此时字段索引的使用情况?

用explain实测,type为ref,并根据key_len字段评估,abc都能使用索引。
假如abc三个字段创建联合索引,where a = v1 and b = v2 and c = v3 and length(d) < 20,此时字段索引的使用情况?

用explain实测,type为ref,并根据key_len字段评估,abc都能使用索引。
假如abc三个字段创建联合索引,where a = v1 and b = v2 and c = v3 or length(d) < 20,此时字段索引的使用情况?

用explain实测,type为all,索引用不上了,全表查,因为使用了函数。
假如abc三个字段创建联合索引,where a = v1 and b = v2 and c = v3 or c = v4,此时字段索引的使用情况?

用explain实测,type为all,索引用不上了,全表查,因为c列没有建索引。
假如abc三个字段创建联合索引,where a = v1 and b = v2 and c = v3 and c = v4,此时字段索引的使用情况?

用explain实测,type为ref,并根据key_len字段评估,abc都能使用索引。
假如abc三个字段创建联合索引,where a > v1 and b = v2 and c = v3,索引失效,explain type为all,数据量大还经常查询,怎么办?

创建bca的联合索引即可,alter table 表名 add index(b,c,a),每个字段,最好加上索引长度。
abc的联合索引,如果用不上,删掉。alter table 表名 drop index 索引名。
为什么不推荐mysql频繁使用null值?

null值是个特殊的存在,在sql查询上,即使是唯一索引列,也允许插入多个null值,这影响了了唯一索引的唯一性约束。
其次有些查询,用where field = '',或者where filed = null,都是匹配补上的,只能用is null。
null值影响聚合函数的使用,导致count(字段)结果不符合真实情况。
否则就难以区分到底是没有关联记录还是其他情况。
什么是索引下推?

索引下推简称ICP,优化SQL执行的一种策略,将where条件下推至存储引擎执行,减少回表的数据量提高性能。
一般是针对二级索引说的,有多个where条件时,执行完第一个条件不着急回表,用剩余的数据再次执行第二个where条件,减少回表的数据量。
索引下推常见在联合索引中,只有使用了联合索引中的字段的时候,才可以。
举例:百万条数据,第一次where之后剩下1000条,执行完第二次where后身下5条,只需要回表5条数据即可,避免第一次where条件剩下的1000条数据回表,然后在执行第二个where,再回表。
为什么有覆盖索引时,不支持索引下推?

使用了覆盖索引,说明索引的数据满足了当前select查询,不需要回表,已经不需要下推了。
索引下推有个暗含的前提,是索引无法完全满足当前查询前提的优化策略,且where的字段又包含在联合索引中,索引下推的终极目的是减少回表数据数量,既然不需要回表,那就不需要下推。
为什么相关子查询,不支持索引下推?

相关子查询,指的是子sql与父sql的参数动态关联,这会导致子SQL语句的参数处于动态(不确定)状态,导致索引下推的目标都无法确定,所以不行。
什么是mysql filesort?

这是mysql explain中Extra中可能会展示的东西,当然也是一种机制,在order by的场景中去用。
这种方式指的是在内存中排序,效率略低,因为没有按照索引排序,尽量避免。
与之相对的,有个index排序,可以按照索引自然而然的排序,效率偏高。
filesort两种排序算法是什么?

双路排序:相对较慢。先找到orderby的列,然后排序,再根据排序的字段查找其它字段,类似回表,所以慢。其次相对于单路排序更可能发生随机io,order by排序后的数据,可能不在同一个页上,这个过程需要来回的读取页中的数据。
单路排序:相对较快,根据orderby的列,一次性取出来所有字段,然后再排序。
什么是覆盖索引?

要查询的字段上有索引,索引中的字段涵盖了select字段的结果,因为不需要回表操作去查询整行数据,避免回表的随机io(回表的数据可能不在同一个页上),这是一种性能优化的提现。
需要尽可能少select 字段的数量,避免使用select *。
什么情况下not in、is not null、、!=,左%能用上索引?

覆盖索引。
要查询的字段上有索引,不用回表,卸掉了一个重担,MySQL优化器认为这代价不大,所以选择用索引。
这种情况下,explain type为index。
什么是Hash索引?

基于哈希表实现的索引结构,用于快速定位数据的存储位置。在Hash索引中,索引键通过哈希算法计算得到一个哈希值,该哈希值指向存储数据的具体位置,从而实现快速的查找和定位。
MyISAM和InnoDB都支持哈希索引吗?

都不支持,只有Memory引擎支持。
并且不支持区间查找,所以索引主要依靠B+tree。
where条件的顺序会影响使用索引吗?

如果都是and,则不影响。
MySQL有个东西叫做优化器,它会根据查询的字段,筛选的字段,索引情况自动调整。
order by调整顺序会影响结果。
where条件左边的or遇见右边的and,谁会先执行?

or的优先级比and更小,会先执行右边的and,再执行左边的or,所以要控制好。避免索引失效。
那些查询适合创建索引?

<ul>需要唯一性约束兜底的字段。
经常被查询或者作为where条件的字段,=、>、join on->where->group by->having->select->order by->limit,确实where在limit前面。
但是MySQL Server有个查询优化器的东西,大概是预加载了limit,在where环节找到数据后立马停止。
本问题没有找到官方说明,只是个人推断。
推断过程如下:
随便找了一个省市区县镇的四级联动的表,共46462条数据,name字段为中文,无索引,所以该字段where是全表扫描。
把全表数据复制了32遍,共1486784条数据,执行select * from address where namelike'%北京%',不加limit 1用时11.62秒,加上limit 1用时0.04秒,性能提升几百倍,如果limit在where全部取筛选数据后在截取,指望着限制条目,性能就提升几百倍,几乎不可能。因为最耗时过程是where环节的全表扫描,所以才猜测是预加载了limit,在where查询数据数量符合limit值时就直接中断。</p>
来源:https://www.cnblogs.com/phpphp/p/18062304
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!
页: [1]
查看完整版本: MySQL索引底层原理相关问题自总结(难度对标18K-25K薪资,已总结80+,持续