不会MySQL索引,面试官让回家等通知!

原创
02/06 11:50
阅读数 4K

索引是面试必不可少的内容,接下来带你进入MySQL索引的世界。

  • 1. Btree解析
  • 2. B+Tree解析
  • 3.Hash索引
  • 4. B+Tree跟BTree区别
  • 5. B+Tree适合做索引的原因
  • 1. 回表
  • 2. 覆盖索引
  • 3. 最左匹配
  • 4. 索引下推

前言

你是不是对于MySQL索引的知识点一直都像大杂烩,好像什么都知道,如果进行深究的话可能一个也答不上来。

假如你去面试,面试官让你聊一下对索引的理解,然而你对索引的理解仅限于,检索数据就是快,是一种数据结构这个层面,那你就只能回家等通知了。

为了避免这种尴尬的事情发生,咔咔用时两天将索引的内容在自己理解的范围内进行整理,如整理的不全面可以在评论区进行补充和提建议。

一、MySQL索引到底是什么

相信大多数伙伴都买过技术类的书籍,看完没看完不知道,但是目录肯定看的次数最多。

看目录有没有自己目前的痛点,如果有就会根据目录对应的页码用最快的速度翻阅到相应内容位置。

那么在MySQL中同样也是这样的一个道理,MySQL的索引就是存储引擎为了快速找到数据的一种数据结构

同样在MySQL索引中又分了几种类型,分别为B-tree索引、哈希索引、空间索引、全文索引。

下文所有内容均在Innodb的基础上讨论。

二、为什么要使用索引

索引可以加快数据检索速度,这也是使用的索引的最主要原因。

索引本身具有顺序性,在进行范围查询时,获取的数据已经排好了序,从而避免服务器再次排序和建立临时表的问题

索引的底层实现本身具有顺序性,通过磁盘预读使得在磁盘上对数据的访问大致呈顺序的寻址,也就是将随机的I/O变为顺序I/O

这几点不理解就暂时先放着,继续看下文即可,会给你一个满意的解释。

任何事物都存在双面性,既然能提供性能的提升,自然在其它方面也会付出额外的代价。

索引是跟数据共存,因此会占用额外的存储空间。

索引创建和维护需要时间成本,这个成本随着数据量的增大而增大。

索引创建会降低数据的增、删、改的性能,因为在修改数据的同时还需要修改索引数据。

三、Innodb为什么使用B+Tree而不使用BTree

聊到这个问题那就必须得分清楚BTree、B+tree的区别,首先来看一下BTree

1. Btree解析

先来看一下BTree的数据结构是怎么样的,这里咔咔给提供一个网站地址https://www.cs.usfca.edu/~galles/visualization/Algorithms.html,可以看到关于数据结构的一些实现过程。

数据结构实现过程

数据结构实现过程

先来看BTree的数据结构,下图是咔咔已经将数据填充进去的。

BTree数据结构

BTree数据结构

这里有一个陌生区关于Max. Degree,这个你可以理解为阶,也可以理解为度。

例如现在这个值设置的是4,那么在一个节点中最多就可以存储三条数据,设置为5那就可以最多放4条记录。

现在可以看到目前只插入了三条数据。

插入了三条数据

插入了三条数据

那么再加一条数据,节点就会进行分裂,这个也就验证了当阶设置为n时,一个节点可存n-1条数据。

节点分裂

节点分裂

那接着再来插入几条数据看看。

插入了十条数据

插入了十条数据

想要达到快速检索数据,那就需要满足俩个特性,一个是有序,另一个就是平衡。

从下图中可以看到BTree是有一定的顺序性的,平衡性更满足,可以看上文中生成的第一张图。

顺序性

顺序性

那么在BTree中找一个值是怎么找呢!

例如现在要找一个值9,看一下寻找过程。

首先看到的数据是4,9是大于4的,所以会往4的右节点寻找。

继续找到范围在6到8的节点,9又大于8,所以还需要往右节点寻找。

最有一步就找到了数据9,这个过程就是BTree数据结构查找数据的执行过程。

寻找过程

寻找过程

了解到了BTree的数据结构后,我们在来看看在MySQL中关于BTree是如何存储的。

在下图中P代表的是指针,指向的是下一个磁盘块。

在第一个节点中的16、24就是代表我们的key值是什么。

