Mysql原理篇之索引是如何一步步实现的---上--02

Mysql原理篇之索引是如何一步步实现的---上--02

• 前言
• 从一条记录说起
  • 如何管理多条记录---页
  • 记录的存储格式
    • COMPACT行格式
    • 行溢出
• 页是如何管理多条记录的
  • 如何快速定位页中某一条记录
  • Page Header
  • File Header
  • File Trailer
• 索引
  • 回顾
  • 如何进行数据查找
  • 如何快速定位某个页
    • 按照直观想法来实现一个简易索引
• 小结
• 参考

前言

Mysql索引的实现是在存储引擎层完成的，因此本文所讲内容是以Innodb存储引擎为基础展开的，核心是讲清楚Innodb的数据存储结构。

数据库是用来存储数据的，那么如何组织存储这些数据就是决定一个数据库好坏的重中之重了，对于关系型数据库而言，我们需要存储的数据往小了看是一条条的记录，往大了看就是一张表，一整个数据库。而一张表又是由成千上万的记录组织起来，因此，我们需要先解决一条记录该如何存储，该以什么格式进行存储，多条记录该如何编排管理…

因此，第一步我们就从一条记录开始说起。

从一条记录说起

如何管理多条记录—页

InnoDB是一个将表中的数据存储到磁盘上的存储引擎，所以即使关机后重启我们的数据还是存在的。而真正处理数据的过程是发生在内存中的，所以需要把磁盘中的数据加载到内存中，如果是处理写入或修改请求的话，还需要把内存中的内容刷新到磁盘上。而我们知道读写磁盘的速度非常慢，和内存读写差了几个数量级，所以当我们想从表中获取某些记录时，InnoDB存储引擎需要一条一条的把记录从磁盘上读出来么？

不，那样会慢死，InnoDB采取的方式是：将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，InnoDB中页的大小一般为 16 KB。也就是在一般情况下，一次最少从磁盘中读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘中。

记录的存储格式

我们平时是以记录为单位来向表中插入数据的，这些记录在磁盘上的存放方式也被称为行格式或者记录格式。设计InnoDB存储引擎的大叔们到现在为止设计了4种不同类型的行格式，分别是Compact、Redundant、Dynamic和Compressed行格式，随着时间的推移，他们可能会设计出更多的行格式，但是不管怎么变，在原理上大体都是相同的。

这里就不对行格式展开具体讨论了，就简单介绍一下Compact格式。

COMPACT行格式

大家从图中可以看出来，一条完整的记录其实可以被分为记录的额外信息和记录的真实数据两大部分。

• 变长字段长度列表主要负责记录字段类型为变长类型的实际数据长度，如: VARCHAR(10)，TEXT，BLOB等。
• NULL值列表记录当前行中哪些列的实际值为NULL，这样就可以避免在记录真实数据部分存储NULL值，并且NULL值列表实际是一串二进制位，表中每一列都对应一个二进制位，如果某一列的实际值为NULL，就将对应二进制位的值设置为1即可。
• 记录头信息是由固定的5个字节组成，这些二进制位代表的详细信息如下表：

这里大家先有个印象，后面还会提到

• 记录的真实数据就是记录每一列的实际值喽，当然为NULL值的列是不需要存储的，除此之外，MySQL会为每个记录默认的添加一些列（也称为隐藏列），具体的列如下：

这里需要提一下InnoDB表对主键的生成策略：优先使用用户自定义主键作为主键，如果用户没有定义主键，则选取一个Unique键作为主键，如果表中连Unique键都没有定义的话，则InnoDB会为表默认添加一个名为row_id的隐藏列作为主键。所以我们从上表中可以看出：InnoDB存储引擎会为每条记录都添加 transaction_id 和 roll_pointer 这两个列，但是 row_id 是可选的（在没有自定义主键以及Unique键的情况下才会添加该列）。这些隐藏列的值不用我们操心，InnoDB存储引擎会自己帮我们生成的。

行溢出

MySQL中磁盘和内存交互的基本单位是页，也就是说MySQL是以页为基本单位来管理存储空间的，我们的记录都会被分配到某个页中存储。而一个页的大小一般是16KB，也就是16384字节，而一个VARCHAR(M)类型的列就最多可以存储65532个字节，这样就可能造成一个页存放不了一条记录的尴尬情况。

在Compact和Redundant行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的一部分数据，把剩余的数据分散存储在几个其他的页中，然后记录的真实数据处用20个字节存储指向这些页的地址（当然这20个字节中还包括这些分散在其他页面中的数据的占用的字节数），从而可以找到剩余数据所在的页，如图所示：

从图中可以看出来，对于Compact和Redundant行格式来说，如果某一列中的数据非常多的话，在本记录的真实数据处只会存储该列的前768个字节的数据和一个指向其他页的地址，然后把剩下的数据存放到其他页中，这个过程也叫做行溢出，存储超出768字节的那些页面也被称为溢出页。画一个简图就是这样：

