首页 体育 教育 财经 社会 娱乐 军事 国内 科技 互联网 房产 国际 女人 汽车 游戏

索引很难么?带你从头到尾捋一遍MySQL索引结构,不信你学不会!

2019-12-21

Hello我又来了,快年末了,作为一个有志向的码农,我想给自己攒一个年终总结。自上上篇写了 手动树立Redis集群和MySQL主从同步 和上篇写了 着手完结MySQL读写别离and毛病搬运 之后,干脆这次把数据库中最中心的也是最难搞懂的内容,也便是索引,共享给咱们。

create table user
)engine = innoDb;

信任只需入门数据库的同学都能够了解这个句子,咱们也将从这个最简略的表开端,一步步地了解MySQL的索引结构。

首要,咱们往这个表中刺进一些数据。

INSERT INTO userVALUES;
INSERT INTO userVALUES;
INSERT INTO userVALUES;
INSERT INTO userVALUES;
INSERT INTO userVALUES;

咱们来查一下,看看这些数据是否现已放入表中。

select * from user;

能够看到,数据现已完整地放到了咱们创立的user表中。

可是不知道咱们发现了什么没有,如同发生了一件十分怪异的工作,咱们刺进的数据如同乱序了…

MySQL如同悄悄的给咱们依照id排了个序。

为什么会呈现MySQL在咱们没有显式排序的状况下,静静帮咱们排了序呢? 它是在什么时分进行排序的?

不知道咱们结业多长时刻了,作为一个刚学完操作系统不久的学渣,页的概念依旧在脑中还没有变凉。其实MySQL中也有相似页的逻辑存储单位,听我渐渐道来。

在操作系统的概念中,当咱们往磁盘中取数据,假定要取出的数据的巨细是1KB,可是操作系统并不会只取出这1kb的数据,而是会取出4KB的数据,因为操作系统的一个页表项的巨细是4KB。那为什么咱们只需求1KB的数据,可是操作系统要取出4KB的数据呢?

这就涉及到一个程序局部性的概念,具体的概念我背不清了,大约便是“ 一个程序在拜访了一条数据之后,在之后会有极大的或许再次拜访这条数据和拜访这条数据的相邻数据 ”,所以干脆直接加载4KB的数据到内存中,下非有必要拜访这一页的数据时,直接从内存中找,能够削减磁盘IO次数,咱们知道,磁盘IO是影响程序功用首要的要素,因为磁盘IO和内存IO的速度是不可同日而语的。

或许看完上面那一大段描绘,仍是有些笼统,所以咱们干脆回到数据库层面中,从头了解页的概念。

抛开一切东西不谈,假定仍是咱们方才刺进的那些数据,咱们现在要找id = 5的数据,依照最原始的方法,咱们必定会想到的便是——遍历,没错,这也是咱们刚开端学核算机的时分最常用的寻觅数据的方法。那么咱们就来看看,以遍历的方法,咱们找到id=5的数据,需求阅历几回磁盘IO。

首要,咱们得先从id=1的数据开端读起,然后判别是否是咱们需求的数据,假如不是,就再取id=2的数据,再进行判别,循环往复。毋庸置疑,在MySQL帮咱们排好序之后,咱们 需求阅历五次磁盘IO ,才干将5号数据找到并读出来。

那么咱们再来看看引进页的概念之后,咱们是怎样读数据的。

在引进页的概念之后,MySQL会将多条数据存在一个叫“页”的数据结构中,当MySQL读取id=1的数据时,会将id=1数据地点的页整页读到内存中,然后在内存中进行遍历判别,因为内存的IO速度比磁盘高许多,所以相关于磁盘IO,简直能够忽略不计,那么咱们来看看这样读取数据咱们需求阅历几回磁盘IO。

那么咱们第一次会读取id=1的数据,而且将id=1到id=4的数据悉数读到内存中,这是第一次磁盘IO,第2次将读取id=5的数据到内存中, 这是第2次磁盘IO。 所以咱们只需求阅历2次磁盘IO就能够找到id=5的这条数据。

但其实,在MySQL的InnoDb引擎中,页的巨细是16KB,是操作系统的4倍,而int类型的数据是4个字节,其它类型的数据的字节数一般也在4000字节以内,所以一页是能够寄存许多许多条数据的,而 MySQL的数据正是以页为底子单位组合而成的 。

上图便是咱们目前为止所了解的页的结构,他包括咱们的多条数据,别的,MySQL的数据以页组成,那么它有指向下一页的指针和指向上一页的指针。

