作者：郑啟龙
摘要：
对于 MYSQL 的 INNODB 存储引擎的索引，大家是不陌生的，都能想到是 B+ 树结构，可以加速 SQL 查询。但对于 B+ 树索引，它到底 “长” 得什么样子，它具体如何由一个个字节构成的，这些的基础知识鲜有人深究。本篇文章从 MYSQL 行记录开始说起，层层递进，包括数据页，B+ 树聚簇索引，B+ 树二级索引，最后在文章末尾给出 MYSQL 索引的建议。文章涉及较多基础知识，内容较为枯燥，因此采用较多的图片补充说明，希望能对读者有帮助。
A. 一条记录存储格式：COMPACT 行记录结构
mysql 是关系型数据库，每一行记录都是表结构定义的关系的 显示表达。在脑中很直观地想到，记录存储时也可能按行存储。
的确，mysql 是这么存储一条行记录的。但会添加一些额外信息，来补充行记录信息。
有一个概念可能大家不熟悉，是【变长字段】。mysql 数据库类型中的 VARCHAR(M), VARBINARY(M), 各种 TEXT，BLOB 类型，这些类型的数据长度是可变的，称 数据类型为可变长类型的列 为 变长字段。
另外，mysql 会默认为行记录添加一些列（隐藏列）。上图补充这些隐藏列之后，完整行记录的结构如：
DB_ROW_ID: 唯一标识一条记录，在表中未设置主键 或 未有不允许为 NULL 的 UNIQUE 键时，则 MYSQL 新增该隐藏列作为主键。 DB_TRX_ID: 事务 ID。 DB_ROLL_PTR: 回滚指针。
下面再详细的铺开 ，关于记录的额外信息 的具体内容。
通过真实的数据库表的行数据，来强化下上面的概念。 首先新增一个表，并在表中 insert 两条记录。
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 值列表都是逆序存放的。 原因是：这样可以使得记录中位置靠前的字段 和 它们对应的字段长度信息在内存中的距离更近，可能会提高 高速缓存的命中率。
B. 盛放记录的盒子：数据页
为了更清楚的理解 数据页结构 以及 下文中的索引，更换一个带主键的表。
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 模块中数据起作用。
展示下完整的数据页结构。
盗用一下网上的一个很好的数据页图。
C. 快速查询的秘籍：B+ 树索引
上文在介绍 File Header 时，我们特别说明了里面的两个数据：FIL_PAGE_PREV，指向前一个页号。FIL_PAGE_NEXT, 指向后一个页号。由此可以得出，多个数据页之间的数据结构是双链表。
上文使用的数据共有 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.存放目录项记录的数据页都是非叶子节点，分层不同的层级。同一层级中的页也是根据页中目录项记录的主键大小顺序，排成一个双向链表。
通常也把 INNODB 的 B+ 树索引称为 聚簇索引（clustered/ˈklʌstəd / index），所有的真实数据都存储在聚簇索引中。【索引即数据，数据即索引】。
通常除了主键索引之外，肯定还会建一些普通索引，称为二级索引，或者辅助索引。上面的数据，我们以上文中的数据 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;
给联合索引画个图。
总结下联合索引的特点：
联合索引的数据页中记录的排序，默认是按照定义联合索引的第一列排序的，在第一列值相等的情况下，再按照第二列排序。其它的方面均与单列的二级索引无差别。
联合索引还有一个比较特殊的使用场景：最左前缀匹配。 例如有联合索引的列包含：C1，C2，C3 三列，而且顺序也是 C1，C2，C3。 则查询语句：select * from page_demo where c1 = x and c2 = y and c3= z, 使用到了 C1，C2，C3 列排序的结果。 select * from page_demo where c1 = x and c2 = y, 使用到了 C1，C2 列排序的结果。 select * from page_demo where c1 = x and c3 = z, 仅使用到了 C1 列排序的结果。
D. 索引的优缺点及建议
优点：
1.对于等值查询，可快速定位到对于的行记录。
2.对于范围查询，可辅助缩小扫描区间。
3.当 ORDER BY 的列名 与 索引的列名完全一致时，可加快排序的顺序。
4.当 GROUP BY 的列名 与 索引的列名完全一致时，可加快分组。
5.当二级索引列中 包含了 SELECT 关键字后面写明的所有列，则在查询完成二级索引之后无需进行回表操作，直接返回即可。这种情况，称为【覆盖索引】。
缺点：
1.建立索引占用磁盘空间。
2.对表中的数据进行 增加，删除，修改 操作时，都需要修改各个索引树，特别是如果新增的行记录的主键顺序不是递增的，就会产生页分裂，页回收等操作，有较大的时间成本。
3.当二级索引列的值 的 不重复值的个数较少时，通过二级索引查询找到的数据量就会比较多，相应的就会产生过多的回表操作。
4.在执行查询语句的时候，首先要生成一个执行计划。通常情况下，一个 SQL 在执行过程中最多使用一个二级索引，在生成执行计划时需要计算使用不同索引执行查询时所需的成本，最后选择成本最低的那个索引执行查询。 因此，如果建立太多的索引，就会导致成本分析过程耗时太多，从而影响查询语句的性能。
建议：
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 会认为 搜索条件不能形成 合适的扫描区间来减少扫描的记录数量】