[大数据]【展开讲讲】InnoDB中的索引方案

环境

MySQL：5.7
存储引擎：InnoDB
行格式：COMPACT
字符集：ascii
先建一张表：

mysql> CREATE TABLE page_demo( 
	-> c1 INT, 
	-> c2 INT, 
	-> c3 VARCHAR(1OOOO), 
	-> PRIMARY KEY (c1) 
	-> ) CHARSET=ascii ROW_FORMAT=COMPACT; 
Query OK, 0 rows affected (0.03 sec) 

前置知识

InnoDB 索引页

页是 InnoDB 管理存储空间的基本单位，一个页的大小一般是 16KB。InnoDB 有很多不同类型的页，我们这里讨论存放记录的页即索引页。
page_demo 表的索引页结构如下图所示：

File Header

页的一些通用信息。

Page Header

索引页专有的一些信息。

Infimum + Supremum

页面中的最小记录和最大记录（虚拟的记录）。

User Records

在页的 7 个组成部分中，我们自己存储的记录会按照指定的行格式（本文中是 COMPACT）存储到 User Records 部分。User Records 中的记录是按照主键值由小到大的顺序串联成一个单向链表。

Free Space

页面中尚未使用的空间。

Page Directory（页目录）

1. 将所有正常的记录（包括 Infimum 和 Supremum 记录，但不包括已经移除到垃圾链表的记录）划分为几个组。
2. 每个组的最后一条记录的头信息中的 n_owned 表示该组内共有几条记录。
3. 将每个组中最后一条记录在页面中的地址偏移量（就是该记录的真实数据与页面中第 0 个字节之间的距离）单独提取出来，按顺序存储到靠近页尾部的地方。这个地方就是 Page Directory。页目录中的这些地址偏移量称为槽（Slot），每个槽占用 2 字节。页目录就是由多个槽组成的。

假设现在 page_demo 表中正常的记录共有 6 条。InnoDB 会把它们分成 2 个组，第一组只有一个 Infimum 记录，第二组是剩余的 5 条记录。2 个组就对应着 2 个槽，每个槽中存放每个组中最大的那条记录在页面中的地址偏移量，如下图所示：

先往 page_demo 表中插入 16 条数据，我们看看怎么在页目录中查找数据：

假设我们要查找主键为 6 的记录，过程是这样的：

1. 计算中间槽的位置：(0+4)/2=2，查看槽 2 对应记录的主键值为 8，又因为 8>6，所以设置 high=2，low 保持不变。
2. 重新计算中间槽的位置，(0+2)/2=1，查看槽 1 对应记录的主键值为 4；又因为 4 < 6，所以设置 low=1，high 保持不变。
3. 因为 high - low 的值为 1，所以确定主键值为 6 的记录在槽 2 对应的组中。此时需要找到槽 2 所在分组中主键值最小的那条记录，然后沿着单向链表遍历槽 2 中的记录。但是，每个槽对应的记录都是该组中主键值最大的记录，这里槽 2 对应的记录是主键值为 8 的记录。所以我们要先找到槽 1 对应的记录（主键为 4），这条记录的下一条记录就是槽 2 所在分组中主键值最小的记录，其主键值为 5。所以，我们可以从这条主键值为 5 的记录出发，遍历槽 2 中的各条记录，直到找到主键值为 6 的那条记录即可。由于一个组中包含的记录条数最多是 8 条，所以遍历一个组中的记录的代价是很小的。

综上，在一个数据页中查找指定主键值的记录时，过程分为两步：

1. 通过二分法确定该记录所在分组对应的槽，然后找到该槽所在分组中主键值最小的那条记录（上个槽中最大记录的下一条）。
2. 通过记录的 next_record 属性遍历该槽所在的组中的各个记录。

File Trailer

校验页是否完整。

记录头信息

预留位 1 和预留位 2

没有使用。

deleted_flag

标记该记录是否被删除。

min_rec_flag

B+ 树中每层非叶子节点中的最小的目录项记录都会添加该标记。

n_owned

一个页面中的记录会被分成若干个组，每个组中最后一条记录的n_owned值代表该组中所有的记录条数，其余记录的 n_owned 值都为 0。