那么提到这儿,其实能够答复第一个问题了,MySQL实践上便是在咱们刺进数据的时分,就帮咱们在页中排好了序,至于为什么要排序,这儿先卖个关子,接着往下看。

上文中咱们提了一个问题, 为什么数据库在刺进数据时要对其进行排序呢? 咱们按正常次序刺进数据不是也挺好的吗?

这就要涉及到一个数据库查询流程的问题了,无论怎样,咱们是肯定不会去无缘无故地在刺进数据时添加一个操作来让流程复杂化的,所以刺进数据时排序必定有其意图,便是 优化查询的功率 。

而咱们不难看出,页内部寄存数据的模块,实质上便是一个链表的结构,链表的特色也便是增删快,查询慢,所以优化查询的功率是有必要的。

仍是依据咱们第一节中的那张页图来谈,咱们刺进了五条数据,id别离是从1-5,那么假定我要找一个表中不存在的id,假定id=-1,那么现在的查询流程便是:

将id=1的这一整页数据取出,进行逐一比对,那么当咱们找到id=1的这条数据时,发现这个id大于咱们所需求找的哪个id,因为数据库在刺进数据时,现已进行过排序了,那么在id=1的数据后边,都是id 1的数据,所以咱们就不需求再持续往下寻觅了。

假如在刺进时没有进行排序,那毋庸置疑,咱们需求再持续往下进行寻觅,逐条查找直到到结束也没有找到这条数据,才干回来不存在这条数据。

当然,这仅仅排序优化的冰山一角,接着往下看。

说完了排序,下面就来剖析一下咱们在第一节中的那幅图,关于大数据量下有什么坏处,或许换一个说法,咱们能够怎样对这个方式进行优化。

咱们不难看出,在现阶段咱们了解的页方式中,只需一个功用,便是 在查询某条数据的时分直接将一整页的数据加载到内存中,以削减硬盘IO次数,然后进步功用。 可是,咱们也能够看到,现在的页方式内部,实践上是选用了链表的结构,前一条数据指向后一条数据,实质上仍是经过数据的逐条比较来取出特定的数据。

那么假定,咱们这一页中有一百万条数据,咱们要查的数据正好在终究一个,那么咱们是不是必定要早年往后找到这一条数据呢?假如是这样,咱们需求查找的次数就达到了一百万次,即使是在内存中查找,这个功率也是不高的。那么 有什么方法来优化这种状况下的查找功率呢?

咱们能够打个比方,咱们在看书的时分,假如要找到某一节,而这一节咱们并不知道在哪一页,咱们是不是就要早年往后,一节一节地去寻觅咱们需求的内容的页码呢?答案是否定的,因为在书的前面,存在目录,它会告知你这一节在哪一页,例如,第一节在第1页、第二节在第13页。 在数据库的页中,实践上也运用了这种目录的结构,这便是页目录。

那么引进页目录之后,咱们所了解的页结构,就变成了这样:

剖析一下这张图,实践上页目录就像是咱们在看书的时分书本的目录相同,目录项1就相当于第一节,目录项2就相当于第二节,而每一条数据就相当于书本的每一页,这张图就能够解说成, 第一节从第一页开端,第二节从第三页开端,而实践上,每个目录项会寄存自己这个目录项傍边最小的id,也便是说,目录项1中会寄存1,而目录项2会寄存3。

那么比照一下数据库在没有页目录时分的查找流程,假定要查找id=3的数据,在没有页目录的状况下,需求查找id=1、id=2、id=3,三次才干找到该数据,而假如有页目录之后,只需求先查看一下id=3存在于哪个目录项下,然后直接经过目录项进行数据的查找即可,假如在该目录项下没有找到这条数据,那么就能够直接确认这条数据不存在,这样就大大提升了数据库的查找功率,可是这种页目录的完结,首要就需求依据数据是在现已进行过排序的的场景下,才干够发挥其效果,所以看到这儿,咱们应该了解第二个问题了,为什么数据库在刺进时会进行排序, 这才是实在发挥排序的效果的当地。

在上文中,咱们底子上说了解了MySQL数据库中页的概念,以及它是怎样依据页来削减磁盘IO次数的,以及排序是怎样优化查询的功率的。

那么咱们现在再来考虑第三个问题:在最初说页的概念的时分,咱们有说过,MySQL中每一页的巨细只需16KB,不会跟着数据的刺进而主动扩容,所以这16KB不或许存下咱们一切的数据,那么必定会有多个页来存储数据,那么 在多页的状况下,MySQL中又是怎样安排这些页的呢?

