1. InnoDB中Page结构

在InnoDB中，Page是整个InnoDB存储的最基本构件，也是InnoDB磁盘管理的最小单位，与数据库相关的所有内容都存储在这种Page结构里，默认大小为16K。以下是page头结构

page头结构

Previous Page ：前向页指针

Next Page ：后向页指针

Page Number ：当前页号

Page Type ： 页类型（数据页、Undo页、系统页、事务数据页）

以下是Page主体结构

Page主体结构

在page中，数据和索引存储在User Records中，User Records由一条一条的Record组成，每条记录代表索引树上的一个节点（非叶子节点和叶子节点），User Record有四种类型：

1）主键索引树非叶节点 

2）主键索引树叶子节点 

3）辅助键索引树非叶节点 

4）辅助键索引树叶子节点

它们都有一个Next指针指向下一个页，这些页在逻辑上有序，物理上可以无序。

2. 有序索引是如何构建的？

按如下逻辑构造一个辅助索引

CREATE TABLE t1 (a INT PRIMARY KEY, b INT, c BLOB);

INSERT INTO t1 VALUES (1, 11, 'hello111');

INSERT INTO t1 VALUES (2, 22, 'hello222');

INSERT INTO t1 VALUES (3, 33, 'hello333');

INSERT INTO t1 VALUES (4, 44, 'hello444');

INSERT INTO t1 VALUES (5, 55, 'hello555');

INSERT INTO t1 VALUES (6, 66, 'hello666');

INSERT INTO t1 VALUES (7, 77, 'hello777');

INSERT INTO t1 VALUES (8, 88, 'hello888');

INSERT INTO t1 VALUES (9, 99, 'hello999');

INSERT INTO t1 VALUES (10, 1010, 'hello101010');

ALTER TABLE t1 ADD INDEX k1(b);

1）在level0创建一个page=>创建一个指针指向该page=>插入辅助索引(11,1) 2）该page未满时直接插入索引(22,2),(33,3) 3）当page满时，创建兄弟页page6=>在[当前level+1]创建父页page7，并将[当前level+1]指针指向该页，插入(11,1),5=>在page6插入(44,4) 4）最终结果

---

参考内容

MySQL InnoDB Sorted Index Builds https://www.percona.com/blog/2019/05/08/mysql-innodb-sorted-index-builds/