最后需要注意的是，不只是 VARCHAR(M) 类型的列，其他的 TEXT、BLOB 类型的列在存储数据非常多的时候也会发生行溢出。

Dynamic和Compressed行格式，我现在使用的MySQL版本是5.7，它的默认行格式就是Dynamic，这俩行格式和Compact行格式挺像，只不过在处理行溢出数据时有点儿分歧，它们不会在记录的真实数据处存储字段真实数据的前768个字节，而是把所有的字节都存储到其他页面中，只在记录的真实数据处存储其他页面的地址，就像这样：

Compressed行格式和Dynamic不同的一点是，Compressed行格式会采用压缩算法对页面进行压缩，以节省空间。

页是如何管理多条记录的

我们上面简单介绍了一条记录的格式大概是什么样子的，下面来聊聊存放记录的容器—页。

数据页代表的这块16KB大小的存储空间可以被划分为多个部分，不同部分有不同的功能，各个部分如图所示：

看到上面给出的一个页的结构图，不少人可能都已经懵逼了，不急，我们一点点顺着开发者的视角来看。

页是用来存储记录的，可以看做是一个保存记录的容器，那么初始页应该是空的:

当我们有一条记录需要存放到当前页中时，首先需要从Free Space申请一个记录大小的空间来存放，那么此时Free Space就需要划分为两部分，一部分是已经被使用了的User Records部分，还有一部分就是剩余的Free Space。

先不需要管页的其他部分，目前就假设只分为Free Space和User Records两部分

当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了。

此时问题又出现了，User Records部分中的多条记录该用什么样的数据结构进行保存呢？

• 数组吗？— 每条记录的大小都是不固定的，不能使用数组
• 链表吗？— 正确的想法，那么如何实现呢?

显然，当前情况下，链表才是首选，那么如何让多条记录间形成链表的串联关系呢？

还记得上面说过的，每条记录都带有一个头信息吗?

这里就需要用到每条记录带有的头信息了，先来简单介绍一下:

• delete_mask： 这个属性标记着当前记录是否被删除，占用1个二进制位，值为0的时候代表记录并没有被删除，为1的时候代表记录被删除掉了。

这些被删除的记录不会立即从磁盘上移除，是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗，所以只是打一个删除标记而已，所有被删除掉的记录都会组成一个所谓的垃圾链表，在这个链表中的记录占用的空间称之为所谓的可重用空间，之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。

• min_rec_mask: B+树的每层非叶子节点中的最小记录都会添加该标记(后面会讲到)
• n_owned: 机密，下面会慢慢揭开他神秘的面纱
• heap_no: 当前记录在当前页的记录列表中的下标,我们插入的记录下标默认从2开始，为啥，下面会讲
• record_type: 当前记录的类型，一共有4种类型的记录，0表示普通记录，1表示B+树非叶节点记录，2表示最小记录，3表示最大记录。我们自己插入的记录就是普通记录，它们的record_type值都是0。
• next_record: 表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量

相信大家已经猜出来了，页中的多条记录就是靠着每条记录头信息中的next_record属性，指向下一条记录，从而形成一个链表。

Innodb为当前链表规定了头尾节点，方便操作，头尾节点在这里也被称为最小记录和最大记录，英文为: Infimum 和Supremum。

heap_no的下标0和1也就是分配给了头尾节点，因此我们插入的记录默认从2开始算起。

这也就对应了每个页中为啥都会有Infimum 和Supremum两部分的原因。

所以，此时页中记录的组织形式就如下所示:

当我们需要删除第2条记录的时候，其实需要做的也就是正常链表中移除某一元素的操作了:

当然，还会把第二条记录的delete_mask标记设置为1，表示删除该记录。

当数据页中存在多条被删除掉的记录时，这些记录的next_record属性将会把这些被删除掉的记录组成一个垃圾链表，以备之后重用这部分存储空间。

并且从图中可以看出来，我们的记录按照主键从小到大的顺序形成了一个单链表，不论我们怎么对页中的记录做增删改操作，InnoDB始终会维护一条记录的单链表，链表中的各个节点是按照主键值由小到大的顺序连接起来的。

因为主键值为2的记录被我们删掉了，但是存储空间却没有回收，如果我们再次把这条记录插入到表中，会发生什么事呢？

从图中可以看到，InnoDB并没有因为新记录的插入而为它申请新的存储空间，而是直接复用了原来被删除记录的存储空间。

如何快速定位页中某一条记录

现在我们了解了记录在页中按照主键值由小到大顺序串联成一个单链表，那如果我们想根据主键值查找页中的某条记录该咋办呢？

