MYSQL-INNODB索引构成详解

对于MYSQL的INNODB存储引擎的索引，大家是不陌生的，都能想到是 B+树结构，可以加速SQL查询。但对于B+树索引，它到底“长”得什么样子，它具体如何由一个个字节构成的，这些的基础知识鲜有人深究。本篇文章从MYSQL行记录开始说起，层层递进，包括数据页，B+树聚簇索引，B+树二级索引，最后在文章末尾给出MYSQL索引的建议。

2、一条记录存储格式：COMPACT行记录结构

mysql是关系型数据库，每一行记录都是表结构定义的关系的显示表达。在脑中很直观地想到，记录存储时也可能按行存储。

有一个概念可能大家不熟悉，是【变长字段】。mysql数据库类型中的 VARCHAR(M), VARBINARY(M), 各种TEXT，BLOB类型，这些类型的数据长度是可变的，称数据类型为可变长类型的列为变长字段。

另外，mysql会默认为行记录添加一些列（隐藏列）。上图补充这些隐藏列之后，完整行记录的结构如：

• DB_ROW_ID: 唯一标识一条记录，在表中未设置主键或未有不允许为NULL的UNIQUE键时，则MYSQL新增该隐藏列作为主键

• DB_TRX_ID: 事务ID

• DB_ROLL_PTR: 回滚指针

下面再详细的铺开，关于记录的额外信息的具体内容：

create table record_format_demo(c1 varchar(10),c2 varchar(10) not null,c3 char(10),c4 varchar(10)) charset=ascii row_format=compact
insert into record_format_demo(c1, c2, c3, c4) values("aaaa", "bbb", "cc", "d"),("eeee", "fff", NULL, NULL);

分析这两行数据的存储记录。

第一行记录：

第二行记录：

应该会注意到，变长字段长度列表 与 NULL值列表都是逆序存放的。

原因是：这样可以使得记录中位置靠前的字段和它们对应的字段长度信息在内存中的距离更近，可能会提高高速缓存的命中率。

3、盛放记录的盒子：数据页

为了更清楚的理解数据页结构以及下文中的索引，更换一个带主键的表。

CREATE TABLE page_demo(c1 INT,c2 INT,c3 VARCHAR(10000),PRIMARY KEY (c1)) CHARSET=ascii ROW_FORMAT=Compact;
INSERT INTO page_demo VALUES(1, 100, 'aaaa'),(2, 200, 'bbbb'),(3, 300, 'cccc'),(4, 400, 'dddd');

根据行记录结构中的next_recrod属性的含义，多条行记录是以单向链表的形式存储。mysql为了后续更好的查询，单向链表上的记录是按照主键顺序排列的。上述这四条记录，可以显示的画成：

假如删除其中c1=2这条数据，则单向链表变更如下。

其中变化点为 c1=2 这条数据中，deleted_flag变更成0，next_record=0，但并没有从磁盘上直接清除掉，head_no也未清除。第一条记录的next_record 指向了第三条记录。

当我们查询数据时，如果数据以行记录的形式一条一条从磁盘加载到内存中，那么因为IO过多的原因，整体性能肯定较为低效。

因此mysql规定，磁盘与内存交换数据的基本单位是一个页大小。这个页大小默认是16K。

根据页中存储的数据类型不同，页也分成许多类型。对于存储行记录的页，称为索引页（Index Page），也称为数据页。

那么接下来我们看看，数据页的结构如何，以及一条条行记录如何存放在数据页中，先上个图：

从上图中，我们可以猜到，数据页总共分成7个模块，目前咱们只关心 User Records 部分，它存储的就是用户真实的行记录。 

但是一个数据页的空间总共是16K，不会自动增大空间，随着User Records 模块中的行记录越来越多，那么肯定有其他模块的空间就越来越小。这个模块是 Free Space，是页中尚未使用的空间。更新一下上面这个图，补充 Free Space的内容。随着User Records中行记录的增加，Free Space空间则越来越小。

在一个数据页中，除了真实的行记录之外，还有两条固定的伪记录。

其中一条记录称为 infimum 【[ɪnˈfaɪməm] ，下确界】行记录，规定是数据页中记录的最小值。 

