InnoDB如何存储数据

MySQL支持多种存储结构，我们常用的就是InnoDB，前面我们在 前面的 " MySQL 的 NULL 值是怎么存放的 " 一文中已经知道记录是按照行来存储的，数据读取并不是以行为单位进行读取的，因为这样效率非常低，InnoDB 是以数据页为单位进行读取的。

也就是说，当用户只需要读取一条记录的时候，并不是将这个记录从磁盘中读出，而是以页为单位，将记录所在的页整体读入内存。

InnoDB 数据页默认大小是16KB。

数据页结构分为7个部分，如下图：

数据页7个部分作用说明

File header

在 File Header 中有两个指针，分别指向上一个数据页和下一个数据页，连接起来的页相当于一个双向的链表，如下图所示：

采用链表的结构是让数据页之间不需要是物理上的连续的，而是逻辑上的连续。

记录在页中的存储

数据页的主要作用是存储记录，也就是数据库的数据，所以重点说一下数据页中的 User Records 是怎么组织数据的。

用户插入数据的时候，记录会按照行格式存储到 User records 部分，在一开始的时候，没有这一部分，每当插入一条记录的时候，都会从Free space 部分划分到 User records 。

当 Free space 这部分的空间完全 被 User records这部分替换之后，也就代表着这个数据页用完了。

过程如下：

数据页中的记录按照 主键 顺序组成单向链表，单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。InnoDB是这样的吗？ 答案：肯定不是啊！

page Directory(页目录)

我们平时在查找一本书中的某个内容的时候，会怎么做呢？一般会先去看目录，找到对应的页码，然后就可以去对应的页码页看内容了。InnoDB也实现了类似这样一个目录。

目录创建过程如下

1. 将所有正常的记录(包括 Infimum Supremum 记录，但不包括已经移除到垃圾链表的记录)划分为几个组.

2. 每个组的最后一条记录(也就是组内最大的那条记录)相当于"带头大哥"组内其余的记录相当于"小弟。带头大哥"记录的头信息中的 owned 属性表示该组内共有几条记录

3. 将每个组中最后一条记录在页面中的地址偏移量(就是该记录的真实数据与页面中个字节之间的距离〉单独提取出来，按顺序存储到靠近页尾部的地方，这个地方就是 Page Directory 。页目录中的这些地址偏移量称为槽 (Slot) ，每个槽占用 2 个字节，页目录就是由多个槽组成的。

举个例子

如下图5 个槽的编号分别为 0，1，2，3，4，我想查找主键为 11 的用户记录：

• 先二分得出槽中间位是 (0+4)/2=2 ，2号槽里最大的记录为 8。因为 11 > 8，所以需要从 2 号槽后继续搜索记录；
• 再使用二分搜索出 2 号和 4 槽的中间位是 (2+4)/2= 3，3 号槽里最大的记录为 12。因为 11 < 12，所以主键为 11 的记录在 3 号槽里；
• 这里有个问题，「槽对应的值都是这个组的主键最大的记录，如何找到组里最小的记录」？比如槽 3 对应最大主键是 12 的记录，那如何找到最小记录 9。解决办法是：通过槽 3 找到 槽 2 对应的记录，也就是主键为 8 的记录。主键为 8 的记录的下一条记录就是槽 3 当中主键最小的 9 记录，然后开始向下搜索 2 次，定位到主键为 11 的记录，取出该条记录的信息即为我们想要查找的内容。

看到第三步的时候，可能有的同学会疑问，如果某个槽内的记录很多，然后因为记录都是单向链表串起来的，那这样在槽内查找某个记录的时间复杂度不就是 O(n) 了吗？

这点不用担心，InnoDB 对每个分组中的记录条数都是有规定的，槽内的记录就只有几条：

• 第一个分组中的记录只能有 1 条记录；
• 最后一个分组中的记录条数范围只能在 1-8 条之间；
• 剩下的分组中记录条数范围只能在 4-8 条之间。

从图可以看到，页目录就是由多个槽组成的，槽相当于分组记录的索引。然后，因为记录是按照「主键值」从小到大排序的，所以我们通过槽查找记录时，可以使用二分法快速定位要查询的记录在哪个槽（哪个记录分组），定位到槽后，再遍历槽内的所有记录，找到对应的记录，无需从最小记录开始遍历整个页中的记录链表。

B+ 树是如何进行查询

上面都是在说一个数据页中的记录检索，因为一个数据页中的记录是有限的，且主键值是有序的，所以通过对所有记录进行分组，然后将组号（槽号）存储到页目录，使其起到索引作用，通过二分查找的方法快速检索到记录在哪个分组，来降低检索的时间复杂度。

当我们需要存储大量的记录时，就需要多个数据页，这时我们就需要考虑如何建立合适的索引，才能方便定位记录所在的页。

为了解决这个问题，InnoDB 采用了 B+ 树作为索引。磁盘的 I/O 操作次数对索引的使用效率至关重要，因此在构造索引的时候，我们更倾向于采用“矮胖”的 B+ 树数据结构，这样所需要进行的磁盘 I/O 次数更少，而且 B+ 树 更适合进行关键字的范围查询。

InnoDB 里的 B+ 树中的每个节点都是一个数据页，结构示意图如下：

通过上图，我们看出 B+ 树的特点：

• 只有叶子节点（最底层的节点）才存放了数据，非叶子节点（其他上层节）仅用来存放目录项作为索引。
• 非叶子节点分为不同层次，通过分层来降低每一层的搜索量；
• 所有节点按照索引键大小排序，构成一个双向链表，便于范围查询；

我们再看看 B+ 树如何实现快速查找主键为 6 的记录，以上图为例子：

• 从根节点开始，通过二分法快速定位到符合页内范围包含查询值的页，因为查询的主键值为 6，在[1, 7)范围之间，所以到页 30 中查找更详细的目录项；
• 在非叶子节点（页30）中，继续通过二分法快速定位到符合页内范围包含查询值的页，主键值大于 5，所以就到叶子节点（页16）查找记录；
• 接着，在叶子节点（页16）中，通过槽查找记录时，使用二分法快速定位要查询的记录在哪个槽（哪个记录分组），定位到槽后，再遍历槽内的所有记录，找到主键为 6 的记录。

可以看到，在定位记录所在哪一个页时，也是通过二分法快速定位到包含该记录的页。定位到该页后，又会在该页内进行二分法快速定位记录所在的分组（槽号），最后在分组内进行遍历查找。

总结

• InnoDB 的数据是按「数据页」为单位来读写的，默认数据页大小为 16 KB。每个数据页之间通过双向链表的形式组织起来，物理上不连续，但是逻辑上连续。
• 数据页内包含用户记录，每个记录之间用单向链表的方式组织起来，为了加快在数据页内高效查询记录，设计了一个页目录，页目录存储各个槽（分组），且主键值是有序的，于是可以通过二分查找法的方式进行检索从而提高效率。
• 为了高效查询记录所在的数据页，InnoDB 采用 b+ 树作为索引，每个节点都是一个数据页。