• 可能聪明的小伙伴第一时间想到了二分法,毕竟是有序的单链表，但是，你细品 , 这是链表哎，不是数组，所以不能用二分法，那该怎么办呢？ 难不成从头到尾遍历一遍链表，这也太慢了吧 !

大家都买过书，一本书少则几十页，多则上百页，如果我们想看书中某部分内容，会借助目录快速查找，这里页中存放了多条记录，少则几十条，多则成千上百条，如果要快速定位一条记录，我们是不是也可以整个目录出来?

这里我们可以把六条记录算为一组，用一个槽指向当前组最后一条记录结束的位置，然后在当前页中单独开辟一块地方存放这些槽，这些槽组成了一个数组，就可以使用二分法进行快速查找，定位记录到某个组，某个组内再进行链表遍历，因为每个组内记录数很少，因此性能影响不大。

Innodb内部就是这样实现的，下面我简单讲讲Innodb实现思路:

• 将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组。
• 每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该记录拥有多少条记录，也就是该组内共有几条记录。
• 将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近页的尾部的地方，这个地方就是所谓的Page Directory，也就是页目录（此时应该返回头看看页面各个部分的图）。页面目录中的这些地址偏移量被称为槽（英文名：Slot），所以这个页面目录就是由槽组成的。

比方说现在的page_demo表中正常的记录共有6条，InnoDB会把它们分成两组，第一组中只有一个最小记录，第二组中是剩余的5条记录，看下边的示意图：

为什么最小记录的n_owned值为1，而最大记录的n_owned值为5呢，这里头有什么猫腻么？

设计InnoDB的大叔们对每个分组中的记录条数是有规定的：对于最小记录所在的分组只能有 1 条记录，最大记录所在的分组拥有的记录条数只能在 1~8 条之间，剩下的分组中记录的条数范围只能在是 4~8 条之间。所以分组是按照下边的步骤进行的：

• 初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组。
• 之后每插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8个。
• 在一个组中的记录数等于8个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。

核心是为了通过槽组成的有序数组实现二分快速查找，定位到某个组(无法精确定位到某个记录)，组内记录个数会限制的比较小，确保组内顺序遍历查找的效率不会太低

所以在一个数据页中查找指定主键值的记录的过程分为两步：

• 通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最小的那条记录。
• 通过记录的next_record属性遍历该槽所在的组中的各个记录。

Page Header

到此为止，我们已经解决了页存储记录和快速查找记录的难题，但是我们还需要一块地方来记录当前页的相关状态信息，如: 本页中已经存储了多少条记录，第一条记录的地址是什么，页目录中存储了多少个槽等等。

这些信息就存放在Page Header中:

它是页结构的第二部分，这个部分占用固定的56个字节，专门存储各种状态信息，具体各个字节都是干嘛的看下表：

File Header

Page Header是专门针对数据页记录的各种状态信息，比方说页里头有多少个记录了呀，有多少个槽了呀。我们现在描述的File Header针对各种类型的页都通用，也就是说不同类型的页都会以File Header作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页、下一个页是谁啦。

• FIL_PAGE_OFFSET: 每一个页都有一个单独的页号，就跟你的身份证号码一样，InnoDB通过页号来可以唯一定位一个页。
• FIL_PAGE_TYPE: 这个代表当前页的类型，我们前边说过，InnoDB为了不同的目的而把页分为不同的类型，我们上边介绍的其实都是存储记录的数据页，其实还有很多别的类型的页，具体如下表：

我们存放记录的数据页的类型其实是FIL_PAGE_INDEX，也就是所谓的索引页。

• FIL_PAGE_PREV和FIL_PAGE_NEXT: 我们前边强调过，InnoDB都是以页为单位存放数据的，有时候我们存放某种类型的数据占用的空间非常大（比方说一张表中可以有成千上万条记录），InnoDB可能不可以一次性为这么多数据分配一个非常大的存储空间，如果分散到多个不连续的页中存储的话需要把这些页关联起来，FIL_PAGE_PREV和FIL_PAGE_NEXT就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了，而无需这些页在物理上真正连着。需要注意的是，并不是所有类型的页都有上一个和下一个页的属性，不过我们本集中唠叨的数据页（也就是类型为FIL_PAGE_INDEX的页）是有这两个属性的，所以所有的数据页其实是一个双链表，就像这样：

File Trailer

我们知道InnoDB存储引擎会把数据存储到磁盘上，但是磁盘速度太慢，需要以页为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了一半的时候中断电了咋办，这不是莫名尴尬么？为了检测一个页是否完整（也就是在同步的时候有没有发生只同步一半的尴尬情况），设计InnoDB的大叔们在每个页的尾部都加了一个File Trailer部分，这个部分由8个字节组成，可以分成2个小部分：

• 前4个字节代表页的校验和