针对这个问题,咱们持续来画出咱们现在所了解的多页的结构图:

能够看到,在数据不断变多的状况下,MySQL会再去拓荒新的页来寄存新的数据,而每个页都有指向下一页的指针和指向上一页的指针,将一切页安排起来,第一页中寄存id为1-5的数据,第二页寄存id为6-10的数据,第三页寄存id为11-15的数据,需求留意的是 在拓荒新页的时分,咱们刺进的数据纷歧定是放在新拓荒的页上,而是要进行一切页的数据比较,来决议这条刺进的数据放在哪一页上,而完结数据刺进之后,终究的多页结构就会像上图中画的那样。

在多页方式下,MySQL总算能够完结多数据的存储了,便是选用拓荒新页的方法,将多条数据放在不同的页中,然后相同选用链表的数据结构,将每一页衔接起来。那么能够考虑第四个问题: 多页状况下是否对查询功率有影响呢?

针对这个问题,已然问出来了,那么答案是必定的,多页会对查询功率发生必定的影响,影响首要就体现在,多页其实质也是一个链表结构,只需是链表结构,查询功率必定不会高。

假定数据又十分多条,数据库就会拓荒十分多的新页,而这些新页就会像链表相同衔接在一同,当咱们要在这么多页中查询某条数据时,它仍是会从头节点遍历到存在咱们要查找的那条数据所存在的页上,咱们十分困难经过页目录优化了页中数据的查询功率,现在又呈现了以页为单位的链表,这不是前功尽弃了吗?

因为多页方式会影响查询的功率,那么必定需求有一种方法来优化多页方式下的查询。信任有同学现已猜出来了,已然咱们能够用页目录来优化页内的数据区,那么咱们也能够采纳相似的方法来优化这种多页的状况。

是的,页内数据区和多页方式实质上都是链表,那么确实能够选用相同的方法来对其进行优化,它便是目录页。

所以咱们比照页内数据区,来剖析怎样优化多页结构。在单页时,咱们 选用了页目录的目录项来指向一行数据,这条数据便是存在于这个目录项中的最小数据,那么就能够经过页目录来查找所需数据。

所以关于多页结构也能够选用这种方法,运用一个目录项来指向某一页,而这个目录项寄存的便是这一页中寄存的最小数据的索引值。和页目录不同的当地在于, 这种目录办理的等级是页,而页目录办理的等级是行。

那么剖析到这儿,咱们多页方式的结构就会是下图所示的这样:

存在一个目录页来办理页目录,目录页中的数据寄存的便是指向的那一页中最小的数据。

这儿要留意的一点是:其实 目录页的实质也是页,一般页中存的数据是项目数据,而目录页中存的数据是一般页的地址。

假定咱们要查找id=19的数据,那么依照曾经的查找方法,咱们需求从第一页开端查找,发现不存在那么再到第二页查找,一向找到第四页才干找到id=19的数据,可是假如有了目录页,就能够运用id=19与目录页中寄存的数据进行比较,发现19大于任何一条数据,所以进入id=16指向的页进行查找,直接然后再经过页内的页目录行等级的数据的查找,很快就能够找到id为19的数据了。跟着数据越来越多,这种结构的功率相关于一般的多页方式,优势也就越来越显着。

B+树的特色我在《 [从入门到入土]令人掉发的数据库底层规划 》现已有具体叙说过了,在这儿就不重复叙说了,假如有不了解的同学能够去看这篇博客。

咱们接着往下聊,咱们将咱们画的存在目录页的多页方式图微观化,能够构成下面的这张图:

这便是咱们兜兜转转由简到繁构成的一颗B+树。和惯例B+树有少许不同,这是一棵MySQL意义上的B+树,MySQL的一种索引结构,其间的每个节点就能够了解为是一个页,而叶子节点也便是数据页,除了叶子节点以外的节点便是目录页。

这一点在图中也能够看出来,非叶子节点只寄存了索引,而只需叶子节点中寄存了实在的数据,这也是契合B+树的特色的。

因为叶子节点上寄存了一切的数据,而且有指针相连,每个叶子节点在逻辑上是相连的,所以关于规模查找比较友爱。

B+树的一切数据都在叶子节点上,所以B+树的查询功率安稳,一般都是查询3次。

B+树有利于数据库的扫描。