date就是这个key值对应的这一行记录是什么。

在MySQL中BTree存储结构

在MySQL中BTree存储结构

那么此时想要寻找key为33的这条记录应该怎么找。

33在16和34中间,所以会去磁盘3进行寻找。

在磁盘3中进行判断,指针指向磁盘8。

在磁盘8中即可获取到数据33,然后将data返回。

那么在这个过程中到底读取了多少条数据呢!

在计算之前需要先了解一些知识点。

从MySQL5.7开始,存储引擎默认为innodb,并且innodb存储引擎用于管理数据的最小磁盘单位就是页。

这个页的类型也分为好几种,分别为数据页,Undo页,系统页,事物数据页。

一般说到的页都是数据页。默认的页面大小为16kb,每个页中至少存储2条或以上的行记录。

那么根据BTree数据查找的过程中可以得知一共读取了三个磁盘,那么每个磁盘的大小就是16kb。

而目前的给的案例寻找了三层,那么三层存储的数据就是16kb * 16kb * 16kb = 4096kb。

如果按照一条记录所需内存1kb,那么这三层的BTree就可以存储4096条记录。

各位数据库的数据少则几百万,多则几千万数据,那么BTree的层级就会越来越深,相对的查询效率也会越来越慢。

这个时候是不是应该思考一个问题,那就是为什么在Btree中48kb的内存怎么就只能存储4000多条记录

问题就出现在data上,要知道在计算数据大小时指针地址和key的内存都是没有计算在内的,单单就计算了data的内存。

因为在BTree结构中,节点中不仅存储的有key、指针地址还有对应的数据,所以就会造成单个磁盘存储的数据相对很少的原因。

为了解决单个节点存储数据量小的问题,于是就演变出另一种结构,也就是下文提到了B+Tree

2. B+Tree解析

依然如初看一下B+Tree的数据结构。

为了方便对比,将BTree和B+Tree的数据结构放到了一起。

数据结构对比

数据结构对比

那么可以看到在B+Tree中叶子节点是存放了全量的数据,而非叶子节点只存储了key值。

咦!这不是就很好的解决了BTree带来的问题吗?可以让每个节点存储更多的数据。每个节点存储的数据越多,那么相对的就是树的深度就不会过深。

了解到了B+Tree的数据结构后,我们在来看看在MySQL中关于B+Tree是如何存储的。

B+Tree数据结构

B+Tree数据结构

从上图很明显就可以看到俩点不同。

第一点:B+Tree所有的数据都存储在叶子节点上。

第二点:B+Tree所有的叶子节点之间是一种链式环结构

那么在这个过程中到底读取了多少条数据呢!

如果说B+Tree读取数据的深度跟B-Tree的深度一样,都是三层,那么同样的道理每个磁盘的大小为16kb。

那在B+Tree中非叶子节点可以存储多少数据呢!一般来说我们每个表都会存在一个主键。

根据三层来计算,第一层跟第二层存储的是key值,也就是主键值。

都知道int类型所占的内存时4Byte(字节),指针的存储就给个6Byte,一共就是10Tybe,那么第一层节点就可以存储16 * 1000 /10 = 1600。

同理第二层每个节点也是可以存储1600个key。

第三层是叶子节点,每个磁盘存储大小同样安装BTree的计算一样,每条数据占1kb。

那么在B+Tree中三层可以存储的数据就是1600 * 1600 * 16 = 40960000

从这点来看B+Tree存储的数据跟BTree存储的数据根本就不是一个级别。

所以可以得出结论:

B+Tree能保证检索的数据量相对BTree是最多的,而且存储的数据量也是最多的

B+Tree选择索引时尽量选择所占内存空间小的类型,比如int类型。

key所占内存越小,在节点中存储的范围就越多。

3.Hash索引

先来创建一个hash索引alter table user add index hash_gender using hash(gender);

存储引擎使用的是innodb。

hash索引

hash索引

会发现name的索引类型还是为Btree,在innodb上创建哈希索引,被称之为伪哈希索引,和真正的哈希索引不是一回事的,这点一定要明白。

在Innodb存储引擎中有一个特殊的功能叫做,自适应哈希索引,当索引值被使用的非常频繁时,它会在内存中基于BTree索引之上再创建一个哈希索引,那么就拥有了哈希索引的一些特点,比如快速查找

