(六)MySQL索引原理篇:深入数据库底层揭开索引机制的神秘面纱!

语言: CN / TW / HK

theme: channing-cyan

引言

本文为掘金社区首发签约文章,14天内禁止转载,14天后未获授权禁止转载,侵权必究!

   本篇也是MySQL索引机制的终章,在经过《索引初识篇》《索引应用篇》两篇后,已经对索引有了很高的掌握度了,但MySQL的索引机制,自始至终对于我们都是一个黑盒般的存在,我们并不清楚建立索引后MySQL会发生什么,也并不清楚使用索引查询时会如何检索......。甚至在前两篇文章中,对于索引咱们也留下了很多很多的疑惑:
中上两篇留下的疑惑
那么!《索引原理篇》它现在终于来了!但对于索引原理及底层实现,相信大家多多少少都有了解过,毕竟这也是面试过程中出现次数较为频繁的一个技术点。在本文中就来一窥MySQL索引底层的神秘面纱!

一、MySQL索引为何使用B+树结构?

   MySQL的索引机制中,有一点可谓是路人皆知,既默认使用B+Tree作为底层的数据结构,但为什么要选择B+树呢?有人会说树结构是以二分法查找数据,所以会在很大程度上提升检索性能,这点确实没错,但树结构有那么多,MySQL为什么不选二叉树、AVL树、红黑树或B树呢?下面一起先聊一聊这个话题。

对于索引为什么不支持数组、链表、队列等结构就不做过多解释了,因为这些结构中的元素都是按序并排存储,如果选择这些结构来实现索引,那走索引依旧等价于走全表,并未带来查询时的效率提升,反而带来了额外的存储开销,这是没有意义的。

1.1、普通SQL的全表扫描过程

   想要真正理解MySQL为何选B+树结构之前,你必须要先了解一条普通SQL的全表扫描过程,否则你很难真正切身感受出有索引和没索引的区别。当然,这里就不再以伪逻辑的形式讲解全表扫描了,而是真正的为大家讲解MySQL全表扫描的实际过程。以下面这张用户表为例:
表数据
首先假设表中不存在任何索引,此时来执行下述这条SQLsql SELECT * FROM `zz_user` WHERE `name` = "黑熊"; 因为表中不具备索引,所以这里会走全表扫描的形式检索数据,但不管是走全表亦或索引,本质上由于数据都存储在磁盘中,因此首先都会触发磁盘IO,所以先来说说磁盘寻道的过程:
磁盘寻道
如果磁盘不是SSD类型,大致长上面这个样子,里面有一个个的盘面和磁针,当发生磁盘IO时,首先会根据给出的磁盘地址,在盘面上寻道。这个寻道过程是怎么回事呢?就跟小时候VCD、DVD放光碟类似,盘面会开始转圈圈,在盘面上有一个磁道的概念,当转到了对应的地址时,磁道和磁针会相互吸引,然后以一上一下的方式读取0、1二进制数据,最终从磁盘中将目标地址中的数据读取出来。

磁盘寻道的大致过程如上,具体的细节没写出来,重点是大家要感受这个过程即可。

当走全表扫描时,会发生磁盘IO,但是磁盘寻道是需要有一个地址的,这个地址最开始就是本地表数据文件中的起始地址,也就是从表中的第一行数据开始读,读到数据后会载入内存,然后MySQL-Server会根据SQL条件对读到的数据做判断,如果不符合条件则继续发生磁盘IO读取其他数据(如果表比较大,这里不会以顺序IO的形式走全表检索,而是会触发随机的磁盘IO)。

那来看一下,上面给出的用户表中,「黑熊」这条数据位于表的第五行,那这里会发生五次磁盘IO吗?答案是NO,为什么呢?因为OS、MySQL中都有一个优化措施,叫做局部性读取原理。

1.1.1、局部性原理

局部性原理的思想比较简单,比如目前有三块内存页x、y、z是相连的,CPU此刻在操作x页中的数据,那按照计算机的特性,一般同一个数据都会放入到物理相连的内存地址上存储,也就是当前在操作x页的数据,那么对于y,z这两页内存的数据也很有可能在接下来的时间内被操作,因此对于y,z这两页数据则会提前将其载入到高速缓冲区(L1/L2/L3),这个过程叫做利用局部性原理“预读”数据。

但是一次性到底预读多大的数据放入到高速缓冲区中呢?

这个是由缓存行大小决定的,比如因特尔的MESI协议中,缓存行的默认大小为64k,也就是说在因特尔的CPU中,一次性会将“当前操作数据”附近的64K数据(16页数据)提前载入进高速缓冲区。

OK~,上述内容讲的是操作系统高速缓冲区的知识,在CPU中利用局部性原理,提前将数据从内存先放入L1/L2/L3三级缓冲区中,主要是为了减小CPU寄存器与内存之间的性能差异。

OK~,由于CPU寄存器和内存之间的性能差异太大,所以逐个读数据的形式会导致CPU工作期间的大量时间会处于等待数据状态,所以利用局部性原理将数据“预读”到高速区。而对于MySQL而言,亦是同理,存储数据的磁盘和内存之间的性能差异也是巨大的,因为MySQL也会利用局部性原理,提前“预读”数据。