infimum记录特别简单，仅包含了 记录头信息(5字节) + 真实记录数据(8字节)，其中【69 6E 66 69 6D 75 6D 00】16进制转换成对应的单词，就是【infimum】。

另外一条记录称为 supremum【[sə'priməm]，上确界】行记录，规定是数据页中记录的最大值。 

supremum记录同样特别简单，仅包含了记录头信息(5字节) + 真实记录数据(8字节)，其中【73 75 70 72 65 6D 75 6D】16进制转换成对应的单词，就是【supremum】。

再更新一版数据库页结构， 补充上infimum 与 supremum。

既然规定了页面中的最小记录 与 最大记录，理所应当，上文中串联各个行记录的单向链表，则应该有一个固定的头部与固定的尾部，更新一下单链表的图。注意下infimum 与 supremum中的几个关键值。

infimum: n_owned=1，表示是某一个分组的最后一条记录，当前分组共1条记录；record_type=2；next_record=第一条真实行记录的真实值的相对位置。

supremum: n_owned=5，表示是某个分组的最后一条记录，当前分组共5条记录；record_type=3；next_record=0，表示记录是本数据页中最后一条记录。

OK，到现在数据页中完整的单链表已经形成了。

思考一个问题，如何根据主键值，在数据页中的单链表如何查找到相应的数据。

最直接的做法是：从 infimum记录开始，沿着单链表的顺序不断的向后查找，直到supremum结束。在这期间，找到满足条件的记录就返回，找不到则不返回。

一个数据页默认大小是16K，用于存储真实行记录的空间超过 98%以上。也就是说，一个数据页中在行记录填充满的情况下，行记录的数量是较多的（当然与行记录大小有关）。如果每次查询都从单链表的infimum记录一直到 supremum记录，肯定是无法接受的，很有必要对此现状进行优化。

由此，引出了数据页中的另一个模块，Page Directory，页目录。

首先返回看下上面完整单链表中，infimum记录 与 supremum记录中的两个值，n_owned。这个值分别为 n_owned=1 与 n_owned=5。

参考下n_owned的定义，它是：【页面分组之后，每个组最后一条行记录中该值等于本组内的记录数量。本组内其他记录该值都等于0。】

对于上面的单链表，其它行记录的owned值 都为零。也就是说，infimum单条记录作为一个组，剩余的四条行记录+supremum记录作为一个组。

mysql规定：

• 对于infimum记录所在的分组只能有1条记录，也就是它本身。

• 对于supremum记录所在的分组的记录数在1~8条之间。

• 其它的分组记录的条数范围，在4~8条之间。

将每个组中 最后一条记录在页面中的地址偏移量（该记录的真实数据与数据页中第0个字节之间的距离）单独提取出来，以倒序存储到数据页中的固定模块中。 

这个模块，就称为：Page Directory。Page Directory中存储的地址偏移量，也称为Slot 【[slɒt]， 槽】，每个Slot两字节。

再次更新下数据页结构图。

目前的只有四条记录，两个分组，数量太少了。我们继续往表中继续增加一些记录。

INSERT INTO page_demo VALUES(5, 500, 'eeee'),(6, 600, 'ffff'),(7, 700, 'gggg'),(8, 800, 'hhhh'),(9, 900, 'iiii'),(10, 1000, 'jjjj'),(11, 1100, 'kkkk'),(12, 1200, 'llll'),(13, 1300, 'mmmm'),(14, 1400, 'nnnn'),(15, 1500, 'oooo'),(16, 1600, 'pppp');INSERT INTO page_demo VALUES(5, 500, 'eeee'),(6, 600, 'ffff'),(7, 700, 'gggg'),(8, 800, 'hhhh'),(9, 900, 'iiii'),(10, 1000, 'jjjj'),(11, 1100, 'kkkk'),(12, 1200, 'llll'),(13, 1300, 'mmmm'),(14, 1400, 'nnnn'),(15, 1500, 'oooo'),(16, 1600, 'pppp');

在不断的插入新行记录时，因此不同类型分组数量的约束，所以分组也会增加。这个过程如下：

• 在初始情况下，一个数据页中只会有 infimum 与 supremum 这两条记录，它们分别属于两个组。此时Page Directory 也只会有两个slot，分别代表infimum的地址偏移量 与 supremum的地址偏移量。
• 之后每新增一条行记录，都会从Page Directory中找到对应的记录的主键值 比 待新增记录的主键值大 并且差值最小的slot【slot是一个组内最大的那条记录在页面中的地址偏移量，通过slot可以快速找到对应记录的主键值】， 然后把该slot对应的记录的 n_owned值加1，表示本组内新增了一条记录，直到该组中的记录数等于8个。

• 当一个组中的记录数等于8后，再插入一条记录，会将组中的记录拆分成两个组，其中一个组中是4条记录，另外一个组中是5条记录。拆分过程中，会新增一个slot，记录这个新增分组中最大的那条记录的地址偏移量。

现在来看看下，目前该数据页中的行记录的分组情况。

来演绎一个根据主键查询行记录的例子。假如想查询主键值 ，也就是C1=6的行记录。通过二分法查找，过程如下：

1. 设置low=0，high=4。计算中间slot的位置，(0 + 4) / 2 = 2, 通过slot 2 查询到对应的主键值等于8。因为8 > 6， 所以设置high = 2， low = 0不变。
2. 重新计算中间slot的位置，（0 + 2）/ 2 = 1, 查看 slot 1对应记录的主键值为4。又因为 4 < 6, 所以设置low = 1，high 不变。

3. 此时low = 1， high = 2， 所以确定主键值为6的行记录在 slot2 对应的组中。此时找到slot 2的最小一条记录【通过slot 1 的next_record找到slot 2的最小记录】，遍历slot 2中的所有记录即可。

截止目前，数据页模块中，还要三个模块是未知的。回想一下，对于一条行记录，它有 记录头信息 来描述这条行记录的相关信息，那么对于一个数据页，它有对应的头部来记录数据页的相关信息吗？

有的，自然是有的，而且还不少。这个模块就称为 Page Header。

Page Header的结构如下：

主要作用是标识 数据页中记录了多少条记录，Free Space在页面中的地址偏移量，页目录中包含多少slot等等。

额外说下page_direction 与 page_n_direction的含义。

page_direction:  假如新插入的一条记录的主键值比上一条记录的主键值比上一条记录大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就是page_direction。

page_n_direction: 假设连续几次插入新记录的方向都是一致的，InnoDB会把沿着同一个方向插入记录的条数记下来，这个条数就用PAGE_N_DIRECTION这个状态表示。 

当然，如果最后一条记录的插入方向改变了的话，这个状态的值会被清零重新统计。

到此为止，仅剩下两个模块了，加油啊。

上文中的Page Header 是专门针对数据页记录的各种状态信息。但数据页 仅仅是多种页类型中的一种，其它的还有例如undo日志页，溢出页，存储段信息页，存储区信息页等。因此mysql 使用了File Header 来描述各种页的通用信息。

从fil_page_prev 与 fil_page_next 两个属性可以联想到，不同页之间是有关联的，而且是以双向链表的形式。

最后一个模块，File Trailer 【 [ˈtreɪlə(r)]，挂车】。

InnoDB存储引擎会把数据存储到磁盘上，但是磁盘速度太慢，需要以页为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。

但是在同步了一半的时候中断电了怎么处理呢？此时就需要靠 File Trailer 模块中数据起作用。

展示下完整的数据页结构。

借用一下网上的一个很好的数据页图。

4、快速查询的秘籍：B+树索引

上文使用的数据共有16条，为了演示这个双链表的效果，现在假设【仅仅是假设】每个页中存放不超过4条行记录。则上文的16条记录，形成的数据页双链表结构如下图【此处省略了许多非必要展示的字段】。

从上面这个链表，可以得到以下结论：

1. 双向链表的页号并不保证是连续的。

2. 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。【在依次写入主键数据不连续的行记录时，会发生页中数据的迁移。】

从目前的双向链表结构中，想要根据主键值查找记录，也只能是从第一页开始，一页一页的依次查找。虽然在一个数据页中，可以根据 Page Directory进行快速的二分查找，但总体效率肯定不尽人意，得优化。

我们注意到，【下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值】。因此，首先进行第一步改进。

维护一个目录项，目录项中记录某个页中主键的最小值以及页号，各个目录项再以单向链表的形式链接起来。这样就可以根据主键查询目录项，得到满足的条件页，再进入相应的页中查询行记录即可。

到现在看看，目录项是不是也很像行记录，只是它的列值是主键与页号。那把这些目录项维护成在一个页中看看效果。毫无违和感，浑然天成。现在看到的，就是主键索引的雏形了。

目前数据有些少了，继续补充一些数据，再画个图看看。

INSERT INTO page_demo VALUES(17, 1700, 'qqqq'),(18, 1800, 'rrrr'),(19, 1900, 'sss'),(20, 2000, 'tttt');





现在看到的，就是一个典型的INNODB的主键索引了。它包含以下特点：

1. 整个主键索引的数据结构是一棵树，具体是以B+树实现。
2. 叶子节点与非叶子节点中的行记录按照主键大小顺序排成一个单向链表，页内的记录被划分成若干组。可以利用Page Directory进行二分法快速查找到行记录。
3. 存放用户记录的数据页，根据页中用户记录的主键大小顺序排成一个双向链表。所有用户记录都存放在叶子节点上。
4. 存放目录项记录的数据页都是非叶子节点，分层不同的层级。同一层级中的页也是根据页中目录项记录的主键大小顺序，排成一个双向链表。

通常除了主键索引之外，肯定还会建一些普通索引，称为二级索引，或者辅助索引。上面的数据，我们以上文中的数据 C2列建立一个二级索引看看。

现在来看看下，INNODB中 二级索引的特点。

1. 二级索引的数据结构 与 聚簇索引一样，是B+树结构。
2. 二级索引的所有目录项页存储行记录的真实数据是 索引列+页号。

3. 二级索引的非叶子节点存储行记录的真实数据是 索引列+主键值。

因为在二级索引中查询到的是主键值，如果想要得到完整的行记录，则需要拿着主键值再到聚簇索引中再进行一次查询。这个过程称为【回表】。

回表的过程，特别要强调下每次对于二级索引来说，每次查询到一条满足二级索引字段条件的记录时，都进行一次回表判断是否满足其他条件，然后将满足所有条件的一条查询结果返回给客户端。

再讲讲联合索引。现在以C2 与 C3两列作为联合索引，为了更好的展示联合索引的效果，先修改几条行记录。

update page_demo set c3 = 'dddd' where c2 = 100;update page_demo set c3 = 'cccc' where c2 = 200;update page_demo set c3 = 'bbbb' where c2 = 300;update page_demo set c3 = 'aaaa' where c2 = 400;update page_demo set c2 = 300 where c1 = 4;

给联合索引画个图。

总结下联合索引的特点：

联合索引的数据页中记录的排序，默认是按照定义联合索引的第一列排序的，在第一列值相等的情况下，再按照第二列排序。其它的方面均与单列的二级索引无差别。

联合索引还有一个比较特殊的使用场景：最左前缀匹配。

优点：

1. 对于等值查询，可快速定位到对于的行记录。
2. 对于范围查询，可辅助缩小扫描区间。
3. 当ORDER BY的列名 与 索引的列名完全一致时，可加快排序的顺序。
4. 当GROUP BY的列名 与 索引的列名完全一致时，可加快分组。
5. 当二级索引列中 包含了 SELECT 关键字后面写明的所有列，则在查询完成二级索引之后无需进行回表操作，直接返回即可。这种情况，称为【覆盖索引】。

1. 只为用于搜索，排序，分组的列创建索引。
2. 索引的列需要有辨识性，尽可能地区分出不同的记录。
3. 索引列的类型尽量小。因为数据类型越小，索引占用的存储空间就越少，在一个数据页内就可以存放更多的记录，磁盘I/O带来的性能损耗也就越小。
4. 如果需要对很长的字段进行快速查询，可考虑为列前缀建立索引。【alter table table_M add index idx_key1(column_n(10)) -->  将table_M表的 idx_key1列的前10个字符创建索引】
5. 覆盖索引，当二级索引列中包含了SELECT关键字后面写明的所有列，则在查询完成二级索引之后无需进行回表操作，直接返回即可。因此，编写【select *】的时候，要想想是否必要
6. 在查询语句中，索引列不要参与条件值计算，也是把条件值计算完成之后，再和索引列对比。【否则MYSQL会认为搜索条件不能形成合适的扫描区间来减少扫描的记录数量】

-end-