heap_no

当前记录在页面堆中的相对位置。

record_type

当前记录的类型，0 表示普通记录，1 表示 B+ 树非叶节点的目录项记录。2 表示 Infimum 记录。3 表示 Supremum 记录。

next_record

下一条记录的相对位置。

目录项记录

每个页对应一个目录项，每个目录项包括下面两个部分：

1. 页的用户记录中最小的主键值，用 key 来表示。
2. 页号，用 page_no 表示。

目录项记录和普通用户记录的异同

同：

• 一样的索引页（页面类型都是 0x45BF，这个属性在 File Header 中）。
• 组成页的 7 部分结构相同。
• 都会为主键值生成 Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。

异：

• 目录项记录的 record_type 值是 1，普通用户记录的 record_type 值是 0。
• 目录项记录只有主键值和页的编号两个列，而普通用户记录的列是用户自己定义的，可能包含很多列，另外还有 InnoDB 自己添加的隐藏列。
• 只有目录项记录的 min_rec_fiag 属性才可能为 1，普通用户记录的 min_rec_fiag 属性都是 0。

InnoDB 中的索引方案 B+ 树

无论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到 B+ 树这个数据结构中。我们也将这些数据页称为 B+ 树的节点。我们真正的用户记录其实都存放在 B+ 树最底层的节点上，这些节点也称为叶子节点或叶节点。其余用来存放目录项记录的节点称为非叶子节点或者内节点，其中 B+ 树最上边的那个节点也称为根节点。
假设现在我们要查询主键为 20 的记录，步骤如下：

1. 确定存储目录项记录的页。
   因为页 33 中有 2 个存储目录项记录的页，即页30和页32。又因为页 30 表示的目录项记录主键值的范围是[1，320)，页 32 表示的目录项记录主键值不小子 320，所以主键值为20的记录对应的目录项记录在页 30 中。
2. 通过存储目录项记录的页确定用户记录真正所在的页。因为 12 < 20 < 209，所以确定记录在页 9 中。
3. 在真正存储用户记录的页中定位到具体的记录（通过 Page Directory 页目录）。

聚簇索引

聚簇索引有以下 2 个特点：

• 使用记录主键值的大小进行记录和页的排序，这包括 3 方面的含义。
  • 页（包括叶子节点和非叶子节点）内的记录按照主键的大小顺序排成一个单向链表，页内的记录被划分成若干个组，每个组中主键值最大的记录在页内的偏移量会被当作槽依次存放在页目录中(当然 Supremum 记录比任何用户记录都大)，我们可以在页目录中通过二分法快速定位到主键列等于某个值的记录。
  • 各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表。
  • 存放目录项记录的页分为不同的层级，在同一层级中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
• B+ 树的叶子节点存储的是完整的用户记录。

我们把具有这两个特点的 B+ 树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。InnoDB 存储引擎会自动为我们创建聚簇索引。
在 InnoDB 存储引擎中，聚簇索引就是数据的存储方式(所有的用户记录都存储在了叶子节点)，也就是所谓的**「索引即数据，数据即索引」**。

总结

InnoDB 存储引擎的索引是一棵 B+ 树，完整的用户记录都存储在 B+ 树第 0 层的叶子节点；其他层次的节点都属于非叶子节点，非叶子节点中存储的是目录项记录。
InnoDB 的索引分为两种：

1. 聚簇索引：以主键值的大小作为页和记录的排序规则，在叶子节点处存储的记录包含了表中所有的列。
2. 二级索引：以索引列的大小作为页和记录的排序规则，在叶子节点处存储的记录内容是索引列 + 主键。

• InnoDB 存储引擎的 B+ 树根节点自创建之日起就不再移动。
• 在二级索引的 B+ 树非叶子节点中，目录项记录由索引列的值、主键值和页号组成。
• 一个数据页至少可以容纳 2 条记录。
• MyISAM 存储引擎的数据和索引分开存储，这种存储引擎的索引全部都是二级索引，在叶子节点处存储的是列 + 行号(对于定长记录格式的记录来说)。