这是什么意思呢?其实就是指MySQL一次磁盘IO不仅仅只会读取一条表数据,而是会读取多条数据,那到底读多少条数据呢?在InnoDB引擎中,一次默认会读取16KB数据到内存。

1.1.2、全表扫描过程

回到前面分析全表扫描的阶段,由于MySQL中会使用局部性原理的思想,所以对于给出的用户表数据而言,可能只需发生一次磁盘IO就能将前五条数据全部读到内存,然后会在内存中对本次读取的数据逐条判断,看一下每条数据的姓名字段是否为「黑熊」: - 如果发现不符合SQL条件的行数据,则会将当前这条数据放弃,同时在本次SQL执行过程中会排除掉这条数据,不会对其进行二次读取。 - 如果发现当前的数据符合SQL条件要求,则会将当前数据写入到结果集中,然后继续判断其他数据。

当本次磁盘IO读取到的所有数据全部筛选完成后,紧接着会看一下表中是否还有其他数据,如果还有则继续触发磁盘IO检索数据,如果没有则将内存中的结果集返回。

有人或许会疑惑,为什么这里已经读到了符合条件的数据,还需要继续发生磁盘IO呢?因为表中的字段没有建立唯一索引或唯一约束,因此MySQL不确定是否还有其他同名的数据,所以需要将整个表全部扫描一遍,才能得到最终结论。

好的,到这里就将MySQL全表扫描的过程讲明白了,紧着来看看全表扫描有什么问题呢?

其实按目前的情况来看,似乎不会有太大的问题,因此表中数据不多,一次磁盘IO几乎就能读完。但思考一下,如果当表的数据量变为百万级别、千万级别呢?假设表中一条数据大小为512Bit,一次磁盘IO也只能读32条,假设表中有320w条数据,一次全表就有可能会触发10W次磁盘IO,每次都需要在硬件上让那个盘面转啊转,其过程的开销可想而知.....

因此建立索引的原因就在于此处,为了避免查询时走全表扫描,因此全表扫描的开销会随着数据量增长而越来越大。

1.2、索引为何不选择二叉树?

   数据结构与算法,这门学科从诞生到现在,自始至终都让人难以理解,但国外有一个比较厉害的程序员,为了帮助他人更好的理解数据结构,自己搭建了一个数据结构的动画演示平台,里面提供了非常多丰富的数据结构类型,我们在其中能以动画的形式观测数据结构的变化。

回归话题本身,全表扫描由于走的是线性查询,因此数据越多,开销越大,此时先来看看二叉搜索树。

Binary Search Tree二叉搜索树是遵守二分搜索法实现的一种数据结构,咱们先来看看这种数据结构为何不适合用来做索引结构呢?
二叉搜索树
上图是我提前构建的二叉树,其中存在6个节点,按咱们前面给出的案例,「黑熊」这条数据位于表的第五行,那假设以二叉树作为索引结构,想要定位到第五行数据,需要经过几次磁盘IO呢?来看动图演示效果:
二叉树查找动画
从动画中可以明显看到,想要查到第五条数据,需要经过五次查询,由于树结构在磁盘中存储的位置也不连续,因此无法利用局部性原理读取后续的节点,所以最终需要发生五次磁盘IO才能读取到数据。 - 二叉树不适合作为索引结构的原因: - ①如果索引的字段值是按顺序增长的,二叉树会转变为链表结构。 - ②由于结构转变成了链表结构,因此检索的过程和全表扫描无异。 - ③由于树结构在磁盘中,各节点的数据并不连续,因此无法利用局部性原理。

1.3、索引为何不选择红黑树?

   上面简单的分析二叉树后,很明显的可以看出,二叉树并不适合作为索引结构,那接下来再看看大名鼎鼎的Red-Black Tree红黑树:
红黑树
同样提前先构建好了六个节点,相较于之前的二叉树,红黑树则进一步做了优化,它是一种自适应的平衡树,会根据插入的节点数量以及节点信息,自动调整树结构来维持平衡,从树的高度上来看,明显比之前的6层减少到了4层,那此时再来看看检索的过程:
红黑树查找动画
由于树变矮了,其效果也很明显,在红黑树中只需要经过三次查找,就能定位到第五个节点,似乎看起来还不错对嘛?但MySQL为啥不用这颗名声远扬的红黑树呢? - 红黑树不适合作为索引结构的原因: - ①虽然对比二叉树来说,树高有所降低,但数据量一大时,依旧会有很大的高度。 - ②每个节点中只存储一个数据,节点之间还是不连续的,依旧无法利用局部性原理。

对于上述两个缺点罗列的很明白,其本质上的原因就在于:单个节点中只能存储一个数据,因此一方面树会随着数据量增长越来越高,第二方面也无法利用局部性原理减少磁盘IO

那是不是把红黑树稍微改造一下,让其单个节点中可存储多个数据是不是可以了呢?B树就是这样干的,一起来看看。

1.4、索引为何不选择B-Tree?

   在前面提到过,将红黑树稍微改造一下,让其单节点可容纳多个数据,就能在很大程度上改善其性能,事实上B-Tree就是这么做的,B树可以理解成红黑树的一个变种,如下:
