1 数据页(B-tree Node)
Mysql数据库中的表在磁盘当中是通过一页页的数据页进行存储的。数据页是磁盘与内存交互的基本单位，Mysql的Innodb存储引擎通过buffer pool与磁盘中的数据页进行交互，每次读取一整页，buffer pool中的数据页是在内存中的动态存储方式，磁盘中的数据页是静态的。严格来讲，InnoDB的页有很多种，数据页(又称索引页)、Undo页、Inode页、系统、BloB页等，一共有10多种。数据页的默认大小为16kb，结构如下：
1.1 文件头
| 结构 | 解释 | 作用 |
|---|---|---|
FIL_PAGE_SPACE_OR_CHKSUM |
校验值 | 占用4个字节，主要用来存储数据页的checksum(校验值)。 |
FIL_PAGE_OFFSET |
页偏移量 | 数据页的page number（页号），每个表空间从0开始，即这个值乘以数据页的大小就可以得到数据页在文件中的起始偏移量。 |
FIL_PAGE_PREV |
上一页 | 指针，指向前一个数据页 |
FIL_PAGE_NEXT |
下一页 | 指针，指向后一个数据页 |
FIL_PAGE_LSN |
LSN | 代表页面被最后修改时对应的日志序列位置。这个字段非常重要，InnoDB redolog幂等的特性就依赖此字段。在奔溃恢复应用日志阶段，如果发现redolog的lsn小于等于这个值，就不需要再次应用redolog了。 |
| …… |
文件头保存了当前数据页的页号，InnoDB 通过页号来唯一定位一个页；数据页上一页、下一页是两个指针，连接起来的数据页就是一个双向链表；
1.2 页头
数据页相关的元信息：
| 结构 | 解释 | 作用 |
|---|---|---|
| …… | ||
PAGE_N_DIR_SLOTS |
记录个数 | 一个新建的空数据页，就有2条记录，分别指向最小记录和最大记录。在一个非空的数据页中，第一个目录永远指向最小记录，最后一个目录永远指向最大记录。当增加目录的时候，会递增这个值。 |
PAGE_N_HEAP |
记录数量 | 目前已经被使用空间中的记录数量，包括正常的记录和已经被删除(放入PAGE_FREE中)的记录。从代码逻辑看，这个值是不会减少的，每次都空闲空间记录的时候就会增加。在创建新的空页时候，默认被置为2，即最大和最小记录。此外，最高位被用来标记这个数据页是否存了新格式的记录(compact和redundant)。 |
PAGE_LAST_INSERT |
指针 | 指向最近一个被插入的记录的。主要用来加速后续插入操作。 |
PAGE_DIRECTION |
方向 | 最后一个记录插入的方向，目前就两个方向，从左边插入和从右边插入。也是用来加速后续插入操作。 |
PAGE_N_RECS |
用户记录数量 | 当前数据页中用户的记录，不包括最大和最小记录。与PAGE_N_HEAP不同，如果记录被标记为delete-marked，这个值就会递减。 |
| …… |
1.3 最小记录、最大记录
这部分存储的是固定的两条记录，与用户记录不同的是，在实际数据存储区域固定保存”Infimum”、”Supremun”，最小记录连接用户数据的最小记录，用户数据的最大记录连接着最大记录；他们在数据页被创建的时候创建，而且不能被删除。引入他们主要是方便页内操作；具体结构可以结合数据行 一起来看；
1.4 数据行
这里就是存储用户数据的地方。每个记录都有指向下一个记录的指针next_record；结合上面的最小记录和最大记录，整体形成一个单向链表；
1.5 空闲区域
从数据页结构可知，每次进行数据插入时数据行区域变大，相应的的空闲区域就会减少。当空闲区域消耗完，就会发生页分裂，形成新的数据页。这里需要注意的是，如果我们使用的是Mysql中的自增主键，那么可以保证按照id的增长顺序进行数据行排列，但是如果主键是我们自己设置的并不是自增长的，那么有可能出现后面插入的数据的主键值小于前面数据的主键值，那么在进行页分裂的时候，会按照主键大小重新进行排列。大致的过程如下图所示：
1.6 数据页目录
页目录的作用实际上是用来进行数据行定位的，存放的是一个个的槽（Slot），每个槽把记录进行分组，槽相当于分组记录的索引；
- 每个槽指向了不同的记录，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录，于是分组就行成了；
- 第1组，也就是
最小记录所在的分组只有 1 个记录；最后一组，就是最大记录所在的分组，会有 1-8 条记录； - 其余的组记录数量在 4-8 条之间；
- 每个槽指向了组内的最大记录；
查询数据的时候，InnoDB就会利用二叉查找迅速确定记录所在的槽，并找到该槽所在分组中主键值最小的那条记录，再通过最小记录的 next_record遍历记录，就能快速定位到匹配的那条记录了。下面一张图对数据页举个例子，假设数据是id+1自增的，想查id为 10 的用户记录：
- 槽id为 [0-3]，采用二分查找法进行查找，首先找到槽的中间位置 p=(low+high)/2=(0+3)/2=1，编号为1的槽指向用户记录id=5，5<10，所以下一步查找的槽编号为(1，3]；
- p’=(p+high)/2=(1+3)/2=2，编号为2的槽指向用户记录id=13，10<13，记录就在槽id=2的分组(分组3)中，遍历6-13找到10这条用户记录，查找结束。
1.7 文件尾
前面介绍 文件头 时说过，在将页写入磁盘时，最先写入的便是 FIL_PAGE_SPACE_OR_CHKSUM 值，就是页的校验和。在写入的过程中，数据库可能发生宕机，导致页没有完整的写入磁盘。
为了校验页是否完整写入磁盘，InnoDB 就设置了 文件尾 部分，其中只有一个FIL_PAGE_END_LSN，占用8字节。FIL_PAGE_END_LSN 又分为两个部分，前4字节代表页的校验和；后4字节代表页面被最后修改时对应的日志序列位置（LSN），与文件头中的FIL_PAGE_LSN相同。
默认情况下，InnoDB每次从磁盘读取一个页就会检测该页的完整性，这时就会将 文件尾 中的校验和、LSN 与 File Header 中的 FIL_PAGE_SPACE_OR_CHKSUM、FIL_PAGE_LSN 进行比较，以此来保证页的完整性。
2 索引原理分析
2.1 主键索引
Mysql通过主键目录(主键索引)，实现数据的查询优化。在主键目录中包含了两个重要元素:
- 数据页中最小的主键;
- 数据页的页号;
这样可以通过这个主键目录方便的进行数据查询。例如，如果想要查询主键id=5的数据，那么首先在主键目录中进行查找，此时发现主键id=5大于主键id=1，但是又小于id=8，那么就可以确定数据是在页号为1的数据页中。
Mysql将索引数据存储在索引页中，在这些索引页的上层又通过主键与索引页号来继续进行索引页的查询定位，因此我们得到如下的结构。其中的id号指的是索引页中记录id号最小的。
2.2 B+树
B+树的一个页内必须存储2行记录，否则就不是B+tree，而是链表了。这样的数据页也就形成了不同的层级：索引页层、索引页、数据页。下图就是索引的B+树结构，通过它完成数据查询效率远高于全表扫描。B+树的叶子节点才会存储数据，下图主键索引，也叫聚簇索引，它的根本思想就是分而治之的思想。
2.3 B+树中的查询过程
如当前需要查询id为3的数据，那么将在索引页中判断应该走索引页为3的索引页。那么在索引页为3中继续判断id=1应该走索引页为1的索引页，在索引页中判断应该页号为1的数据页，在此数据页中遍历最终查询到对应的数据。
2.4 二级索引
以上通过索引页与数据页组成的B+树就是聚簇索引，当然我们也可以通过其他字段来建立二级索引。二级索引会的叶子节点存储的是对应的主键id，而不是具体的数据。二级索引会存在回表的问题，即查询到对应的id之后，还需要根据id继续到聚簇索引中查询具体的数据，通过这样的操作才能查询到select *的所有数据，可以通过覆盖索引的方式避免这样的查询浪费。