1.磁盘数据页存储结构

MySQL数据最终都会存储到磁盘文件中，在文件存放的物理格式就是数据页，相邻的数据页会采用双向链表的格式相互引用。
数据页内部会存储一行一行的数据，每一行数据会按照主键大小进行排序存储，每一行数据都有指针指向下一行数据的位置。
每个数据页里都会有一个页目录，里面根据数据行的主键存放一个目录，同时数据行被分散存储到不同的槽位。之后每当插入一条记录时，都会从页目录中找到对应记录的主键值比待插入记录的主键值大，并且差值最小的槽，然后把该槽对应的n_owned加1。
页目录理解：https://blog.csdn.net/li1325169021/article/details/121044671

如果根据主键查询一条数据，会先到数据页的页目录里根据主键进行二分查找，找到主键对应的数据槽位，遍历槽位中的每一行数据，直到找到主键对应的数据。
如果不使用主键进行查找，那么只能进入到数据页，根据单项链表依次遍历查询。
如果数据量非常大的情况下，可能会遍历所有数据页才能找到需要的数据。

2.页分裂

mysql中插入一些数据的时候，会进入到一个数据页中，在数据页内部，会组成一个单向链表。

数据页里就是一行一行的数据，第一行是起始行，行类型是2，也就是最小的一行。每一行数据都有自己每个字段的值，每一行通过指针不停的指向下一行数据。普通的数据行的类型都是0，最后一行的类型为3，代表最大的一行。
如果不停的往表里插入数据，当一个数据页容量满了后，就会再创建一个数据页，如下图。

此时就会碰到一个问题，索引运行的一个核心机制就是后一个数据页的主键值都大于前面一个数据页的主键值，如果主键是自增的，还可以保证这一点，因为新插入数据页的主键一定大于前一个数据页的主键值。
如果主键不是自增的，就会出现页分裂。

如上图所示，第一个数据页有1、5、6三条数据，第二个数据页有2、3、4三条数据，第二个数据页里的数据的主键值存在比第一个数据页中数据小的情况，这是不允许的。
此时会出现页分裂的行为，把新数据里的两条数据挪到上一个数据页，上一个数据页里挪两条到新的数据页（同一个数据页每行数据也是按大小进行排序），如下图。

页分裂，核心目标就是保证下一个数据页里的主键值都比上一个数据页里的主键值要大。

3.基于主键的索引是如何设计的

针对主键的索引就是主键目录。这个主键目录会把每个数据页的页号，还有数据页中最小的主键值放到一起，组成一个索引的目录。

有了主键目录后，如果要查找id=3的数据，此时就会跟每个数据页的最小主键进行比较，首先id=3大于了数据页2里的最小主键值1，接着小于了数据页5里的最小主键值4，那就直接可以定位到id=3的数据一定在数据页2里。
当数据页有很多的时候，在主键目录里就会有很多的数据页和最小主键值，此时完全可以根据二分查找的方式来找id对应的数据页。

4.B+树存储结构

主键索引的目录结构，只要在一个主键索引里包含每个数据页跟他最小主键值，就可以组成一个索引目录，后续查询主键值，就可以在目录里二分查找直接定位到查询主键对应的数据页，接着再到数据页二分查找那条数据。
但是，如果表里的数据有很多，比如几百万、几千万以上，此时就会有大量的数据页，主键目录里也要存储大量的数据页和最小主键值。
这时候，就会采取一种把索引数据存储在数据页里的方式。表的实际数据是放在数据页里，表的索引也是放在页里（索引页）。假设现在有很多数据页，那么也会有很多索引页，如下图所示。

但现在就会有一个问题，目前有很多索引页，如果要根据主键查询数据，要到哪个索引页去找主键数据？
接下来就需要把索引页都加一个层级出来，在更高的索引层级里，保存每个索引页和索引页里的最小主键值。

如果现在要查找id=3的数据，会现在到顶层的索引页30里查找，然后通过二分查找定位到下一步要到索引号20里找，接下来再通过二分查找定位到数据在数据页2里，再进入数据页2查找，就可以找到id=3的那行数据了。
假如最顶层的索引页里存放的下层索引也太多了，此时还可以再次分裂，再加一层索引页，如下图。

这就是形成了B+树。当为一个表的主键建立索引之后，这个主键索引就是一颗B+树，根据主键查询数据的时候，就是从B+树的顶层开始二分查找，一层一层往下定位，最终定位到一个数据页里。再到数据页内部进行二分查找，找到数据。

5.聚簇索引

在最下层的索引页中，都会有指针引用对应的数据页，并且在索引页内部，最下层索引页相互之间都是基于双向链表的。

B+树里，最底层的就是数据页，数据页也就是B+树里的叶子节点。
B+树索引数据结构里，叶子节点就是数据页本身，就称这颗B+树索引为聚簇索引。
聚簇索引默认是按照主键来组织的，在执行增删改查数据的时候，一方面会更新数据页，一方面会自动维护B+树的聚簇索引。