B树
此时给B树结构也添加了6个节点,此时观测上述结构,一方面树仅有2层,同时一个节点中也存储了多个数据,再来看看B树的查找过程:
B树查找动画
哦吼吼吼~,完美完美,两次就查到了数据,同时一个节点中还能存储多个数据,可充分利用局部性原理,让一次磁盘IO读取多个数据!!但有人可能会问,上面的一个节点也只存两个数据啊,没太大的区别似乎。但你要这么想就错了,B树中一个节点可容纳的数据个数,可以自己控制的,例如:
B树更改节点容量
在这里将Max.Degree更改后,B树单节点的容量也会随之更改,从上图中可清晰看到一个节点同时将6个数据全存储进去了,这也就代表着只需要一次磁盘IO就能检索出5这个数据,是不是很完美?先别急着下定律,毕竟咱们目前是站在索引设计者的角度来看待问题的,此时虽然看起来很美好了,但想一个问题:

MySQL由于是关系型数据库,因此经常会碰到范围查询的需求,举例:
SELECT * FROM zz_user WHERE ID BETWEEN 2 AND 5;

比如上述这条SQL语句,需要查询表中ID2~5的所有数据,那也就代表着需要查四条数据,在这里因为2~5在同一个节点中,因此仅触发一次IO就可拿到数据,但实际业务中往往不会有这么小的范围查询,假设此时是查ID=2~1000之间的数据呢?这么多数据定然不会在一个节点中,因此这里又会触发多次磁盘IO! - B树不适合作为索引结构的原因: - 虽然对比之前的红黑树更矮,检索数据更快,也能够充分利用局部性原理减少IO次数,但对于大范围查询的需求,依旧需要通过多次磁盘IO来检索数据。

1.5、索引为何要选择B+Tree?

   上面聊到的B-Tree相对来说已经较为完美了,但最后也谈到:它并不适合用于范围查询,但这种查询需求在关系型数据库中又很常见,那这里怎么优化呢?一起来看看B+Tree
B+树
相较于B树而言,B+树的结构又出现了新的变化,一方面节点分为了叶节点和叶子节点两类,这里先有这两个概念即可,后续介绍这两类节点在索引中的作用。B+树中除开节点分为两类外,还有一个最大的变化就是:最下面的一排节点之间,都存在一个单向指针,指向下一个节点所在的位置,这也是B+树对B树的最大改造点:

前面讲过,由于B树不适合于大范围查询操作,因此B+树中多了个指针,当需要做范围查询时,只需要定位第一个节点,然后就可以直接根据各节点之间的指针,获取到对应范围之内的所有节点,也就是只需要发生一次IO,就能够确定所查范围之内的所有数据位置。

OK~,到现在为止,B+树以接近完美的形式解决之前其他数据结构中的所有问题,因此B+Tree正式成为了MySQL默认的索引结构,因此对于MySQL索引为何要选择B+Tree的原因大家应该也懂了,MySQL的设计者在研发时,也绝对是对比了多种数据结构后,逐步推导其缺陷,然后采用更好的数据结构代替,从而最终推导出了B+Tree

OK~,接下来再说一下前面抛出的一个问题:叶节点和叶子节点在MySQL索引中的作用。

要弄明白这个问题,首先得搞清楚叶节点和叶子节点是什么?其实很简单:
B+树-叶节点
B+Tree上面这些节点则被称为叶节点,在MySQL中不会存储数据,仅存储指向叶子节点的指针,这样做的好处在于能够让一个叶节点中存储更多的元素,从而确保树的高度不会由于数据增长而变得很高。
B+树-叶子节点
同时,B+Tree最下面这排节点则被称为叶子节点,这些节点中会存储实际的数据,例如聚簇索引中就直接存储对应的行数据,非聚簇索引中则存储指向主键/聚簇索引的字段值。同时每个叶子节点之间都有一根单向指针指向下一个节点,从而使得最下面的一排叶子节点之间又形成了一个单向链表结构,方便范围取值。

1.5.1、B+Tree结构为何会存在叶节点呢?

其实在之前的数据结构中,从来没有叶节点的这个概念出现,每个节点信息在整棵树结构中只会存储一份,但为什么B+树中会用叶节点,同时冗余一份节点信息呢?因为你从前面的B+Tree结构中,也能明显观测到2、3、4、5节点都会出现了两次。在这里如果想要搞明白为什么要冗余节点,你得想明白一个问题:

能不能将所有的索引数据、表数据全部放入到一个节点中存储呢?这样树的高度永远为1呀,是不是只需要经过一次磁盘IO啊?

其实乍一听似乎有道理,实则是行不通的,因为一次磁盘IO读取的数据量是有限制的,如果将所有的数据全放入到一个节点中存储,那一次磁盘IO只能读取节点的一部分数据,将整个节点读完,本质上就和之前走一次全表没区别了。

理解这个点之后,再来看看抛出的问题:B+Tree为何会有叶节点冗余数据呢?

因为B+Tree的每个节点大小会有限制,所以如果将数据存储在叶节点上,会导致单个树节点存的索引键很少。但如果树的叶节点不存实际的行数据,就代表单个节点可以存更多的索引键,单个节点存的越多也就代表着树的高度会越小,树的高度越小就等价于查询时会发生的磁盘IO次数越少,IO次数越少就相当于数据检索速度会更快,到这里相信大家应该能明白为什么会有叶节点冗余索引键了。

