InnoDB存储引擎的物理结构

Table of Contents

要了解使用InnoDB存储引擎进行CRUD时发生了什么，怎么也绕不过其物理结构，于是在这里记录下。

只记录关键信息，能支持理解CRUD与事务特性即可

关于取舍 #

作为一个通用的数据存储方案，需要考虑很多问题，这些问题包括如何占用更少的磁盘、内存，如何提高CRUD的速度，如何保证数据的一致性等待。

作为一个通用的方案，就一定要对这些问题进行取舍，而在InnoDB的设计中，可以看到其优先考虑减少磁盘随机IO，然后是占用更少的磁盘空间。而为了支持事务的特性，而引入了undo log和redo log等组件，导致整体设计上的复杂度很高。看完InnoDB的设计，再对比redis的设计，就能感慨redis的简洁，但是这不代表redis的设计更优雅，每个组件的定位不同，使用场景也不同，设计上自然也就不同。

磁盘 #

页 #

页是InnoDB最基本的存储单位。

页由File Header、Page Header、Infimum+Supremum、UserRecords、Free Space、Page Directory、File Trailer组成。

File Header #

File Header通用于各种类型的页，用户记录页号、页类型、校验和、所属表空间、上下页的页号等。

这些页通过上下页的页号构建了一个双向链表，无需这些页在物理上真正连着。

File Trailer #

File Trailer由8字节组成。

前4个字节表示页的校验和，此校验和应该与File Header的校验和相等，如果不等，说明刷新页的过程被中断了，如断电。

后4个字节表示页面最后修改时对应的LSN的后4字节，正常情况下与File Header的Fil_PAGE_LSN的后4字节相同。也是用来校验页的完整性的。

Page Header用来存储页的状态，如存储的记录条数、槽的数量、Free Space在页面的地址偏移量等。

User Record 和 Free Space #

User Record和Free Space组成了页的剩余部分，每次插入数据时，都会从Free Space申请一部分空间划到User Record中。

在User Record中是一条条紧密相邻的记录。记录中包括一些控制信息，比如记录是否被删除、下一条记录的相对位置（next_record）等。

通过next_record，页中的记录组成了一个单向链表，链表是根据主键大小由小到大按顺序连接的，因此为了更快的找到最大值和最小值，页中又引入了两个虚拟记录——最大记录（Supremum）和最小记录(Infimum)。

Page Directory #

如果没有页目录，那么查找一条数据只能遍历查找，所以InnoDB引入了页目录。

页目录只记录每组记录的最大值，这些最大值在页目录中被称为槽(Slot)，槽在页目录中也是从小到大按顺序存放的。

记录的分组规则：

最开始时只有两个虚拟记录Supremum和Infimum，各自占一个槽。
插入数据时，找到比插入数据大的第一个槽（二分法），将其插入到这个组中。
1. 如果插入后该组的记录数大于8个，那么就将这个槽拆分成两个组，并在页目录中增加一个槽，其中小槽中分配到的记录数为5条，大槽中分配到的记录数为4条。

由上可知分组的记录特色：

第一个槽Infimum只有其自身一条记录
最后一个槽Supremum记录数为1-8条
中间槽的记录数为4-8条

在页中查找一条记录时：

通过二分法确定该记录所在的槽（先找到比该记录主键大的第一个槽，再找到上一个槽，根据其next_record找到记录所在槽的最小记录地址）
通过next_record遍历该组中的各个记录

索引 #

在查询数据时，首先需要定位数据存在于哪个页时，虽然通过遍历数据页组成的链表查询到，但性能太差，因此引入了索引。

在页中，为了更快的找到记录，引入了Page Directory，而为了更快的找到页，也要引入这样一个目录项。

目录项的结构与数据页的结构没什么不同（目录项也是一种页），只不过数据页存储的数据是用户记录，而目录项存储的数据是索引键+页号。目录项所在的页填满后，就会进行“页分裂”拆分成两个页，同时增加一个新的父目录项。每层目录项都同数据页一样组成了双向链表。