这个部分是和File Header中的校验和相对应的。每当一个页面在内存中修改了，在同步之前就要把它的校验和算出来，因为File Header在页面的前边，所以校验和会被首先同步到磁盘，当完全写完时，校验和也会被写到页的尾部，如果完全同步成功，则页的首部和尾部的校验和应该是一致的。如果写了一半儿断电了，那么在File Header中的校验和就代表着已经修改过的页，而在File Trailer中的校验和代表着原先的页，二者不同则意味着同步中间出了错。

• 后4个字节代表页面被最后修改时对应的日志序列位置（LSN）

这个部分也是为了校验页的完整性的，只不过我们目前还没说LSN是个什么意思，所以大家可以先不用管这个属性。

这个File Trailer与File Header类似，都是所有类型的页通用的。

索引

回顾

各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

页和记录的关系示意图如下：

其中页a、页b、页c … 页n 这些页可以不在物理结构上相连，只要通过双向链表相关联即可。

如何进行数据查找

假设目前表中的记录比较少，所有的记录都可以被存放到一个页中，那么我们查找数据的时候，也只需要在一个页中进行查找即可：

• 以主键为搜索条件

这个查找过程我们已经很熟悉了，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

• 以其他列作为搜索条件

对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。

大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：

• 定位到记录所在的页。
• 从所在的页内中查找相应的记录。

定位到记录所在的页后，就是对当前页进行数据查找，可以采用查询页目录的方式，快速定位到页中我们需要的那一条记录。

现在问题是表中的数据很大的情况下，需要很多个数据页进行保存，这些数据页串联成链表的形式，那么我们需要快速定位到我们的记录再哪一个数据页中呢?

这个问题其实和一开始询问如何在当前页中快速定位一条记录是同样的，如果采用遍历页链表的方式逐个进行过滤，那么显然太慢了，能不能向页中定位记录一样，给出一个类似于页目录的实现呢？

如何快速定位某个页

现在我们面临的问题就是如何快速定位记录存在于哪个页中，直接的想法就是模仿页目录的操作方式，给页链表上这些页整个目录，这个目录也被称为索引。

为了快速定位页中某条记录，我们整了个页目录 为了快速定位记录在哪个页中，我们整了个目录(索引)

按照直观想法来实现一个简易索引

我们在根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？

因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以 不得不 依次遍历所有的数据页。所以如果我们想快速的定位到需要查找的记录在哪些数据页中该咋办？还记得我们为根据主键值快速定位一条记录在页中的位置而设立的页目录么？我们也可以想办法为快速定位记录所在的数据页而建立一个别的目录，建这个目录必须完成下边这些事儿：

• 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。

这里我们假设一个页中最多存放三条记录

我们往一张demo表中插入三条记录,这三条记录被存储到页10上:

此时如果我们再插入一条记录呢?

因为页10最多只能放3条记录，所以我们不得不再分配一个新页：

咦？怎么分配的页号是28呀，不应该是11么？再次强调一遍，新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。它们只是通过维护着上一个页和下一个页的编号而建立了链表关系。另外，页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图如下：

这个过程表明了在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂。

由于数据页的编号可能并不是连续的，所以在向表中插入许多条记录后，可能是这样的效果：

因为这些16KB的页在物理存储上可能并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：

• 页的用户记录中最小的主键值，我们用key来表示。
• 页号，我们用page_no表示。

所以我们为上边几个页做好的目录就像这样子：

以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5。我们只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现根据主键值快速查找某条记录的功能了。比方说我们想找主键值为20的记录，具体查找过程分两步：

• 先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为 12 < 20 < 209），它对应的页是页9。
• 再根据前边说的在页中查找记录的方式去页9中定位具体的记录。

至此，针对数据页做的简易目录就搞定了，这个简易的目录上面也说了，被称为索引。

我们实现的简易索引还有什么不足呢?

• 因为一个页对应一个页目录项，如果页非常滴多，那么对应的页目录项就会非常滴多，那么使用二分法查找到对应页的耗时就会增加，这该怎么解决呢？
• 二分法查找的前提是页目录项是连续存储在内存上的，这样的前提一定能够确保成立吗？

Innodb和磁盘交互的最小单元是页，因此可以确保一整个页同时被加载进内存，而页目录项也一定是在内存上连续存储的,这才可以使用二分法快速定位

小结

本文，我们主要介绍了Innodb存储引擎中一条记录的行格式，以及存储记录的最小单位页的设计，最后我们设计了一个简单的索引实现，来争取能够快速根据主键定位记录在哪个页中。

下一篇文章，我们将来学习Innodb是如何来实现索引的，敬请期待。

参考

本篇文章参考 : <<从根上理解Mysql>> 一书创作而成，本文旨在用更短的篇幅理清Innodb索引的实现思路，如果想完整学习Innodb索引实现原理的小伙伴，建议可以阅读: MySQL 是怎样运行的：从根儿上理解 MySQL