但索引中除开索引键外,也必须要存数据,如果不存数据索引就失去了意义,因此B+tree最下面一排的叶子节点,其中就会存储对应的索引键与行数据/聚簇索引字段值。

一句话来概述,B+Tree的叶节点仅是作为一个“过渡者”的角色,主要是为了提升索引效率的,实际的数据会保存在最下面的叶子节点中,叶节点中仅有一个指针指向罢了。

1.5.2、千万级别的表B+Tree会有多高?

搞清楚B+Tree的一些疑惑后,此时来倒推一个问题,MySQL中一张千万级别的数据表,如果基于自增ID的主键字段建立B+树索引,那此时树会有多高呢?有人或许会认为,虽然B+Tree结构很优异,但千万级别的表至少有1000W条数据,再怎么样应该也有几十、几百的树高吧?但实际上答案会让你大吃一惊。

想要科学的弄懂这个问题,那必须建立在实际的依据上来计算,想要计算出树高,首先得有三个值:
①索引字段值的大小。
MySQLB+Tree单个节点的大小。
MySQL中单个指针的大小。

如何计算索引字段值的大小呢?

这点要依据字段所使用的数据类型来决定。假设此时表的自增ID,创建表时使用的int类型,int类型在计算机中占4Bytes,那此时基于ID字段建立主键索引时,B+Tree每个节点的索引键大小就为4Bytes

如何得知MySQL中B+树单个节点的大小呢?

对于索引单个节点的容量是多少呢?在MySQL中默认使用引擎的一页大小作为单节点的容量,假设此时表的存储引擎为InnoDB,就可以通过下述这条命令查询:
sql SHOW GLOBAL STATUS LIKE "Innodb_page_size"; +------------------+-------+ | Variable_name | Value | +------------------+-------+ | Innodb_page_size | 16384 | +------------------+-------+ 从上述查询结果来看,InnoDB引擎的一页大小为16384Bytes,也就是16KB,此时也就代表着B+Tree的每个节点容量为16KB

MySQL中的指针是多大呢?

一般来说,操作系统的指针为了方便寻址,一般都与当前的操作系统位数对应,例如32位的系统,指针就是32bit/4Bytes64位的操作系统指针则为64bit/8Bytes,但由于64bit的指针寻址范围太大,目前的计算机根本用不上这么大的寻址范围,因此在MySQL-InnoDB引擎的源码中,单个指针被缩小到6Bytes大小。

千万级别的索引树高计算

从上述三条可得知:单个索引节点容量为16KB,主键字段值为4B,指针大小为6B,一个完整的索引信息是由主键字段值+指针组成的,也就是4+6=10B,那此时先来计算一下单个节点中可存储多少个索引信息呢?

16KB / 10B ≈ 1638个。

那此时来计算一下,对于一颗高度为2B+树,根节点可存储1638个叶子节点指针,也就代表着B+Tree的第二层有1638个叶子节点,因为叶子节点要存储实际的行数据,假设表中每行数据为1KB,这也就是代表着一个叶子节点中可存储16条行数据,那么一颗高度为2B+树可存储的索引信息为:1638 * 16 = 26208条数据。

再来算算树高为3B+树可以存多少呢?因为最下面一排才是叶子节点,此时树高为3,也就代表着中间一排是叶节点,只存储指针并不存储数据,而每个节点可容纳1638个索引键+指针信息,因此计算过程是:1638 * 1638 * 16 = 42928704条。

是不是很令你惊讶?树高为3B+Tree,竟然可以存储四千多万条数据,也就代表着千万级别的表,走索引查询的情况下,大致只需要发生三次磁盘IO即可获取数据。

当然,上述的这个数据是基于主键为int类型、表的一行数据为1KB来计算的,实际情况中会不一样,因为主键有可能是bigint类型或其他类型,而一行数据也可能不仅仅只有1KB。因此对于一张实际的千万级别表,它的主键索引实际树高有多少,你结合主键的数据类型以及一行数据的大小,也可以计算出来,它同时不会太高。
对实际的千万表索引树高感兴趣的,我提供一个计算公式:索引键大小=索引字段类型所占的空间、一行表数据大小=所有表字段的类型+隐藏字段(20Bytes)所占大小总和,得到这两个值之后,再套入前面的例子中既可得知。

看到这里,对于索引凭啥那么快?为啥能够提升查询性能?相信大家也有了答案,毕竟索引树高才是个位数,发生的磁盘IO次数也那么少,检索数据的速度不快才来了个鬼~

不过B+Tree中的每个索引页中,还会存储页头(页号、指针、伪记录等)、页目录、页尾等信息,大概一共占用128KB左右,因此想要真正的计算出来接近实际情况的索引树高,还需要把这点考虑在内~

1.5.3、MySQL索引底层的真正结构

以为B+Tree就是索引的终点了嘛?实则不然,MySQL的追求可不止于此,虽然B+Tree已经特别特别优秀了,但B+Tree的叶子节点之间是单向指针组成的链表结构,这对于倒排序查询时,显然并不友好,因为只有单向指针,那么只能先正序获取数据后再倒排一次,因此MySQL真正的索引结构还对B+Tree做了变种设计!

啥意思呢?也就是MySQL在设计索引结构时,对于原始的B+Tree又一次做了改造,叶子节点之间除开一根单向的指针之外,又多新增了一根指针,指向前面一个叶子节点,也就是MySQL索引底层的结构,实际是B+Tree的变种,叶子节点之间是互存指针的,所有叶子节点是一个双向链表结构。