目录项和PageDirectory不同的是：Page Directory存储的是一组记录中的最大值，而目录项存储的是一个页中的最小值。

这些目录项和索引页就组成了我们常说的B+树。

聚簇索引 #

聚簇索引中目录项记录的数据是主键+页号，叶子结点记录的是真实的用户记录。

二级索引 #

二级索引中目录项记录的数据是索引键+主键+页号（存主键是为了防止两个“槽”的值相同时，没办法区分数据要插入到哪个“槽”），叶子节点记录的是主键值+索引键。

查询时，先通过二级索引找到主键，再“回表”查询——通过主键根据聚簇索引查询。

联合索引 #

联合索引中的目录项记录的数据是这些索引和主键值，先根据第一个索引排序，在第一个索引相同的情况下，再根据第二个索引进行排序，以此类推。叶子结点中存放的是这些索引值和主键值。

类比MyISAM #

MyISAM的数据是单独存放的，每条记录都有唯一的行号。

索引信息会保存到另外一个文件中，索引的叶子结点存储的是主键+行号。因此，MyISAM中的索引都相当于InnoDB中的二级索引。

所以业内常说：InnoDB中的索引即数据，数据即索引；MyISAM中则是索引是索引，数据是数据。

表空间 #

系统表空间对应文件系统中一个或多个实际文件。

每个独立表空间对应文件系统中一个名为“表名.idb”的实际文件。

区 #

一个表空间最多可以有2^32个页，如果按页的默认大小16KB来算，则一个表空间最多支持64TB的数据。

为了管理如此多的页，引入了区的概念。

对于16KB的页来说，连续的64个页面就是一个区，即区的大小默认为1MB.

即使引入了区，对于一个表空间来说，区的数量还是太多了，于是又将每256个区分成为一组。

第一组的最开始的3个页面用来记录整个表空间的属性和本组所有区的属性、change buffer以及INODE Entry。

其余组的前两个页面用来记录本组的区的属性以及change buffer的信息。

引入区还能减少磁盘的随机IO：B+树的每一层中的页都会形成双向链表，如果以页为单位来分配存储空间，那么相邻的两个页之间的物理地址可能离的非常远，这对于传统的机械硬盘来说，需要重新定位磁头位置，即随机IO。因此让页面链表中相邻的页物理位置也相邻，能够在扫描叶子节点中大量记录时使用顺序IO。

段 #

在使用B+树执行查询时只是扫描叶子节点的记录，所以将叶子节点和非叶子节点区分开——即使用不同的区，能够使扫描效率更高。

于是就提出了段的概念：一个索引会生成两个段，一个叶子节点段，一个非叶子节点段。除此之外还有其他特殊段，如回滚段等。

从上述可知，一个表最少会存在两个段，对应于最少两个区，也就是2MB。考虑到有些小表只有几条记录，不需要2MB的空间，因此又提出了碎片区的概念。

在碎片区中，这些页可以用于不同的段。碎片区直属于表空间。有了碎片区后，为段分配存储空间的策略变为：

刚开始向表中插入数据时，段从碎片区获取页来分配存储空间。
当某个段已占用了32个碎片区页后，再次分配存储空间就会以完整的区来分配。（已占用的碎片区不会复制到新申请的完整的区中）

Change Buffer #

每个分组区的第二个页的类型都是IBUF_BITMAP，用于记录Change Buffer。

插入数据时，需要先插入聚簇索引，再插入每个二级索引。这些页面在表空间中随机分布，会产生大量的随机IO。更新和删除操作同理。所以引入了Change Buffer。其本质也是一颗B+树，根节点存储在系统空间中。

在修改非唯一二级索引页面时（修改唯一二级索引不一定用到Change Buffer），如果页未加载到内存中，那么该修改先被放在Change Buffer中，之后再找时机合并到对应页面。

