InnoDB 索引结构

Posted on 2020-07-07 In 数据库

根据 InnoDB 的行记录格式和数据页结构，我们已经知道了数据页之间组成了一个双向链表，而每个数据页中的行记录又会按照主键值从小到大的顺序组成一个单向链表。在某一页中查找指定主键值的记录可以根据页目录使用二分法快速定位到行记录所在分组的槽，然后遍历该分组的行记录即可。

数据页组成的双向链表

没有索引的查找

我们先看一下在没有索引时是如何查找记录的。为了方便说明，这里只列举对某个列精确匹配的情况，比如：

1	SELECT [列名列表] FROM 表名 WHERE 列名 = xxx;

在没有索引的情况下，由于我们无法快速定位到记录所在的页，因此只能从第一个数据页开始，沿着双向链表一直向后找。在每个页中，如果以主键作为搜索条件，则可以直接通过页目录使用二分法快速找到记录所在分组，然后遍历分组即可；如果使用其他列作为搜索条件，那么就无法借助于页目录，只能使用最笨的方式，也就是从最小记录开始沿着 next_record 向后遍历。

InnoDB 的索引结构

为了方便说明，我们首先创建一张表：

CREATE TABLE index_demo (
    c1 INT,
    c2 INT,
    c3 CHAR(1),
    PRIMARY KEY(c1)
) ROW_FORMAT = Compact;

这里简化了行记录的结构，记录头只保留了 record_type 和 next_record。同时为了方便，这里限制了一页只能存放 3 条记录（实际可以存放很多条记录）。

简化的行记录结构

InnoDB 为数据页也建立了类似页目录那样的目录项，即选择每页中最小行记录（不是 Infimum 行记录）的主键值和页号来作为一个目录项，然后将这些目录项作为行记录也存放在一页中。这些行记录的 record_type 的值为 1，表示这是一个 B+树非叶子节点，也就意味着这是一个目录项，同时目录项记录只有主键值和页号这两个列。除了这些，目录项记录与普通的行记录就没有太大差别了。它们使用的都是数据页（FIL_PAGE_TYPE 的值为 0x45BF），都会为主键值生成 Page Directory，从而可以使用二分法加速主键记录的查找。

目录项和目录项记录都是为了表达清楚而杜撰的，并不代表真实名称。

索引结构1

如果数据页有很多，那么只用一个数据页来存放目录项就有可能不够，此时就会再申请一个数据页，同时该数据页与第一个数据页通过指针进行关联，从而形成一个双向链表。

索引结构2

当行记录继续增多，存放目录项的数据页也持续增多，那么此时又该如何根据主键值快速定位到某个存储目录项记录的页呢？答案就是为这些存储目录项记录的页再生成一个更高级别的目录，如此往复。

索引结构3

那么此时根据主键值查找对应行记录就分为以下几步：假设要查找的主键值为 20，那么首先需要确定目录项所在的页。从最高层开始，根据页目录（Page Directory）用二分法快速找到页号为 30 的目录项记录，然后对页号为 30 的数据页重复上述步骤，找到页号为 9 的目录项记录，最后到 9 号数据页中同样重复上述步骤，最终找到对应的行记录。

根页

每当为一个表创建一个 B+树索引（聚集索引非手工创建）时，InnoDB 都会为这个索引创建一个根节点（根页）。随后向表中插入记录，这些记录会先存储在这个根页中。当根页中的可用空间不足时，会将根页中的所有记录复制到一个新分配的数据页中，假设为页 a，然后对这个新页进行页分裂的操作，得到另一个新的页，假设为页 b。接下来新插入的记录会根据键值（聚集索引是主键值，辅助索引是索引列的值）的大小被分配到页 a 或者页 b 中，而根页则升级为存储目录项记录的页。

一个 B+树索引的根节点自诞生之日起，便不会再移动。只要我们对某个表建立一个索引，那么它的根节点的页号便会被记录到某个地方，之后只要用到这个索引的时候，都会从这个固定的地方取出根节点的页号，从而来访问这个索引。

页分裂

当一个页（假设页号为 10）快要填满或者已经填满，新记录无法填充到本页时，会到当前页的下一页（假设页号为 11）进行填充。如果下一页也没有足够的空间容纳新记录，那么 InnoDB 会创建一个新的页（页号可能为 12），然后判断从当前页的哪行记录开始进行页分裂，接下来需要移动行记录，然后重新确定页之间的关系。此时 10 号页的前一页为 9 号页，下一页为 12 号页，而 12 号页的下一页则为 11 号页。

页分裂1

页分裂2

页分裂3

页分裂4

此时 B+树从逻辑上来说仍然满足按照主键大小顺序排序，但是从物理存储上讲数据页是乱序的，并且有很大的概率会落到不同的区。

聚集索引

像上面这样的，B+树本身就是一个目录，或者说本身就是一个索引，它有两个特点：其一是行记录和页都是通过主键值的大小进行排序的，即页内记录按照主键值由小到大形成一条单向链表，各个存放用户记录的数据页也是根据页中用户数据的主键值由小到大形成一条双向链表，存放目录项记录的数据页分为不同的层级，同一层级的数据页也是根据页中目录项记录的主键值由小到大形成一条双向链表。其二是 B+树的叶子节点存储的是完整的用户记录。

满足这些条件的索引结构就是聚簇索引，同时在 InnoDB 中，聚簇索引就是数据的存储方式，也就是所谓的索引即数据，数据即索引。

辅助索引

辅助索引也就是二级索引，通过 INDEX 语句创建。在聚集索引中，B+树中的数据都是按照主键值进行排序的，对于非主键的查询条件只能通过最笨的方式，也就是我们常说的全表扫描来查找。有时候为了优化查询性能，我们会选择一些列来建立二级索引，这样我们就有了好几颗 B+树，不过二级索引的树结构与聚集索引有些不同。还是以上表为例子，我们在 c2 列上建立辅助索引。

辅助索引

辅助索引中的行记录与数据页会按照 c2 列的大小进行排序，与聚集索引不同的是，此时 B+树的叶子节点存储的并不是完整的用户记录，而只是 c2 和主键这两列，目录项记录中也不再是主键和页号，而是 c2 和页号。同时在使用辅助索引进行查询时，前面的查询步骤与聚集索引相同，但是如果没有覆盖索引，在拿到了行记录之后，还需要使用行记录中的主键到聚集索引中查找主键值对应的完整用户记录，这也就是我们俗称的回表。

需要注意的是，我们把辅助索引中的内节点，也就是存储目录项记录的数据页中的行记录内容说成是“索引列和页号”的搭配其实是不严谨的。因为建立辅助索引的列很大可能是没有唯一约束的，因此很有可能会出现索引列的值重复的情况，如果此时新插入记录的索引列值与目录项记录中的两条记录相同，那么新记录应该插入哪一页呢（如下图的例子）？

辅助索引目录项记录页