B+树有利于磁盘的IO,因为他的层高底子不会因为数据扩展而增高记载比该页中任何主键值都要小的值,Supremum 记载比该页中任何主键值都要大的值,这个伪记载别离构成了页中记载的鸿沟。

User Records 中寄存的是实践的数据行记载,具体的行记载结构将在本文的第二节中具体介绍。Free Space 中寄存的是闲暇空间,被删去的行记载会被记载成闲暇空间。Page Directory 记载着与二叉查找相关的信息。File Trailer 存储用于检测数据完整性的校验和等数据。

看到这儿,咱们现已了解了MySQL从单条数据开端,到经过页来削减磁盘IO次数,而且在页中完结了页目录来优化页中的查询功率,然后运用多页方式来存储很多的数据,终究运用目录页来完结多页方式的查询功率并构成咱们口中的索引结构——B+树。已然提到这儿了,那咱们就来聊聊MySQL的其他知识点。

关于聚簇索引和非聚簇索引在 [从入门到入土]令人掉发的数据库底层规划 这篇文章中现已有了具体的介绍,这儿简略地说说,所谓聚簇索引,便是将索引和数据放到一同,找到索引也就找到了数据,咱们方才看到的B+树索引便是一种聚簇索引,而非聚簇索引便是将数据和索引分隔,查找时需求先查找到索引,然后经过索引回表找到相应的数据。InnoDB有且只需一个聚簇索引,而MyISAM中都对错聚簇索引。

在MySQL数据库中不只能够对某一列树立索引,还能够对多列树立一个联合索引,而联合索引存在一个最左前缀匹配准则的概念,假如依据B+树来了解这个最左前缀匹配准则,相对来说就会简略很许多了。

首要咱们依据文首的这张表树立一个联合索引:

create index idx_obj on user

咱们现已了解了索引的数据结构是一颗B+树,也了解了B+树优化查询功率的其间一个要素便是对数据进行了排序,那么咱们在创立idx_obj这个索引的时分,也就相当于创立了一颗B+树索引,而这个索引便是 依据联合索引的成员来进行排序 ,这儿是age,height,weight。

看过我之前那篇博客的同学知道,InnoDB中只需有主键被界说,那么主键列被作为一个聚簇索引,而其它索引都将被作为非聚簇索引,所以自然而然的,这个索引就会是一个非聚簇索引。

所以依据这些咱们能够得出定论:

idx_obj这个索引会依据age,height,weight进行排序

idx_obj这个索引是一个非聚簇索引,查询时需求回表

依据这两个定论,首要需求了解的便是,怎样排序?

单列排序很简略,比巨细嘛,谁都会,可是 多列排序是依据什么准则的呢?

实践上在MySQL中,联合索引的排序有这么一个准则,从左往右顺次比较巨细,就拿方才树立的索引举比方,他会先去比较age的巨细,假如age的巨细相同,那么比较height的巨细,假如height也无法比较巨细, 那么就比较weight的巨细,终究对这个索引进行排序。

那么依据这个排序咱们也能够画出一个B+树,这儿就不像上文画的那么具体了,简化一下:

数据:

B+树:

留意:此刻因为对错聚簇索引,所以叶子节点不在有数据,而是存了一个主键索引,终究会经过主键索引来回表查询数据。

B+树的结构有了,就能够经过这个来了解最左前缀匹配准则了。

咱们先写一个查询句子

SELECT * FROM user WHERE age=1 and height = 2 and weight = 7

毋庸置疑,这条句子必定会走idx_obj这个索引。

那么咱们再看一个句子:

SELECT * FROM user WHERE height=2 and weight = 7

答案是否定的,那么咱们剖析的方向便是,为什么这条句子不会走索引。

上文中咱们提到了一个多列的排序准则,是从左到右进行比较然后排序的,而咱们的idx_obj这个索引从左到右顺次是age,height,weight,所以当咱们运用height和weight来作为查询条件时,因为age的缺失,那么就无法从age来进行比较了。

看到这儿或许有小伙伴会有疑问,那 假如直接用height和weight来进行比较不能够吗? 显然是不能够的,能够举个比方, 咱们把缺失的这一列写作一个问号,那么这条句子的查询条件就变成了?27,那么咱们从这课B+树的根节点开端,根节点上有127和365,那么以height和weight来进行比较的话,走的必定是127这一边,可是假如缺失的列数字是大于3的呢? 比方427,527,627,那么假如走索引来查询数据,将会丢掉数据,过错查询。 所以这种状况下是肯定不会走索引进行查询的。 这便是最左前缀匹配准则的成因。