哈希索引就是基于哈希表实现的,假设对 name 建立了哈希索引,则查找过程如下图所示,哈希表是根据键值对进行访问的数据结构,它让检索的数据经过哈希函数映射到散列表的对应位置,查找效率非常高。

哈希索引数据结构

哈希索引数据结构

哈希索引存储的是哈希值和行指针,没有存储key值、字段值,但哈希索引多数是在内存完成的,检索数据是非常快的,所以对性能影响不大。

哈希索引不是按照索引值排序的,所以也就无法排序。

哈希索引只支持等值操作,不支持范围查找,在MySQL中只能只用 =、in 、<>

哈希索引在任何时候都不能避免表扫描

哈希索引在遇到大量哈希冲突时,存储引擎必须遍历链表的所有行指针,逐行比较。

4. B+Tree跟BTree区别

经过了特别漫长的计算、画图现在基本对俩者的区别有一定认识了吧!

咔咔在这里进行总结一下。

  • B+Tree叶子节点上存储的是全量数据(key+data),而非叶子节点只存储key

  • B+Tree在同样的深度下存储的数据是远远大于BTree的。

  • B+Tree每个叶子节点都有指向下一个叶子节点的链接。这样的好处在于,我们可以从任意一个叶子节点开始遍历,获取接下来所有的数据。

5. B+Tree适合做索引的原因

B+Tree树非叶子节点只存储key值,因此相对于BTree节点可以存储更多的数据,每次读入内存的key值就更多,相对来说I/O就降低

B+Tree树查询效率稳定,任何数据的查找都是必须从叶子节点到非叶子节点,所以说每个数据查找的效率几乎都是相同的。

B+Tree树的叶子节点存储的是全量数据,并且是有序的,所以说只需要遍历叶子节点就可以对所有的key进行扫描,在范围查找时效率更高。

以上就是关于Innodb存储引擎为什么使用B+Tree作为索引的解析。

四、聚簇索引、非聚簇索引区别

聚簇索引、非聚簇索引也被称之为主索引、二级索引。

那么如何区分聚簇索引和非聚簇索引呢!

首先看一下Innodb引擎下,创建表生成的文件,可以看到有俩个ibd文件。

数据表文件

数据表文件

看到这里不知道大家有没有疑问,为什么看有的文章中也会有frm文件呢!但是在这里怎么没有呢!

原因是在MySQL8.0之后将源数据都存储到了表空间中,所以也就不存在frm文件喽!

都知道这个idb文件会存储数据信息和索引信息。

那再来看一下Myisam存储引擎创建表生产的文件。

myisam存储引擎创建表生成的文件

myisam存储引擎创建表生成的文件

从图中可以看到创建一个表会生成三个文件,扩展名分别为MYD、MYI、sdi。

MYD:是表数据文件(保存数据的文件)

MYI :是表索引文件(保存索引的文件)

那么就可以得出一个结论

只要数据跟索引存储在一个文件里,那就是聚簇索引,否则就是非聚簇索引。

这个时候就会有人问了,表中有主键的时候,idb文件中存储的是主键+数据,那么当没有设置主键时怎么办呢!

记住这一句话,在Innodb中,数据插入时必须跟一个索引值进行绑定,如果没有主键那就选择唯一索引,如果没有唯一索引就会选择一个6Byte的rowid。

五、表中存在多个索引数据是如何存储的

看了上文的解释,有没有产生过一丝疑问,在Innodb存储引擎下,如果存在多个索引,是不是会产生多个idb文件。

在Innodb中数据只会保存一份,如果有多个索引,会维护多个B+Tree

例如:表字段 id,name,age,sex。

id设置为主键索引(聚簇索引),name设置为普通索引,那么数据到底会存储几份呢!

不管一个表中设置多少个索引,数据只会存储一份,但是这张表会维护多个B+Tree。

按照这个案例中id为主键索引,name为普通索引,那么在这张表中就会维护俩颗B+Tree。

id主键索引跟数据存储在一起,name索引所在的B+Tree中叶子节点存储的是主键id的值。

对应的图就是以下俩幅图,可以好好的看一下。

主键索引对应的B+Tree

主键索引对应的B+Tree

name索引对应的B+Tree

name索引对应的B+Tree

