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_fill_factor 配置选项来指定在 B+Tree 页空间保留的空闲百分比，用于后续在这些位置插入索引条目。

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

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