InnoDB Sorted Index Build

Sorted Index Build

InnoDB 在创建或重建索引时采用 批量加载而不是一次插入一个索引记录的方式。这种索引创建方法也称为 Sorted Index Build ,该方式不支持空间索引。

索引创建有三个阶段:

  1. 第一阶段,扫描聚簇索引,生成索引条目并添加到排序缓存(sort buffer)。当排序缓存满了后,条目被排序、写入临时的中间文件。这个过程也称为 run 。

  2. 第二阶段,一个或多个 run 写入临时中间文件,对文件里的所有条目执行合并排序。

  3. 在第三阶段,排序后的条目被插入到 B+tree 上。

Sorted Index build 采用自底向上方式来构建索引,采用这种方式,在 B+Tree 的每一层,持有对最右叶子页的引用。位于B+Tree需要的深度的最右叶子页被分配,条目按它们排序后的顺序插入。一旦叶子页满了,一个节点指针追加到父页上,同层叶子页被分配用于接下来的插入。这个过程持续至所有条目插入完成,这可能导致插入一直到顶层。

白话解读:最底层的最右叶子页插入索引记录,如果当前最右叶子页满了,生成一个新的最右叶子页作为接下来的插入位置,在新旧最右叶子页之间建立指针链接,然后把指向旧最右叶子页的指针追加到上一层的最右叶子页,触发上一层的最右叶子页插入,逻辑跟前面是一样的,这是个递归的过程,直至根页。这是一个自底向上、递归构建的过程

最终生成的索引结构如下图(图片来自MySQL内核解析:Innodb页面存储结构-1):
InnoDB索引结构

为后续插入保留空间

可以使用 innodb_fill_factor 配置选项来指定在 B+Tree 页空间保留的空闲百分比,用于后续在这些位置插入索引条目。

这个设置应用于索引树的叶子和非叶子页。不适用于外部页如用于 TEXT/CLOB 条目的。

这个配置是一个提示而非强制约束。