InnoDB表结构与页结构详解

╰半夏微凉° 2023-01-16 06:34 27阅读 0赞

# 前言 #

写这篇文章的初衷是为了探索数据在InnoDB中如何存储的，文章从表在InnoDB中的存储形式讲到页的结构，以及索引树与页的关系，页分裂问题等。

# 一、InnoDB表结构 #

从MySQL 5.6版本开始`innodb_file_per_table`参数默认设置为1。该配置下你的每一个表都会单独作为一个文件存储（如果有分区也可能有多个文件）。在MySQL的设定中，同一个表空间内的一组连续的数据页为一个extent（区），默认区的大小为1MB，页的大小为16KB。16\*64=1024，也就是说一个区里面会有64个连续的数据页。连续的256个数据区为一组数据区。

于是我们可以画出这张图：

![img][]

## **InnoDB逻辑存储结构** ##

[https://zhuanlan.zhihu.com/p/96432864][https_zhuanlan.zhihu.com_p_96432864]

从InnoDB存储应引擎的存储结构来看，所有的数据都被逻辑的存放在一个空间中，成为表空间（tablespace）。表空间又由段（segment）、区（extent）、页（page）组成。页在一些文档中也成为块（block），InnoDB存储引擎的逻辑存储结构大致如图：

![img][img 1]

### 区（extent）的概念 ###

**区可以理解为创建某个聚簇索引，即创建B+树，非叶子节点都是索引页，这些索引页组成了一个区，因为一个区是物理位置上连续的64个页，因此便于顺序查找。**

表空间中的页实在是太多了，为了更好的管理这些页面，设计`InnoDB`的大叔们提出了`区`（英文名：`extent`）的概念。对于16KB的页来说，连续的64个页就是一个`区`，也就是说一个区默认占用1MB空间大小。

为啥好端端的提出一个`区`（`extent`）的概念呢？我们以前分析问题的套路都是这样的：表中的记录存储到页里边儿，然后页作为节点组成`B+`树，这个`B+`树就是索引，然后吧啦吧啦一堆聚簇索引和二级索引的区别。这套路也没啥不妥的呀～

是的，如果我们表中数据量很少的话，比如说你的表中只有几十条、几百条数据的话，的确用不到`区`的概念，因为简单的几个页就能把对应的数据存储起来，但是你架不住表里的记录越来越多呀。

？？啥？？表里的记录多了又怎样？`B+`树的每一层中的页都会形成一个双向链表呀，`File Header`中的`FIL_PAGE_PREV`和`FIL_PAGE_NEXT`字段不就是为了形成双向链表设置的么？

是的是的，您说的都对，从理论上说，不引入`区`的概念只使用`页`的概念对存储引擎的运行并没啥影响，但是我们来考虑一下下边这个场景：

*  我们**每向表中插入一条记录，本质上就是向该表的聚簇索引以及所有二级索引代表的`B+`树的节点中插入数据**。而`B+`树的每一层中的页都会形成一个双向链表，如果是以`页`为单位来分配存储空间的话，双向链表相邻的两个页之间的物理位置可能离得非常远。我们介绍`B+`树索引的适用场景的时候特别提到范围查询只需要定位到最左边的记录和最右边的记录，然后沿着双向链表一直扫描就可以了，而如果链表中相邻的两个页物理位置离得非常远，就是所谓的`随机I/O`。再一次强调，磁盘的速度和内存的速度差了好几个数量级，`随机I/O`是非常慢的，所以我们应该尽量让链表中相邻的页的物理位置也相邻，这样进行范围查询的时候才可以使用所谓的`顺序I/O`。

所以，所以，所以才引入了`区`（`extent`）的概念，**一个区就是在物理位置上连续的64个页**。在表中数据量大的时候，**为某个索引分配空间的时候就不再按照页为单位分配了，而是按照`区`为单位分配，甚至在表中的数据十分非常特别多的时候，可以一次性分配多个连续的区**。虽然可能造成一点点空间的浪费（数据不足填充满整个区），但是从性能角度看，可以消除很多的随机`I/O`，功大于过嘛！

### 段（segment）的概念 ###

**叶子节点和非叶子节点进行了区别对待，也就是说叶子节点有自己独有的`区`，非叶子节点也有自己独有的`区`，存放区的集合即为段。**

事情到这里就结束了么？太天真了，我们提到的范围查询，其实是对`B+`树叶子节点中的记录进行顺序扫描，而如果不区分叶子节点和非叶子节点，统统把节点代表的页面放到申请到的区中的话，进行范围扫描的效果就大打折扣了。所以设计`InnoDB`的大叔们对`B+`树的叶子节点和非叶子节点进行了区别对待，也就是说叶子节点有自己独有的`区`，非叶子节点也有自己独有的`区`。**存放叶子节点的区的集合就算是一个`段`（`segment`），存放非叶子节点的区的集合也算是一个`段`。也就是说一个索引会生成2个段，一个叶子节点段，一个非叶子节点段。**

# 二、InnoDB数据页结构 #

## 结构概述（粗略介绍） ##

[https://mp.weixin.qq.com/s/\_ka7cY0R3GJ-ox9V\_d30AQ][https_mp.weixin.qq.com_s_ka7cY0R3GJ-ox9V_d30AQ]

**总结：**

1、InnoDB查找数据是从磁盘中拿数据页，拿到数据页后再查数据页中的行记录

2、页分为数据页、索引页等，页的结构会有不同，例如B+树非叶子节点的索引页，都是存储键值和指针，叶子节点的则是普通的数据页

3、数据页与数据页之间是双向链表（每个页的File Header会有当前页的页号以及上一个页和下一个页的页号）

4、数据页内，每条行记录之间是单向链表（行记录的头信息中next\_record会记录下一个记录的地址偏移，相当于单链表，其中最小记录和最大记录是一开始就固定的，infimum是链表头，supermum是链表尾，具体可参见后面页面目录的介绍）

5、数据页内进行查找时，并不是单链表一个个遍历，而是将行记录分组，每组最后一条数据的真实数据位置偏移放在页面的`page directory`中，这个就是页的目录了，查找行记录的时候根据目录进行二分查找

6、为保证从内存中同步到磁盘的页的完整性，在页的首部和尾部都会存储页中数据的校验和和LSN值，如果首部和尾部的校验和和LSN值校验不成功的话，就说明同步过程出现了问题。

7、创建索引即是创建索引树，数的每个节点都是页，因此之后对数据操作需要去维护这些页。利用键值查询某数据，会先从磁盘中拉取根页（从索引节点开始搜索），根据**page directory区域使用二分法定位到索引行在内页的位置**，**根据索引行定位到下一级索引页的位置**，**再递归查找下一个索引**页，直到定位到数据页。

8、数据页内的行记录之间，是根据主键的大小进行排序的，因此主键最好是自增的。若不是自增的，会发生页分裂，影响效率。

9、InnoDB逻辑存储结构由段（segment）、区（extent）、页（page）组成。以B+树为例，一个索引会生成2个段，一个叶子节点段，一个非叶子节点段。其中非叶子节点段（segment）由非叶子节点区（extent）组成，区中存放着物理地址连续的索引页（page）。当有另一个索引出现时，会以另一个extend形式存在于segment中。叶子节点段（segment）即存放着叶子节点区，区内包含着数据页。

### **一、InnoDB页说明** ###

InnoDB是将磁盘上的数据拿到内存里操作，然后放回磁盘上的，因此关机后数据依然存在。但我们都知道Mysql数据库能放的数据是非常大的，不可能一次把所有数据都加载到内存里，也不能一条一条的把数据拿出来。而I**nnoDB是将数据分为很多页，一个页占16KB，以页为单位拿数据**，页其实也有很多种类，比如存放undo日志的信息页，存放数据的数据页等。我们这次则是将目光聚集到数据页。

### **二、InnoDB页构成** ###

一个数据页是由很多部分构成的：文件头部（File Header）、页面头部(Page Header)、最小记录和最大记录(Infimum + Supremum)、**用户数据（User Records）**、空闲空间（Free Space）、页面目录(Page Directory)、文件尾部(File Trailer)。

![img][img 2]

我们在一个页中，每插入一条数据都会从空闲空间中拿到一部分空间，放我们的数据，当空闲空间被占完了，这个页也就满了，于是再有新的数据插入，就会申请一个新的页。（页号不是顺序分配的）若删除数据，则是把行记录头信息的delete\_mask置为1，而不是马上删除，而且这部分存储空间之后还可以重用，也就是说之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。

### **三、InnoDB页面目录** ###

在一个页内，**有很多条数据，这些数据会根据主键的值，由小到大排列，通过一个单向链表来存储数据**。

既然是通过链表存储数据页中数据，那要查找某条数据的话，InnDB是沿着链表找下去吗？

不是的！为了提高查询的效率，InnoDB将所有的页中数据按顺序分为几组，每一组的最后一条数据的会记录该组有多少条数据。然后将每一组的最后一条数据的地址放在页面目录里。页目录里的数据的地址就称为槽。

所有，在一个页面中找某条数据是这样的：

1.  先通过二分法确定一条数据所在的槽（通过比对槽所对应的主键大学），再找到槽所对应组的主键最小的记录。
2.  然后再通过向下遍历，直到找到所需的数据。

比如，现在有一个页，里面有16条数据，共有5个槽：0,1,2,3,4。我现在要查找主键为6的数据，会先计算中间槽的位置（0+4）/2=2，中间槽是2号槽，然后比对它的主键和6的大小，如果2号槽的主键大于6就继续计算中间槽的位置，和6比对。也就是二分法查找，这样的效率就会比只使用链表遍历快多了。

#### 先说说插入一条记录，这条记录是什么样子的 ####

[https://www.jianshu.com/p/e13e70b90a45/][https_www.jianshu.com_p_e13e70b90a45]

![img][img 3]

这里重要的几点  
`n_owned` 当前记录的记录数  
`next_record` 下条记录相对位置  
`delete_mask` 标记是否删除  
`heap_no` 当前记录在页中的位置

因为数据储存是一个单向链表，这个值是记录的该条数据真实值，到下一条记录真实值的地址偏移。这样用就可以通过上一条记录找到下一条记录。  
下一条记录是指的下一个索引值的记录，而不是插入的顺序。在innoDB中，删除一条数据的操作，只会将`delete_mask`标记为1，上一条记录的`next_record`会自动变成下一条有效数据的地址偏移。  
因为删除这个记录，会需要重排所有记录值，这样性能会有问题，但是被标记删除的记录位置，会变成可重用位置。之后再插入索引值为该位置的时候，会将此处重写。也就是说，单向链表，永远是按照索引顺序排列，新插入未制定索引都会插入到最后位置。  
页初始化会有最大最小记录，最大记录的`next_record`为0，说明这就是最后一条。

#### 根据页面目录查询 ####

如果傻瓜式查询，从头开始查，什么时候查到了，什么时候结束，这就太傻了。  
所以innoDB觉得不能这么傻，决定搞点东西，让查询更快一些。  
于是想到了目录这个东西。  
因为所有数据都是在一个链表中，所以要给这个链表做一个目录  
目录怎么做？  
他会将所有数据，包括最大最小，分组。再将每组最后一条数据的真实数据位置偏移，放在页面的`page directory`中，这个就是页的目录了。  
每组中最后一条数据的`n_owned`是表示该组一共有多少条。

![img][img 4]

这个分组是什么规则，为啥最小记录自己一组？  
规定就是，最小记录分组只能他自己，别问我为什么，规定  
最大记录的那组，可以是1-8条，剩下的只能是4-8条  
来走一遍逻辑  
当一条都没有的时候，最小记录自己一组，最大记录自己一组  
当有7条记录的时候，最小记录一组，七条数据和最大记录一组，最大记录的`n_owned`为8  
在加一条数据的时候，会先去槽中找一下，找索引值比他大，且差值最小的，（因为槽记录的是组中最大的数据）。如果该组到了8条，那就分出去4条成为新的组，剩下四条和这个新数据组成一个组，槽会跟着改变。  
组搞好了，那就很简单了，直接用二分法找到对应的槽，然后遍历槽中的数据就可以了。毕竟槽中的数据很少了。  
槽中的第一条数据可以通过上一个槽的`next_record`找到。

### **四、InnoDB文件头部** ###

文件头部主要是**用来记录该页的页号，他的上一页页号，下一页页号，这样页与页之间就形成了一个双向链表的关系**,还记录了页的一些通用信息，就是每个页都有的信息。

### **五、InnoDB页面头部（Page Header）** ###

页面头部是用来**记录数据页的各种状态信息，比如一个页中有多少条记录，有多少个槽**等等。

### **六、InnoDB文件尾部（File Trailer）** ###

这个是起校验作用的东西  
可以分成两部分  
第一部分：校验和  
和fileheader是一样的，从内存同步到磁盘的时候，会先吧这个写进去。等同步完成，页尾的校验和，会和头部相同。  
如果同步一半没电了，那就不会一样。  
后面部分也是相同功能。

### 七、索引树和页的关系 ###

b树索引是怎么存的。

本质上b树索引也是存在索引页这一种类型的页上的一样。不同的点在于user records区域存的内容不用而已。索引只需要存储索引值+页号即可，如果不是主键索引，还需要存主键值。另外这些记录的行格式的type是1，表明是索引类型的记录。其余基本类似，page directory区域也存储了每一组的最大索引值。

所以查找过程就是：先从索引节点开始搜索，根据**page directory区域使用二分法定位到索引行在内页的位置**，**根据索引行定位到下一级索引页的位置**，**再递归查找下一个索引**页，直到定位到数据页。

![img][img 5]

### 八、页合并与分裂 ###

#### 页的内部原理 ####

页可以空或者填充满（100%），行记录会按照主键顺序来排列。例如在使用`AUTO_INCREMENT`时，你会有顺序的ID 1、2、3、4等。  
![C8kyE2t1AHSnBIW.jpg][]  
页还有另一个重要的属性：`MERGE_THRESHOLD`。该参数的默认值是50%页的大小，它在InnoDB的合并操作中扮演了很重要的角色。

![img][img 6]

当你插入数据时，如果数据（大小）能够放的进页中的话，那他们是按顺序将页填满的。

若当前页满，则下一行记录会被插入下一页（NEXT）中。  
![img][img 6]

根据B树的特性，它可以自顶向下遍历，但也可以在各叶子节点水平遍历。因为每个叶子节点都有着一个指向包含下一条（顺序）记录的页的指针。

例如，页\#5有指向页\#6的指针，页\#6有指向前一页（\#5）的指针和后一页（\#7）的指针。

这种机制下可以做到快速的顺序扫描（如范围扫描）。之前提到过，这就是当你基于自增主键进行插入的情况。但如果你不仅插入还进行删除呢？

#### 页合并 ####

当你删了一行记录时，实际上记录并没有被物理删除，记录被标记（flaged）为删除并且它的空间变得允许被其他记录声明使用。

![img][img 6]

当页中删除的记录达到`MERGE_THRESHOLD`（默认页体积的50%），InnoDB会开始寻找最靠近的页（前或后）看看是否可以将两个页合并以优化空间使用。

![img][img 6]

在示例中，页\#6使用了不到一半的空间，页\#5又有足够的删除数量，现在同样处于50%使用以下。从InnoDB的角度来看，它们能够进行合并。  
![img][img 6]

合并操作使得页\#5保留它之前的数据，并且容纳来自页\#6的数据。页\#6变成一个空页，可以接纳新数据。

![img][img 7]

如果我们在UPDATE操作中让页中数据体积达到类似的阈值点，InnoDB也会进行一样的操作。

规则就是：页合并发生在删除或更新操作中，关联到当前页的相邻页。如果页合并成功，在`INFOMATION_SCHEMA.INNODB_METRICS`中的`index_page_merge_successful`将会增加。

#### 页分裂 ####

前面提到，页可能填充至100%，在页填满了之后，下一页会继续接管新的记录。但如果有下面这种情况呢？

![img][img 8]

页\#10没有足够空间去容纳新（或更新）的记录。根据“下一页”的逻辑，记录应该由页\#11负责。然而：

![img][img 9]

页\#11也同样满了，数据也不可能不按顺序地插入。怎么办？

还记得之前说的链表吗（译注：指B+树的每一层都是双向链表）？页\#10有指向页\#9和页\#11的指针。

InnoDB的做法是（简化版）：

1.  创建新页
2.  判断当前页（页\#10）可以从哪里进行分裂（记录行层面）
3.  移动记录行
4.  重新定义页之间的关系

![img][img 10]

新的页\#12被创建：

![img][img 11]

页\#11保持原样，只有页之间的关系发生了改变：

*  页\#10相邻的前一页为页\#9，后一页为页\#12
 *  页\#12相邻的前一页为页\#10，后一页为页\#11
 *  页\#11相邻的前一页为页\#10，后一页为页\#13

（译注：页\#13可能本来就有，这里意思为页\#10与页\#11之间插入了页\#12）

这样B树水平方向的一致性仍然满足，因为满足原定的顺序排列逻辑。然而从物理存储上讲页是乱序的，而且大概率会落到不同的区。

规律总结：页分裂会发生在插入或更新，并且造成页的错位（dislocation，落入不同的区）

InnoDB用`INFORMATION_SCHEMA.INNODB_METRICS`表来跟踪页的分裂数。可以查看其中的`index_page_splits`和`index_page_reorg_attempts/successful`统计。

一旦创建分裂的页，唯一（译注：实则仍有其他方法，见下文）将原先顺序恢复的办法就是新分裂出来的页因为低于合并阈值（merge threshold）被删掉。这时候InnoDB用页合并将数据合并回来。

另一种方式就是用`OPTIMIZE`重新整理表。这可能是个很重量级和耗时的过程，但可能是唯一将大量分布在不同区的页理顺的方法。

另一方面，要记住在合并和分裂的过程，InnoDB会在索引树上加写锁（x-latch）。在操作频繁的系统中这可能会是个隐患。它可能会导致索引的锁争用（index latch contention）。如果表中没有合并和分裂（也就是写操作）的操作，称为“乐观”更新，只需要使用读锁（S）。带有合并也分裂操作则称为“悲观”更新，使用写锁（X）。

**分裂前**

![img][img 12]  
**分裂调整后**

页分裂的目的就是保证：后一个数据页中的所有行主键值比前一个数据页中主键值大。

![img][img 13]

#### 好的主键 ####

好的主键不仅对于数据查找很重要，而且也影响写操作时数据在区上的分布（也就是与页分裂和页合并操作相关）。

在第一个测试中我使用的是是自增主键，第二个测试主键是基于一个1-200的ID与自增值的，第三个测试也是1-200的ID不过与UUID联合。

插入操作时，InnoDB需要增加页，视为“分裂”操作：

![img][img 14]

表现因不同主键而异。

在头两种情况中数据的分布更为紧凑，也就是说他们拥有更好的空间利用率。对比半随机（semi-random）特性的UUID会导致明显的页稀疏分布（页数量更多，相关分裂操作更多）。

在页合并的情况中，尝试合并的次数因主键类型的不同而表现得更加不一致。

![img][img 15]

在插入-更新-删除操作中，自增主键有更少的合并尝试次数，成功比例比其他两种类型低9.45%。UUID型主键（图表的右一侧）有更多的合并尝试，但是合并成功率明显更高，达22.34%，因为数据稀疏分布让很多页都有部分空闲空间。

在辅助索引与上面主键索引相似的情况下，测试的表现也是类似的。

# 三、数据页结构的详细介绍 #

[https://blog.51cto.com/u\_15102959/2634084][https_blog.51cto.com_u_15102959_2634084]

[img]: /images/20221022/92eed02ca2094670b5ae4913a454c749.png
[https_zhuanlan.zhihu.com_p_96432864]: https://zhuanlan.zhihu.com/p/96432864
[img 1]: /images/20221022/319433cc93234542a35856adb9e97832.png
[https_mp.weixin.qq.com_s_ka7cY0R3GJ-ox9V_d30AQ]: https://mp.weixin.qq.com/s/_ka7cY0R3GJ-ox9V_d30AQ
[img 2]: /images/20221022/5e70c563a667451fadcd1d0a3824ac11.png
[https_www.jianshu.com_p_e13e70b90a45]: https://www.jianshu.com/p/e13e70b90a45/
[img 3]: /images/20221022/1b52c510585b4433930a8f1a18897556.png
[img 4]: /images/20221022/3909cd137f8647f1a0a1106d54b84d3e.png
[img 5]: /images/20221022/da830b9880be45238ac20775f4b39e41.png
[C8kyE2t1AHSnBIW.jpg]: https://i.loli.net/2021/04/24/C8kyE2t1AHSnBIW.jpg
[img 6]: /images/20221022/743b490d7b70489e969b1f4e49b636ea.png
[img 7]: /images/20221022/eacf9bdd709a41ccaa76ef96e46a2e07.png
[img 8]: /images/20221022/44465e8d79fe421d8a2c31db81fdedb3.png
[img 9]: /images/20221022/aaea7d260f494314907389557423f867.png
[img 10]: /images/20221022/2a86141698744587a9f32f8973806200.png
[img 11]: /images/20221022/655fe6cc481141079bc3fbe6133890ab.png
[img 12]: /images/20221022/9188865d8f154d92af6a08a5b6a6520a.png
[img 13]: /images/20221022/a3c8348faa9846aaa8571ddaa3fa0295.png
[img 14]: /images/20221022/045189182b074c509efa97f2e72bf2cd.png
[img 15]: /images/20221022/3725d1b4f1d34b838dee251f86b489b4.png
[https_blog.51cto.com_u_15102959_2634084]: https://blog.51cto.com/u_15102959/2634084