MySQL存储相关详解
说明
本人在MySQL锁方面的知识总是理解不深刻面试也总是答的不如意，了解MySQL存储结构对于锁的认识和理解一定会有一个质的飞跃，本文也是根据小林的《图解MySQL》中取得经，自己写一些东西方便看
InnoDB是MySQL的默认存储引擎也是最常使用的存储引擎，所以就以InnoDB展开
MySQL数据存放在什么文件
欸创建一个 database（数据库） 都会在 /var/lib/mysql/目录下创建一个以database为名的目录，然后保存它的表结构和表数据。例如现在有一个名为my_test的数据库有表t_order，那么在/var/lib/mysql/my_test/目录下有文件db.opt，t_order.frm，t_order.ibd
db.opt，用来存储当前数据库的默认字符集和字符校验规则。t_order.frm，t_order 的表结构会保存在这个文件。在 MySQL 中建立一张表都会生成一个,frm 文件，该文件是来保存每个表的元数据信息的，主要包含表结构定义。t_order.ibd，t_order 的表数据会保存在这个文件。表数据既可以存在共享表空间文件(文件名:ibdata1)里也可以存放在独占表空间文件(文件名:表名字.ibd)。这个行为是由参数 innodb_file_per_table 控制的，若设置了参数innodb_fle_per_table为 1，则会将存储的数据、索引等信息单独存储在一个独占表空间，从 MySQ5.6.6 版本开始默认值就是1了，因此从这个版本之后， MySQL 中每一张表的数据都存放在一个独立的.ibd 文件。
表空间文件的结构如何
表空间由段、区、页、行组成
1、行(row)
数据库表中的记录都是按行(row)进行存放的，每行记录根据不同的行格式，有不同的存储结构。
2、页(page)
记录是按照行来存储的，但是数据库的读取并不以「行」为单位，否则一次读取(也就是一次 I/0 操作)只能处理行数据，效率会非常低。因此，InnoD8 的数据是按「页」为单位来读写的，也就是说，当需要读一条记录的时候，并不是将这个行记录从磁盘读出来，而是以页为单位，将其整体读入内存。
默认每个页的大小为 16KB，也就是最多能保证 16KB 的连续存储空间。页是 InnoD8 存储引擎磁盘管理的最小单元，意味着数据库每次读写都是以 16KB 为单位的，一次最少从磁盘中读取16K 的内容到内存中，一次最少把内存中的 16K 内容刷新到磁盘中。
页的类型有很多，常见的有数据页、undo 日志页、溢出页等等。数据表中的行记录是用「数据页」来管理的
3、区(extent)
InnoDB 存储引擎是用 B+ 树来组织数据的。B+树中每一层都是通过双向链表连接起来的，如果是以页为单位来分配存储空间，那么链表中相邻的两个页之间的物理位置并不是连续的，可能离得非常远，那么磁盘查询时就会有大量的随机I/O，随机I/O 是非常慢的。解决这个问题也很简单，就是让链表中相邻的页的物理位置也相邻，这样就可以使用顺序 I/O 了，那么在范围查询(扫描叶子节点)的时候性能就会很高。
在表中数据量大的时候，为某个索引分配空间的时候就不再按照页为单位分配了，而是按照区(extent)为单位分配。每个区的大小为 1MB，对于 16KB 的页来说，连续的 64 个页会被划为一个区，这样就使得链表中相邻的页的物理位置也相邻，就能使用顺序 I/O 了
4、段(segment)
表空间是由各个段(segment)组成的，段是由多个区(extent)组成的。段一般分为数据段、索引段和回滚段等。
索引段:存放B+树的非叶子节点的区的集合
数据段:存放 B+树的叶子节点的区的集合;
回滚段:存放的是回滚数据的区的集合，例如MVCC 利用了回滚段实现了多版本查询数据。
InnoDB数据行格式（Compact格式）
记录的额外信息
记录的额外信息包含3个部分:变长字段长度列表、NULL 值列表、记录头信息
变长字段长度列表
varchar(n) 和 char(n) 的区别是char 是定长的，varchar 是变长的，变长字段实际存储的数据的长度(大小)不固定的。所以在存储数据的时候，也要把数据占用的大小存到「变长字段长度列表」里，读取数据的时候根据「变长字段长度列表」读取对应长度的数据。其他 TEXT、BLOB 等变长字段也是这么实现的。
为了展示「变长字段长度列表」具体是怎么保存「变长字段的真实数据占用的字节数」，先创建一张表字符集是 ascii(每个字符占用1字节)，行格式是 Compact，t_user表中 name 和 phone 字段都是变长字段
| id | name | phone | age |
|---|---|---|---|
| 1 | a | 123 | 18 |
| 2 | bb | 1234 | (NULL) |
| 3 | ccc | (NULL) | (NULL) |
以第一条记录为例，name的值是a，真实数据占用1字节（0x01）；phone的值是123，真实数据占用3字节（0x03）；age和id不是边长字段不需要管。
这些变长字段的真实数据占用的字节数会按照列的顺序逆序存放，所以「变长字段长度列表」里的内容是「03 01」；然而，NULL值不会存放在行格式中记录的真实数据部分。第二行数据是「04 02」，第三行是「03（phone不存）」
变长字段字节数列表不是必须的。当数据表没有变长字段的时候，这时候表里的行格式就不会有「变长字段长度列表」了，因为没必要，不如去掉以节省空间。所以「变长字段长度列表」只出现在数据表有变长字段的时候。
「变长字段列表」占用的总字节数是多少
公式：「变长字段列表」占用字节数 = 所有的「变长字段长度」占用字节数之和
每个变长字段的「变长字段长度」需要用多少字节表示?具体情况分为：
条件一：如果变长字段允许存储的最大字节数小于等于 255 字节，就会用 1 字节表示「变长字段长度」
条件二：如果变长字段允许存储的最大字节数大于 255 字节，就会用 2 字节表示「变长字段长度」
NULL 值列表
表中的某些列可能会存储 NULL 值，但如果把这些 NULL 值都放到记录的真实数据中浪费空间，所以 Compact行格式把这些值为 NULL 的列存储到 NULL值列表中。
如果存在允许 NULL 值的列，则每个列对应一个二进制位(bit)，二进制位按照列的顺序逆序排列。二进制位的值为 1 时，代表该列的值为NULL。二进制位的值为 0 时，代表该列的值不为NULL。另外，NULL值列表必须用整数个字节的位表示(1字节8位)，如果使用的二进制位个数不足整数个字节，则在字节的高位补 0。
仍然用上面的三行数据举例，第三行数据的phone和age都是NULL，所以对应的值是0x06
数据库表的行格式也不一定都有「NULL值列表」
当数据表的字段都定义成 NOT NULL 的时候，这时候表里的行格式就不会有 NULL 值列表了所以在设计数据库表的时候，通常都是建议将字段设置为 NOT NULL，这样可以至少节省1字节的空间(NULL 值列表至少占用1字节空间)。
[NULL 值列表」是固定1字节空间吗?如果这样的话，一条记录有9个字段值都是 NULL，这时候怎么表示?
[NULL 值列表」的空间不是固定1字节的。当一条记录有9个字段值都是 NULL，那么就会创建 2 字节空间的[NULL 值列表」，以此类推。
记录头信息（只展示部分）
delete_mask：标识此条数据是否被删除。执行 detele 删除记录的时候并不会真正的删除记录，只是将这个记录的 delete_mask 标记为 1。
next_record：下一条记录的位置。记录与记录之间是通过链表组织的，指向的是下一条记录的「记录头信息」和「真实数据」之间的位置，这样的好处是向左读就是记录头信息，向右读就是真实数据，比较方便。
这里形象一些：指针就是指向下图中「记录的额外信息」和「记录的真实数据」中间的那条，上面的「变长字段列表」和「NULL值列表」存数据的时候都是按照字段原顺序的逆序存储，因此指针向左读取的时候，依次读取的其实正好就是字段的原顺序。
record_type：表示当前记录的类型，0表示普通记录，1表示B+树非叶子节点记录，2表示最小记录，3表示最大记录
记录的真实数据
row id：如果建表时指定了主键或者唯一约束列，那么就没有 row_id 隐藏字段了；如果既没有指定主键又没有唯一约束，那么 InnoDB 就会为记录添加 row_id 隐藏字段。row_id不是必需的，占用6个字节。
trx_id：事务id，表示这个数据是由哪个事务生成的。 trx_id是必需的，占用6个字节。（MVCC）
roll_pointer：这条记录上一个版本的指针。roll_pointer 是必需的，占用7个字节。（MVCC）
行溢出后MySQL如何处理
MySQL 中磁盘和内存交互的基本单位是页，一个页的大小一般是16K8，也就是 16384字节，而一个varchar(n)类型的列最多可以存储 65532字节，一些大对象如 TEXT、BLOB 可能存储更多的数据，这时一个页可能存不了一条记录。此时就会发生行溢出，多的数据就会存到另外的「溢出页」中。
如果一个数据页存不了一条记录，InnoD8 存储引擎会自动将溢出的数据存放到「溢出页」中。在一般情况下,InnoDB 的数据都是存放在「数据页」中。但是当发生行溢出时，溢出的数据会存放到「溢出页」中。当发生行溢出时，在记录的真实数据处只会保存该列的一部分数据，而把剩余的数据放在「溢出页」中，然后真实数据处用 20 字节存储指向溢出页的地址，从而可以找到剩余数据所在的页。
B+ Tree是如何进行查询的
首先了解B树🌳的简单知识：B树沿用了AVL树（平衡二叉树）的设计思想，即小于的在左大于的在右，但是又解决了二叉树每个节点最多有两个子节点的缺陷，所以B树是一个多叉树。一个M阶的B树表示某一个节点最多包含M - 1个KEY和M个子节点（一个节点最多可以包含M个子节点，M称为B树的阶）。主要是用B树的结构比起平衡二叉树能有更低的层数（对应于大大减少磁盘的I/O操作次数）。
为了方便定位记录所在的页，InnoDB 采用了 B+ 树作为索引。磁盘的 I/O 操作次数对索引的使用效率至关重要，更倾向于采用“矮胖"的 B+ 树数据结构，这样所需要进行的磁盘 I/O 次数更少，而且 B+ 树 更适合进行关键字的范围查询。
InnoDB 里的 B+ 树中的每个节点都是一个数据页，结构示意图如下:
通过上图，总结 B+树的特点:
- 只有叶子节点(最底层的节点)才存放了数据，非叶子节点(其他上层节)仅用来存放目录项作为索引。
- 非叶子节点分为不同层次，通过分层来降低每一层的搜索量;
- 所有节点按照索引键大小排序，构成一个双向链表，便于范围查询;
B+ 树如何实现快速査找主键为 6 的记录，以上图为例子:
从根节点开始，通过二分法快速定位到符合页内范围包含查询值的页，因为查询的主键值为6，在[1,7)范围之间，所以到页 30 中查找更详细的目录项。
在非叶子节点(页30)中，继续通过二分法快速定位到符合页内范围包含查询值的页，主键值大于5，所以就到叶子节点(页16)查找记录
接着，在叶子节点(页16)中，通过槽査找记录时，使用二分法快速定位要查询的记录在哪个槽(哪个记录分组)，定位到槽后，再遍历槽内的所有记录，找到主键为6的记录。
可以看到，在定位记录所在哪一个页时，也是通过二分法快速定位到包含该记录的页。定位到该页后，又会在该页内进行二分法快速定位记录所在的分组(槽号)，最后在分组内进行遍历查找。
因此，如果某个查询语句使用了二级索引，但是查询的数据不是主键值，这时在二级索引找到主键值后，需要去聚簇索引中获得数据行，这个过程就叫作「回表」，也就是说要查两个 B+ 树才能查到数据。不过，当查询的数据是主键值时，因为只在二级索引就能查询到，不用再去聚簇索引查，这个过程就叫作「索引覆盖」，也就是只需要查一个 B+ 树就能找到数据。
总结
InnoDB 的数据是按**「数据页」**为单位来读写的，默认数据页大小为 16 KB。每个数据页之间通过双向链表的形式组织起来，物理上不连续，但是逻辑上连续。
数据页内包含用户记录，每个记录之间用单向链表的方式组织起来，为了加快在数据页内高效查询记录，设计了一个页目录，页目录存储各个槽(分组)，且主键值是有序的，于是可以通过二分查找法的方式进行检索从而提高效率。
为了高效查询记录所在的数据页，InnoDB 采用 b+ 树作为索引，每个节点都是一个数据页。
如果叶子节点存储的是实际数据的就是聚簇索引，一个表只能有一个聚簇索引；如果叶子节点存储的不是实际数据，而是主键值则就是二级索引，一个表中可以有多个二级索引。
在使用二级索引进行查找数据时，如果查询的数据能在二级索引找到，那么就是「索引覆盖」操作，如果查询的数据不在二级索引里，就需要先在二级索引找到主键值，需要去聚簇索引中获得数据行，这个过程就叫作「回表」。