最左前缀匹配准则,MySQL会一向向右匹配直到遇到规模查询就中止匹配,比方 a=3 and b=4 and c 5 and d=6,假如树立次序的索引,d是无法运用索引的,假如树立的索引则都能够运用到,a、b、d的次序能够恣意调整。

=和in能够乱序,比方 a=1 and b=2 and c=3 树立索引能够恣意次序,MySQL的查询优化器会帮你优化成索引能够辨认的方式。

依据咱们了解的能够得出定论:

能够再看几个句子:

SELECT * FROM user WHERE age=1 and height = 2

这条句子是能够走idx_obj索引的,因为它能够经过比较 。

SELECT * FROM user WHERE age=1 and weight=7

这条句子也是能够走ind_obj索引的,因为它也能够经过比较,走左子树,可是实践上weight并没有用到索引,因为依据最左匹配准则,假如有两页的age都等于1,那么会去比较height,可是height在这儿并不作为查询条件,所以MySQL会将这两页全都加载到内存中进行终究的weight字段的比较,进行扫描查询。

SELECT * FROM user where age 1

这条句子不会走索引,可是能够走索引。这句话是什么意思呢?这条SQL很特别,因为其存在能够比较的索引,所以它走索引也能够查询出成果,可是因为这种状况是规模查询而且是全字段查询,假如走索引,还需求进行回表,MySQL查询优化器就会以为走索引的功率比全表扫描还要低,所以MySQL会去优化它,让他直接进行全表扫描。

SELECT * FROM user WEHRE age=1 and height 2 and weight=7

这条句子是能够走索引的,因为它能够经过age进行比较,可是weight不会用到索引,因为height是规模查找,与第二条句子相似,假如有两页的height都大于2,那么MySQL会将两页的数据都加载进内存,然后再来经过weight匹配正确的数据。

因为聚簇索引是将索引和数据都寄存在叶子节点中,假如一切的索引都用聚簇索引,则每一个索引都将保存一份数据,会形成数据的冗余,在数据量很大的状况下,这种数据冗余是很耗费资源的。

这两个点也是前次写关于索引的博客时漏下的,这儿补上。

科普时刻:查询优化器 一条SQL句子的查询,能够有不同的履行计划,至于终究挑选哪种计划,需求经过优化器进行挑选,挑选履行本钱最低的计划。

在一条单表查询句子实在履行之前,MySQL的查询优化器会找出履行该句子一切或许运用的计划,比照之后找出本钱最低的计划。这个本钱最低的计划便是所谓的履行计划。

优化进程大致如下:

1、依据查找条件,找出一切或许运用的索引

2、核算全表扫描的价值

3、核算运用不同索引履行查询的价值

4、比照各种履行计划的价值,找出本钱最低的那一个 。

参阅:https://juejin.im/post/5d23ef4ce51d45572c0600bc

依据咱们方才的那张表的非聚簇索引,这条句子便是因为查询优化器的效果,形成没有走索引:

SELECT * FROM user where age 1

科普时刻:掩盖索引 掩盖索引指一个查询句子的履行只用从索引中就能够获得,不必从数据表中读取。也能够称之为完结了索引掩盖。

当一条查询句子契合掩盖索引条件时,MySQL只需求经过索引就能够回来查询所需求的数据,这样防止了查到索引后再回来表操作,削减I/O进步功率。

如,表 covering_index_sample 中有一个一般索引  idx_key1_key2 。当咱们经过SQL句子: select key2 from covering_index_sample where key1 = 'keytest'; 的时分,就能够经过掩盖索引查询,无需回表。

参阅:https://juejin.im/post/5d23ef4ce51d45572c0600bc

例如:

SELECT age FROM user where age = 1

这句话就不需求进行回表查询。

本篇文章侧重聊了一下关于MySQL的索引结构,从零开端渐渐构建了一个B+树索引,而且依据这个进程谈了B+树是怎样一步一步去优化查询功率的。

简略地概括一下便是:

排序:优化查询的底子,刺进时进行排序实践上便是为了优化查询的功率。

页:用于削减IO次数,还能够使用程序局部性原理,来略微进步查询功率。

页目录:用于躲避链表的软肋,防止在查询时进行链表的扫描。

多页:数据量添加的状况下拓荒新页来保存数据。

目录页:“特别的页目录”,其间保存的数据是页的地址。查询时能够经过目录页快速定位到页,防止多页的扫描。

欢迎拜访博客:http://blog.objectspace.cn/

热门文章

随机推荐

推荐文章