转:关于 Mysql 数据存储，你了解多少？
原文地址 mp.weixin.qq.com
前言
大家都知道 MySQL 的数据都是保存在磁盘的，那具体是保存在哪个文件呢？MySQL 存储的行为是由存储引擎实现的，MySQL 支持多种存储引擎，不同的存储引擎保存的文件自然也不同。InnoDB 是我们常用的存储引擎，也是 MySQL 默认的存储引擎。本文主要以 InnoDB 存储引擎展开讨论。
InnoDB 简介
InnoDB 是一个将表中的数据存储到磁盘上的存储引擎。而真正处理数据的过程是发生在内存中的，所以需要把磁盘中的数据加载到内存中，如果是处理写入或修改请求的话，还需要把内存中的内容刷新到磁盘上。而我们知道读写磁盘的速度非常慢，和内存读写差了几个数量级。所以当我们想从表中获取某些记录时，InnoDB 存储引擎需要一条一条的把记录从磁盘上读出来么？想要了解这个问题，我们首先需要了解 InnoDB 的存储结构是怎样的。
InnoDB 采取的方式是：将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位 innodb_page_size 选项指定了 MySQL 实例的所有 InnoDB 表空间的页面大小。这个值是在创建实例时设置的，之后保持不变。有效值为 64KB，32KB，16KB(默认值)，8kB 和 4kB。也就是在一般情况下，一次最少从磁盘中读取 16KB 的内容到内存中，一次最少把内存中的 16KB 内容刷新到磁盘中。
InnoDB 行格式
我们平时是以记录为单位来向表中插入数据的，这些记录在磁盘上的存放方式也被称为行格式或者记录格式。一行记录可以以不同的格式存在 InnoDB 中，行格式分别是 compact、redundant、dynamic 和 compressed 行格式。可以在创建或修改的语句中指定行格式：
mysql5.0 之前默认的行格式是 redundant，mysql5.0 之后的默认行格式为 compact ， 5.7 之后的默认行格式为 dynamic
compact 格式
记录的额外信息
记录的额外信息：分别是变长字段长度列表、NULL 值列表和记录头信息
1：变长字段长度列表
mysql 中支持一些变长数据类型（比如 VARCHAR(M)、TEXT 等），它们存储数据占用的存储空间不是固定的，而是会随着存储内容的变化而变化。在 Compact 行格式中，把所有变长字段的真实数据占用的字节长度都存放在记录的开头部位，从而形成一个变长字段长度列表，各变长字段数据占用的字节数按照列的顺序逆序存放
变长字段长度列表中只存储值为 非 NULL 的列内容占用的长度，值为 NULL 的列的长度是不储存的 。
并不是所有记录都有这个 变长字段长度列表 部分，比方说表中所有的列都不是变长的数据类型的话，这一部分就不需要有
2：NULL 值列表
NULL 值列表：Compact 格式会把所有可以为 NULL 的列统一管理起来，存在一个 NULL 值列表，如果表中没有允许为 NULL 的列，则 NULL 值列表也不复存在了。
为什么要有 NULL 值列表？
表中的某些列可能存储 NULL 值，如果把这些 NULL 值都放到记录的真实数据中存储会很浪费空间，所以 Compact 行格式把这些值为 NULL 的列统一管理起来，存储到 NULL 值列表中，它的处理过程是这样的：
首先统计表中允许存储 NULL 的列有哪些。
根据列的实际值，用 0 或者 1 填充 NULL 值列表，1 代表该列的值为空，0 代表该列的值不为空。
如果表中没有允许存储 NULL 的列，则 NULL 值列表 也不存在了。
3：记录头信息
redundant 格式
与 compact 格式相比, 没有了 变长字段列表以及 NULL 值列表, 取而代之的是 记录了所有真实数据的偏移地址表 ，偏移地址表 是倒序排放的, 但是计算偏移量却还是正序开始的从 row_id 作为第一个, 第一个从 0 开始累加字段对应的字节数。在记录头信息中, 大部分字段和 compact 中的相同，但是对比 compact 多了。
n_field(记录列的数量)、1byte_offs_flag(字段长度列表每一列占用的字节数)，少了 record_type 字段。
因为 redundant 是 mysql 5.0 以前就在使用的一种格式, 已经非常古老, 使用频率非常的低，这里就不过多表述。
dynamic 格式
在现在 mysql 5.7 的版本中, 使用的格式就是 dynamic。
dynamic 和 compact 基本是相同的，只有在溢出页的处理上面, 有所不同。
在 compact 行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的前 768 个字节的数据，把剩余的数据分散存储在几个其他的页中，然后记录的真实数据处用 20 个字节存储指向这些页的地址，从而可以找到剩余数据所在的页。
这种在本记录的真实数据处只会存储该列的前 768 个字节的数据和一个指向其他页的地址，然后把剩下的数据存放到其他页中的情况就叫做行溢出，存储超出 768 字节的那些页面也被称为溢出页（uncompresse blob page）。
dynamic 中会直接在真实数据区记录 20 字节 的溢出页地址, 而不再去额外记录一部分的数据了。
行溢出临界点
MySQL 中规定一个页中至少存放两行记录。简单理解：因为 B + 树的特性，如果不存储至少 2 条记录，则这个 B + 树是没有意义的，形不成一个有效的索引。
每个页除了存放我们的记录以外，也需要存储一些额外的信息，大概 132 个字节。
每个记录需要的额外信息是 27 字节。假设一个列中存储的数据字节数为 n，如要要保证该列不发生溢出，则需要满足：132 + 2×(27 + n) < 16384 结果是 n < 8099。也就是说如果一个列中存储的数据小于 8099 个字节，那么该列就不会成为溢出列。如果表中有多个列，那么这个值更小。
compressed 格式
compressed 格式将会在 Dynamic 的基础上面进行压缩处理特别是对溢出页的压缩处理，存储在其中的行数据会以 zlib 的算法进行压缩，因此对于 blob、text 这类大长度类型的数据能够进行非常有效的存储。但 compressed 格式其实也是以时间换空间，性能并不友好，并不推荐在常见的业务中使用。
InnoDB 数据页结构
数据页代表的这块 16KB 大小的存储空间可以被划分为多个部分，不同部分有不同的功能
每当我们插入一条记录，都会从 Free Space 部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到 User Records 部分，当 Free Space 部分的空间全部被 User Records 部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了，这个过程的图示如下：
为了方便讲述
这些记录，就如下图所示，存储在 User Rcords 里
delete_mask 这个属性标记着当前记录是否被删除。这些被删除的记录之所以不立即从磁盘上移除，是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗，所以只是打一个删除标记而已。所有被删除掉的记录都会组成一个所谓的垃圾链表，在这个链表中的记录占用的空间称之为所谓的可重用空间，之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。
min_rec_maskB + 树的每层非叶子节点中的最小记录都会添加该标记，min_rec_mask 值都是 0，意味着它们都不是 B + 树的非叶子节点中的最小记录。
n_owned 在页目录分组时使用，每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的 n_owned 属性表示该记录拥有多少条记录，也就是该组内共有几条记录。
heap_no 这个属性表示当前记录在本页中的位置，从图中可以看出来，我们插入的 4 条记录在本页中的位置分别是：2、3、4、5。heap_no 值为 0 和 1 的记录，称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录。
record_type 这个属性表示当前记录的类型，一共有 4 种类型的记录，0 表示普通记录，1 表示 B + 树非叶节点记录，2 表示最小记录，3 表示最大记录。
next_record 它表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量。比方说第一条记录的 next_record 值为 32，意味着从第一条记录的真实数据的地址处向后找 32 个字节便是下一条记录的真实数据。下一条记录指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。而且规定 Infimum 记录（也就是最小记录） 的下一条记录就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是 Supremum 记录（也就是最大记录）。
从图中可以看出来，我们的记录按照主键从小到大的顺序形成了一个单链表。
Page Directory（页目录）
现在我们了解了记录在页中按照主键值由小到大顺序串联成一个单链表，单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块，专门给记录做一个目录，通过二分查找法的方式进行检索，提升效率。
1：将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组。
2：每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的 n_owned 属性表示该记录拥有多少条记录，也就是该组内共有几条记录。
3：将每个组的最后一条记录的地址偏移量单独提取出来，用作查找。
注意：这个页目录是为主键服务的。
需要注意的是：
第一：第一个小组，也就是最小记录所在的分组只能有 1 个记录;
第二：最后一个小组，就是最大记录所在的分组，只能有 1-8 条记录;
第三：剩下的分组中记录的条数范围只能在是 4-8 条之间；
分组是按照下边的步骤进行：
初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组。
之后每插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的 n_owned 值加 1，表示本组内又添加了一条记录，直到该组中的记录数等于 8 个。
在一个组中的记录数等于 8 个后再插入一条记录时，会将组中的记录拆分成两个组，一个组中 4 条记录，另一个 5 条记录。这个过程会在页目录中新增一个槽来记录这个新增分组中最大的那条记录的偏移量。
我们再添加 8 条记录看看效果：
这里为了便于理解，图中只保留了用户记录头信息中的 n_owned 和 next_record 属性。
因为各个槽代表的记录的主键值都是从小到大排序的，所以我们可以使用二分法来进行快速查找。
所以在一个数据页中查找指定主键值的记录的过程分为两步：
通过二分法确定该记录所在的槽，并找到该槽所在分组中主键值最大的那条记录。
通过记录的 next_record 属性遍历该槽所在的组中的各个记录。
比方说我们查找主键值为 x 的记录，计算中间槽的位置 (min+max)/2 =mid, 查看 mid 槽对应的主键值 y，若 x<y, 则 min 不变，max=mid，若 x>y，则 max 不变，min=mid。依此类推。
举例：我们想找主键值为 6 的记录，过程是这样的计算中间槽的位置：(0+3)/2=1，所以查看槽 1 对应记录的主键值为 4，因为 4 < 6，所以设置 low=1，high 保持不变。因为 high - low 的值为 1，所以确定主键值为 6 的记录在槽 2 对应的组中。我们可以很轻易的拿到槽 1 对应的记录（主键值为 4），该条记录的下一条记录就是槽 2 中主键值最小的记录，该记录的主键值为 5。所以我们可以从这条主键值为 5 的记录出发，遍历槽 2 中的各条记录找到主键为 6 的数据。
注意：若查到数据在槽 2 的分组中，由于槽 2 是指向最后一个记录，所以需要向上找一个槽位，定位到上一个槽位最后一行，然后再向下找。
File Header（文件头部）
File Header 针对各种类型的页都通用，也就是说不同类型的页都会以 File Header 作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页、下一个页是谁等。
FIL_PAGE_OFFSET 每一个页都有一个单独的页号，就跟你的身份证号码一样，InnoDB 通过页号来可以唯一定位一个页。
FIL_PAGE_PREV 和 FIL_PAGE_NEXTFIL_PAGE_PREV 和 FIL_PAGE_NEXT 就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了。
B + 树索引
InnoDB 数据页的主要组成部分。各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录。再通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽。
在一个页中的查找：
以主键为搜索条件这个查找过程我们已经很熟悉了，可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
以其他列作为搜索条件对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。
在很多页中查找：
1：定位到记录所在的页。
2：从所在的页内中查找相应的记录。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们上面聊过的查找方式去查找指定的记录。
索引
同样的，我们以上面建的表 test 为例，清空插入的数据，此时 test 表为一张空数据的表，为了便于讲述，我们可以简单的把 test 表的行格式理解如下：
一个简单的索引方案：我们为根据主键值快速定位一条记录在页中的位置而设立的页目录，目录中记录的数据页需要满足下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。
假设我们的每个数据页最多能存放 3 条记录（实际上一个数据页非常大，可以存放下很多记录），这时候我们向 test 表插入三条记录，那么数据页就如图所示：
此时我们再来插入一条记录：
1 | |
因为上面定义了，一个页最多只能放 3 条记录，所以我们不得不再分配一个新页：
页 1 中用户记录最大的主键值是 4，而页 2 中有一条记录的主键值是 3，因为 4 > 3，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为 3 的记录的时候需要伴随着一次记录移动，也就是把主键值为 4 的记录移动到页 2 中，然后再把主键值为 3 的记录插入到页 1 中。最后形成如图所示。
这个过程叫做页分裂。
真实数据存储中，数据页的编号并不是连续的，当我们在 test 表中插入多条记录后，可能是这样的效果：
因为这些 16KB 的页在物理存储上可能并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项由页中记录的最小主键值和页号组成。我们为上面几个页做目录，则如图：
比方说我们想找主键值为 5 的记录，具体查找过程分两步：
1：先从目录项中根据二分法快速确定出主键值为 5 的记录在目录 2 中（因为 4 < 5 < 7），它对应的数据页是页 23。
2：再根据前边说的在页中查找记录的方式去页 23 中定位具体的记录。
这个目录有一个别名，称为索引。
InnoDB 中的索引方案
在 InnoDB 中复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。
用 record_type 来区分普通的用户记录还是目录项记录。
如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，会再多整一个存储目录项记录的页。所以如果此时我们再向上图中插入一条主键值为 10 的用户记录的话：
在查询时我们需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？其实也简单，为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：
用户记录其实都存放在 B + 树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中 B + 树最上边的那个节点也称为根节点。
聚簇索引
我们上边介绍的 B + 树本身就是一个目录，或者说本身就是一个索引。它有两个特点：
1：使用记录主键值的大小进行记录和页的排序
2：B + 树的叶子节点存储的是完整的用户记录。
我们把具有这两种特性的 B + 树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在 MySQL 语句中显式的使用 INDEX 语句去创建，InnoDB 存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在 InnoDB 存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。
二级索引
这个 B + 树与上边介绍的聚簇索引有几处不同：
使用记录 a2 列的大小进行记录和页的排序
页内的记录是按照 a2 列的大小顺序排成一个单向链表。
各个存放用户记录的页也是根据页中记录的 a2 列大小顺序排成一个双向链表。
存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的 a2 列大小顺序排成一个双向链表。
B + 树的叶子节点存储的并不是完整的用户记录，而只是 a2 列 + 主键这两个列的值。
目录项记录中不再是主键 + 页号的搭配，而变成了 a2 列 + 页号的搭配。
索引的代价
1：空间上的代价每建立一个索引都要为它建立一棵 B + 树，每一棵 B + 树的每一个节点都是一个数据页，一个页默认会占用 16KB 的存储空间。
2：时间上的代价每次对表中的数据进行增、删、改操作时，都需要去修改各个 B + 树索引。
B + 树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收等操作来维护好节点和记录的排序。
总结
通过对 InnoDB 存储逻辑分析，我们可以清楚的了解到 mysql 中是怎样对数据进行存储的。并且对索引树的结构进行分析，帮助我们在工作中更加合理的使用索引。