内存 #

Buffer Pool #

InnoDB存储引擎读写数据都是以页为单位的。为了减少磁盘IO，当我们读写页时，先将其加载到内存中，这样当下次再访问该页时，就能省下磁盘IO了。

当Mysql服务器启动时，向操作系统申请一片连续的内存，内存的主要结构是缓冲页和控制块

缓冲页 #

Buffer Pool对应的一片连续的内存被划分为若干个页面，页面大小与InnoDB表空间使用的页面大小一致。从磁盘中加载到Buffer Pool里的数据页称为缓冲页。

控制块 #

每个缓冲页都存在一个控制块，控制块中存放缓冲页的控制信息，如所属表空间编号、页号、内存地址、链表节点信息等。

缓冲页和控制块虽然是一一对应的，但是控制块放在一起，缓冲页放在一起，中间剩余的是碎片。这样做的好处是能够更高效的使用内存，因为缓冲页大小是固定的，控制块也是固定的，而两者大小不同（有点类似于golang的map的key和value的存储）。

free链表 #

为了区分缓冲页是否被使用，需要做标记。我们可以在控制块中做标记，但是这样每次都需要遍历整个控制块列表，所以InnoDB在设计时使用链表来标识——将控制块放到一个链表中来表示未被使用。

每次从磁盘中加载一个数据页到Buffer Pool中时，就从free链表中取一个空闲的缓冲页，并填充对应的控制块信息，然后把该控制块从free链表中移除。

缓冲页的哈希处理 #

不管是CRUD，我们都需要知道一个页是否在Buffer Pool中，这时就需要用到哈希表。

哈希表的key为其唯一标识——表空间号+页号，value为其控制块。

flush链表 #

我们需要记录哪些缓冲页被修改了（被修改的页称为脏页），这样的页会最终刷新到磁盘中。所以有了flush链表。flush链表和free链表结构一样。

LRU链表 #

当BufferPool的大小不够用时，我们需要移除一些数据。这里采用的是淘汰最近最少使用的缓冲页。

最简单的实现就是将最新使用的的缓冲页对应的控制块（后边简称数据吧）放到链表头部，当内存不够用时，移除链表尾部的数据。但是一些特殊操作使得情况变得复杂：

InnoDB含有预读功能。
1. 线性预读：如果顺序访问一个区的页面超过一个系统值，就会触发异步操作将下一个区中的全部页面放到Buffer Pool中。
2. 随机预读：如果某个区的13个连续页面（这些页面都在young区）都被加载到BufferPool中，就会触发异步操作将本区中的其他页面放到BufferPool中。
全表扫描：如果表的数据较大，会“重置”BufferPool。

为了解决这些问题，InnoDB将LRU链表分为两部分，分别是使用频率非常高的数据和频率不高的数据，简称young和old。默认情况下old占LRU链表的比例是37%。

解决“预读问题”：初次加载的数据放到old的头部，这样就不会影响young
解决“全表扫描问题”：全表扫描的频率是很低的，因此在控制块中记录第一次访问的时间，如果当前访问的时间减去首次访问时间小于1s（默认值），那么就不会将其放到young的头部。（一次全表扫描，多次读取一个页的多个记录时，多次访问一个页面的时间间隔不会超过1s）

为了避免频繁修改LRU链表，规定只有被访问的数据位于young区域的1/4后面时，才会移动到LRU链表头部。

多BufferPool实例以及动态调整BufferPool大小 #

访问BufferPool的各种链表时都需要加锁处理，单一的BufferPool会影响性能，因此需要拆分成多个。那么如何根据页的信息定位到BufferPool实例？应该是将BufferPool实例的编号放到了控制块中。

在调整BufferPool大小后，需要重新向操作系统申请一块的连续空间，然后将旧的数据复制过去。

InnoDB将BufferPool以chunk为单位进行切割，这样修改时就不用修改整个BufferPool。