最后给大家总结一个点:在Innodb中,一定有聚簇索引,其它索引都是非聚簇索引。

这里简单提一下myisam中只有非聚簇索引。

六、索引的几个技术名词

在面试中往往会问这几个关键词,分别为回表、覆盖索引、最左侧原则、索引下推,一定要知道哈!

1. 回表

网上对回表的解释各种各样,咔咔给你说种简单易懂的,但前提是你需要把聚簇索引、非聚簇索引区分清楚。

还是用上边的案例,id为主键索引,name为普通索引。

此时查询语句为select id,name,age from table where name = 'kaka'

那么这条语句会先在name的这颗B+Tree中寻找到主键id,然后在根据主键id的索引获取到数据并且返回。

其实这个过程就是从非聚簇索引跳转到聚簇索引中查找数据,被称为回表,也就是说当你查询的字段为非聚簇索引,但是非聚簇索引中没有将需要查询的字段全部包含就是回表。

在这个案例中,非聚簇索引name的叶子节点只有id,并没有age,所以会跳转到聚簇索引中,根据id在查询整条记录返回需要的字段数据。

2. 覆盖索引

覆盖索引,根据名字都能理解的差不多,就是查询的所有字段都创建了索引!

此时查询语句为select id,name from table where name = 'kaka'

那么这条语句就是使用了覆盖索引,因为id和name都为索引字段,查询的字段也是这俩个字段,所以被称为索引覆盖。

也就是说当非覆盖索引的叶子节点中包含了需要查询的字段时就被称为覆盖索引

3. 最左匹配

最左匹配原则是在组合索引中存在的。

还是用之前表信息:表字段 id,name,age,sex。

此时给name,age设置成组合索引。

以下语句中那个不符合最左侧原则。

select * from table where name = ? and age = ?

select * from table where name = ?

select * from table where age = ?

select * from table where age= ? and name= ?

可以自行做一下测验哈!是只有第三条语句不会用到索引,其它的三条语句都会符合最左侧原则。

关于这个最左侧原则远远不止这么简单的,一试就是一个坑,关于这部分内容咔咔后期会在优化文章中提到。

4. 索引下推

还是使用这条sql语句。

select * from table where name = ? and age = ?

索引下推是在MySQL5.6及以后的版本出现的。

之前的查询过程是,先根据name在存储引擎中获取数据,然后在根据age在server层进行过滤。

在有了索引下推之后,查询过程是根据name、age在存储引擎获取数据,返回对应的数据,不再到server层进行过滤。

当你使用Explain分析SQL语句时,如果出现了Using index condition那就是使用了索引下推,索引下推是在组合索引的情况出现几率最大的。

七、索引存储在什么地方

索引的数据文件是存储在磁盘中的,也是需要进行持久化操作。

但是当使用索引时会把数据从磁盘读取到内存中,读取方式为分块读取。

这时就要涉及到操作系统的概念,操作系统在磁盘中获取数据,假设现在要取的数据大小是1kb,但操作系统并不会只取出你需要的这1kb,而是会取出4kb的数据。

为什么会是4kb,因为在操作系统中一页的数据就是4kb。

那又为什么只需要1kb而取出整页的数据呢!

那就又会涉及到另一个概念那就是局部性原理:数据和程序都有聚集成群的倾向,在访问了一条数据之后,在之后有极大的可能再次访问这条数据和这条数据的相邻数据。

所以说MySQL的Innodb存储引擎,在读取数据时也会采取这种局部性原理,每次读取的数据是16kb。

在Innodb存储引擎下每页的大小默认为16kb,这个参数也可以进行调整,参数为innodb_page_size。

最后一点:

既然标题问的是索引数据存储在什么地方,在第一句就直接回答了索引是存储在磁盘中,并且以页为单位进行从磁盘往内存读取。

那为什么不直接存储在内存中呢!你有没有这个疑问呢!

如果索引数据只存储在内存中,那么当电脑关机,服务器宕机之后,就需要重新生成索引,这种的效率是十分低的。

八、总结

以上就是咔咔对索引的理解,在尽最大的可能将知识点说全面。

如果还有遗漏,或者文章中有错误的地方还请各位能给出提议。

展开阅读全文
打赏
2
21 收藏
分享
加载中
打赏
2 评论
21 收藏
2
分享
返回顶部
顶部