这样做的好处在于:即可以快速按正序进行范围查询,而可以快速按倒序进行范围操作,在某些业务场景下又能进一步提升整体性能!

1.5.4、前缀索引为何能提升索引性能?

这个问题是在之前的《索引初识篇》中抛出的问题,到这里答案也就呼之欲出了,因为前缀索引可以选用一个字段的前N个字符来创建索引,相较于使用完整字段值做为索引键,前缀索引的索引键,显然占用的空间更少,一个索引键越小,代表一个B+Tree节点中可以存储更多的索引键,等价于树高会越小,也就代表磁盘IO更少,检索数据时自然效率更高。

二、建立索引时那些不为人知的内幕

   弄明白了索引的底层数据结构后,再一起来聊一聊创建索引后会发生什么事情呢?一般我们都会以下述方式创建索引:
sql -- ①通过CREATE语句创建 CREATE INDEX indexName ON tableName (columnName(length) [ASC|DESC]); -- ②通过ALTER语句创建 ALTER TABLE tableName ADD INDEX indexName(columnName(length) [ASC|DESC]); -- ③建表时通过DML语句创建 CREATE TABLE tableName( columnName1 INT(8) NOT NULL, columnName2 ...., ....., INDEX [indexName] (columnName(length)) ); 在咱们通过SQL命令创建索引时,MySQL首先会判断一下当前表的存储引擎,因为在《索引初识篇》中提到过,索引机制本身是由存储引擎层提供实现的,不同的引擎实现的索引也不同,因此创建索引时第一步就会先判断存储引擎,然后根据不同的存储引擎创建索引,这里重点聊一下常用的MyISAM、InnoDB

2.1、常用存储引擎的数据存储

首先为了能够实际观察到两个引擎之间的区别,分别使用MyISAM、InnoDB两个引擎创建两张表: ``sql -- 创建一张使用MyISAM引擎的表:zz_myisam_index CREATE TABLEzz_myisam_index(z_m_idint(8) NOT NULL,z_m_name` varchar(255) NULL DEFAULT '' ) ENGINE = MyISAM CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact;

-- 创建一张使用InnoDB引擎的表:zz_innodb_index CREATE TABLE zz_innodb_index ( z_i_id int(8) NOT NULL, z_i_name varchar(255) NULL DEFAULT '' ) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Compact; `` 上述过程中创建了两张表:zz_myisam_index、zz_innodb_index,分别使用了不同的引擎,而MySQL中对于所有的数据都会放入到磁盘中存储,因此先来找一下这两张表的本地位置,默认位于C:\ProgramData\MySQL\MySQL Server 5.x\data`这个目录中,在这里保存着所有已创建的数据库磁盘文件,首先从这里面找到对应的数据库并进入目录,如下:
磁盘文件
对于这几个文件相信大家一定不陌生,毕竟在《MySQL架构篇-文件系统层》中曾介绍过,此时分别来看看使用不同引擎的两张表有何不同。

2.1.1、使用MyISAM引擎的表

zz_myisam_index这张表是使用MyISAM引擎的表,在磁盘中有三个文件: - zz_myisam_index.frm:该文件中存储表的结构信息。 - zz_myisam_index.MYD:该文件中存储表的行数据。 - zz_myisam_index.MYI:该文件中存储表的索引数据。

也就是说,MyISAM引擎的表数据和索引数据,是分别放在两个不同的磁盘文件中存储的,这也意味着MyISAM引擎并不支持聚簇索引,因为聚簇索引要求表数据和索引数据一起存储在同一块空间,而MyISAM.MYI索引文件中,存储的是表数据所在的地址指针。

2.1.2、使用InnoDB引擎的表

zz_innodb_index这张表是使用InnoDB引擎的表,在磁盘中仅有两个文件: - zz_innodb_index.frm:该文件中存储表的结构信息。 - zz_innodb_index.ibd:该文件中存储表的行数据和索引数据。

因为InnoDB引擎中,表数据和索引数据都一起放在.ibd文件中,也就代表着索引数据和表数据是处于同一块空间存储的,这符合聚簇索引的定义,因此InnoDB支持聚簇索引。

同时也正由于这个原因,所以如果使用InnoDB引擎的表未主动创建聚簇索引,它会自动选择表中的主键字段,作为聚簇索引的字段。但如果表中未声明主键字段,那则会选择一个非空唯一索引来作为聚簇索引。但如果表中依旧没有非空的唯一索引,InnoDB则会隐式定义一个主键来作为聚簇索引(这个列在上层是不可见的,是一个按序自增的值)。

OK~,搞明白两种常用引擎的底层存储区别后,接下来再聊聊手动创建索引后究竟会发生什么?

2.2、手动创建索引后发生的事情

当手动创建索引后,MySQL会先看一下当前表的存储引擎是谁,接着会判断一下表中是否存在数据,如果表中没有数据,则直接构建一些索引的信息,例如索引字段是谁、索引键占多少个字节、创建的是啥类型索引、索引的名字、索引归属哪张表、索引的数据结构.....,然后直接写入对应的磁盘文件中,比如MyISAM的表则写入到.MYI文件中,InnoDB引擎的表则写入到.ibd文件中。

上述这个过程,是表数据为空时,创建索引会干的工作,还算比较简单,但当表中有数据时,过程也一样吗?NO,会多出很多步骤。

当表中有数据时,首先MySQL-Server会先看一下目前要创建什么类型的索引,然后基于索引的类型对索引字段的值,进行相应的处理,比如: - 唯一索引:判断索引字段的每个值是否存在重复值,如果有则抛出错误码和信息。 - 主键索引:判断主键字段的每个值是否重复、是否有空值,有则抛出错误信息。 - 全文索引:判断索引字段的数据类型是否为文本,对索引字段的值进行分词处理。 - 前缀索引:对于索引字段的值进行截取工作,选用指定范围的值作为索引键。 - 联合索引:对于组成联合索引的多个列进行值拼接,组成多列索引键。 - ........

根据索引类型做了相应处理后,紧接着会再看一下当前索引的数据结构是什么?是B+Tree、Hash亦或是其他结构,然后根据数据结构对索引字段的值进行再次处理,如: - B+Tree:对索引字段的值进行排序,按照顺序组成B+树结构。 - Hash:对索引字段的值进行哈希计算,处理相应的哈希冲突,方便后续查找。 - .......

到这一步为止,已经根据索引结构,对索引字段的值处理好了,此时就会准备将内存中处理好的字段数据,写入到本地相应的磁盘文件中,但如果此时为InnoDB引擎,那在写入前还会做最后一个判断,也就是判断当前的索引是否为主键/聚簇索引: - 如果当前创建索引的字段是主键字段,则在写入时重构.ibd文件中的数据,将索引键和行数据调整到一块区域中存储。

当然,如果这里创建的不是主键/聚簇索引,或者目前是MyISAM引擎,则意味着现在需要创建的是非聚簇索引,因此会先会为每个索引键(索引字段值)寻找相应的行数据,找到之后与索引键关联起来,不过InnoDB、MyISAM引擎两者之间的非聚簇索引也会存在些许差异,所以在这里也会有一点点不同:
- InnoDB:因为有聚簇索引存在,所以非聚簇索引在与行数据建立关联时,存放的是主键/聚簇索引的字段值。 - MyISAM:由于表数据在单独的.MYD文件中,因此可以直接以指针的形式关联起来。

也就是说,InnoDB引擎中的非聚簇索引,都是主键/聚簇索引的“附庸”,因此每个索引信息中是以「索引键:聚簇字段值」这种形式关联的。

MyISAM引擎中由于表数据和索引数据都是分开存储的,所以MyISAM的每个非聚簇索引都是独立的,因此每个索引信息则是以「索引键:行数据的地址指针」这种形式关联。

由于MyISAM引擎的非聚簇索引,关联的是行数据的指针,而InnoDB引擎关联的是聚簇索引的索引键,所以InnoDB的非聚簇索引在查询时需要回表,再查一次聚簇索引才能得到数据。而MyISAM每个非聚簇索引都能直接获取到行数据的地址,可以直接根据指针获取数据,从整体而言,MyISAM检索数据的效率会比InnoDB快上不少。

到这里,索引键和行数据关联好之后,就会开始根据引擎的不同,将内存中的索引信息分别写入到不同的磁盘文件中。写完完成后,B+Tree的根节点会放到内存中维护,以便于后续索引查询时再次从磁盘读取根节点信息。

到这里为止,大家也应该明白了为什么创建表之后,立马建索引会很快,但当表中有不少数据时创建索引会很慢的原因,就是因为表中有数据时,创建索引要做一系列判断、处理工作。

OK~,最后再放上一个聚簇索引和非聚簇索引的结构区别:
聚簇索引与非聚簇索引
在上图中给出了一张用户表,然后基于ID字段建立主键/聚簇索引,基于name字段建立普通/非聚簇索引,最终索引结构如图中所示。 - 在InnoDB聚簇索引的示意图中,由于不方便画出每行数据,就用row_data代替行数据。 - 在InnoDB非聚簇索引中,每个索引信息中存储聚簇索引的ID值。 - MyISAM非聚簇索引中,每个索引信息中则直接存储行数据的指针。

当然,这里也是画出的伪结构,因为不可能按照MySQL单节点16KB的尺寸1:1还原,毕竟画不下这么大(实际MySQL对于上述这些数据,一个节点就全放下了)。

索引键的大小会随着值长度变化吗?

这个问题很有趣,比如现在基于一个int类型的字段建立了一个索引,但目前的字段值是1,按理来说这个值只占1bits对不对?那在索引键中,或数据库中占多少呢?答案是4Bytes/32bits,这是因为一个int类型在操作系统中就会占用32bit空间,不会根据实际值而减少占用空间。

但大家也都知道,数据库中还有不少文本类型,例如varchar类型,它是固定的长度吗?并不是,它是一个变长类型,而非一个定长类型,也就是一个varchar字段值,占用的空间会随着实际所存储的数据而变化。

所以对于一个索引键的大小是否会发生变化,这要取决于你是基于什么字段类型建立的索引,如果是定长类型就不会变化,但如果是变长类型就会随之发生改变。

三、索引内部查询与维护的过程

   建立索引时会发生的内部过程,上一段落已经阐述明白了,接着再来说说查询SQL执行时,如果选中了索引,索引内部的检索过程是什么样的呢?也包括当写类型的SQL更改表中数据后,MySQL又会如何维护索引的内部结构呢?

当然,在此之前,如若对于SQL执行前会发生的工作还不了解的,可参考《SQL执行篇》

3.1、聚簇索引查找数据的过程

在《SQL执行篇》中聊到过,当查询SQL来到MySQL后,经过一系列处理后,最终会来到优化器,此时会由优化器来为SQL语句选择出一个合适的索引,当然,你也可以手动强制指定索引。那当SQL命中索引时,索引内部是如何查找对应的行数据的?

工作线程执行查询SQL时,首先会先看一下当前索引的结构,如果是Hash索引就很简单了,直接对索引字段的值进行哈希计算,然后直接根据哈希值,从索引中找到相应的索引信息,最后获取数据即可。

但如果索引结构是默认的B+Tree呢?内部又会发生什么工作?

如果当前SQL使用的是主键/聚簇索引,比如: sql SELECT * FROM `zz_user` WHERE `ID` = 12; 此时首先会根据条件字段,去内存中找到聚簇索引的根节点,然后根据节点中记录的地址去找次级的叶节点,最后再根据叶节点中的指针地址,找到最下面的叶子节点,从而获取其中的行数据,动画过程如下:
B+树查找动画

B+Tree结构的索引似乎查找过程也并不复杂对不对?但有一个细节点需要注意,B+Tree的单个节点可存储多个数据,也就是当磁盘IO发生后,MySQL一次读取的数据中有多个索引信息,此时MySQL会如果查找单个节点中的索引信息呢?全部判断一次嘛?

其实并不会全部判断一次,因为B+Tree是一种有序的数据结构,小的会放左边,大的会放右边,单个节点中的索引信息,同样遵循这个原理。既然单个节点中的数据也是有序的,所以MySQL同样会采用二分查找法去检索数据。对于单个节点中的索引信息,先从索引中间开始查询,然后判断一下当前SQLID=12这个条件,是大于还是小于最中间的索引键,小于则去节点左边取中间的索引键继续判断,大于则去右边.....,以此类推直至定位到单节点中对应索引键为止。

OK,如果是范围取值,比如取ID>=2的所有数据,则会先定位到ID=2的索引键,然后通过叶子节点之后的指针,直接将2之后的数据全部取出。

聚簇索引中,定位到了索引键,即代表着取到了数据,毕竟索引和行数据是一起存储的。

3.2、非聚簇索引查找数据的过程

相较于聚簇索引而言,非聚簇索引前面的步骤都是相同的,仅是最后一步有些许不同罢了,非聚簇索引经过一系列查询步骤后,最终会取到一个聚簇索引的字段值,然后再做一次回表查询,也就是再去聚簇索引中查一次才能取到数据。

如果是MyISAM引擎,则直接根据索引树中记录的指针地址,直接触发磁盘IO再次读取数据即可。

3.3、写SQL执行时索引的维护过程

前面分析了查询SQL执行时,索引查找数据的过程,那当出现增、删、改SQL时呢?索引会怎么维护呢?其实这里也要分索引类型,如果是Hash结构的索引,直接增删改对应的索引键即可,但B+Tree结构的索引,因为要内部节点是有序的,所以需要维护有序性。

也就是代表着,插入、更改、删除数据时,都会对B+Tree索引造成影响。

但先说清一个误区,表中不同的索引在本地有不同的索引记录,比如ID、Name字段分别建立了两个索引,那么就会有两颗不同的索引树写入到本地磁盘文件中。

3.3.1、插入数据时索引的变化

B+Tree索引是有序的,对于这点在前面已经反复提到了,但如果索引字段是数值类型,例如int、bigint、long等,本身就能区分大小顺序,此时可以直接做排序工作。但如果是基于字符串或其他类型的字段建立索引呢?又该如何排序呀?其实对于这个问题也并不难回答,大家还记得在建库建表时,干的一件事情嘛?
排序规则
在创建库表时,咱们通常都会指定一个排序规则,而这个规则就是MySQL对非数值类型字段的排序规则,比如字符串类型的字段,MySQL就会基于该规则对值先做计算处理,然后得到一个数值用于排序。

当然,具体排序处理的过程暂且不去纠结,重点只需搞清楚一点:数据库中任何字段都能排序即可。

OK~,那此时像数据库中插入一条数据时,还是以之前的用户表为例,比如: sql INSERT INTO `zz_user` VALUES(6,"上海市黄浦区xx街道666号","棕熊","男",30); 同样假设用户表上有两个索引,一是基于自增ID建立的主键索引,第二个则是基于姓名字段建立的普通索引。当表中插入这条数据后,索引又会发生什么变化呢?咱们分开聊聊。

主键/聚簇索引的变化

因为主键索引字段,也就是ID字段是顺序递增的,因此只需要在本地索引文件的B+Tree结构中,按照树结构找到最后的位置,将当前插入的ID:6作为索引键,以当前插入的行数据作为索引值,然后插入到最后的节点中即可。如下:
B+树插入ID动画

按序递增的索引维护,就是这么简单~

普通/非聚簇索引的变化

因为姓名字段本身的数据类型是字符串,与数值型字段天生的有序不同,字符串类型是无序的,因此首先需要根据已经配置好的排序规则,先对插入的name:棕熊这个值进行计算,然后根据计算出的值,决定当前数据在B+Tree中的索引位置,计算好之后再执行插入工作,过程如下:
B+树插入字符串
相较于主键字段的顺序ID,插入字符串类型的name值会复杂一些,因为从这里可以明显看到,插入的“棕熊”数据经过计算后,它并不排最后面,而是排中间,所以要将这个值插入到对应的位置,此时树的节点就会发生裂变,后续的所有叶子节点都需要往后移动,这个开销是较大的。

同时,在插入索引信息时,会以“棕熊”作为索引键,以ID:6作为索引值,然后一同插入,也就是要与行数据建立关联(MyISAM引擎则是行数据的地址指针)。

3.3.2、删除数据时索引的变化

sql DELETE FROM `zz_user` WHERE ID = 5; 例如上述这条删除语句,当执行后则会先根据ID在索引树中查找索引信息,然后先删除非聚簇索引上的索引信息,紧接着再去聚簇索引上删除主键索引信息和行数据。

过程大致是相同的,就不再制作动图演示其过程了,重点要记住的是:先删非聚簇索引信息,再删聚簇索引的信息,因为聚簇索引上存放着行数据,如果先把聚簇索引删了,就无法找到非聚簇索引上的信息了。

3.3.3、更改数据时索引的变化

sql UPDATE `zz_user` SET name = "狗熊" WHERE ID = 6; 对于上述这条修改语句,索引维护的过程相信大家自己也能推测出来,毕竟修改的本质就是先删再插入,首先在聚簇索引上查到ID=6这条数据,获取原本的name字段值:“棕熊”,然后以该值去非聚簇索引上找到对应的索引信息,然后将这个索引信息删除掉,紧接着再插入一个“狗熊”的索引信息。

当非聚簇索引更新完成后,紧接着会去更新聚簇索引,聚簇索引就不会删数据了,因为聚簇索引上保存着行数据。

首先会在聚簇索引上根据ID=6找到对应的行数据,然后将行数据中的name字段更新为“狗熊”。

至此,对于写SQL执行后,索引的维护过程就做了简单分析,实际上也并不难。

PS:实际索引更新数据时,具体的过程也会复杂一些,会牵扯到锁机制,也包括会判断修改的新值与原值的大小,如果大小相同则直接在原空间做修改(直接插入覆盖),如果不同才会先删再改。

3.4、主键为何推荐使用自增整数ID?

《索引应用篇-主键的陷阱》中,我曾推荐大家使用自增的整数ID作为主键,而并不是使用随机的UUID这类字符串等类型,这是为何呢?因为观察前面name索引字段的插入过程,能够很明显的观察到一个现象,字符串是无序的,当使用字符串作为主键字段时,在插入数据的时候会频繁破坏原有的树结构,造成树分裂以及后续节点的挪动,一两个条数据插入倒还没关系,但是每一条插入的数据都有可能导致树的结构调整一次,这个过程的开销可想而知.....

但是自增的整数ID就不会有这个问题,因为插入的ID本身就是按序递增的,因此插入的每一条新数据,都会直接放到B+Tree最后的节点中存储。

同时,除开上述原因外,还有一个原因就是UUID比整数自增ID长,UUID至少占位32字节,但int类型只占4字节,存储一个UUID的空间,可以存8个自增整数ID。也就代表着单个节点中,能存储的自增ID会比UUID多很多,单个节点存储的索引键越多.....(后面这一排就不讲了,前面复述过两次了,大家应该也懂哈~)

四、索引原理篇总结

   到目前而言,对于MySQL的索引底层实现,大多数内容就全面讲明白了,从最开始的全表扫描过程,到磁盘IO实现、局部性原理、索引为什么默认是B+Tree结构、建立索引后发生的一系列事情、写类型的SQL对索引的影响.....等一系列内容进行了深入剖析。

看完本章后,对于之前两章中抛出的一些疑惑,你稍加思考后也能彻底明悟,最后再简单说说聚簇索引和非聚簇索引的区别。

聚簇索引和非聚簇索引的根本区别: - 聚簇索引中,表数据和索引数据是按照相同顺序存储的,非聚簇索引则不是。 - 聚簇索引在一张表中是唯一的,只能有一个,非聚簇索引则可以存在多个。 - 聚簇索引在逻辑+物理上都是连续的,非聚簇索引则仅是逻辑上的连续。 - 聚簇索引中找到了索引键就找到了行数据,但非聚簇索引还需要做一次回表查询。

InnoDB-非聚簇索引与MyISAM-非聚簇索引的区别: - InnoDB中的非聚簇索引是以聚簇索引的索引键,与具体的行数据建立关联关系的。 - MyISAM中的非聚簇索引是以行数据的地址指针,与具体的行数据建立关联关系的。

一般来说,由于MyISAM引擎中的索引可以根据指针直接获取数据,不需要做二次回表查询,因此从整体查询效率来看,会比InnoDB要快上不少。

其实也不仅仅跟索引有关系,如果考虑的更加深入来说,其实跟锁的粒度以及事务也有关系,但对于具体的原因,在后续的《MySQL锁篇》、《MySQL事务篇》、《MySQL引擎篇》讲完后,大家自然就理解啦~

「其他文章」