本文翻译自MySQL 8.0 Reference Manual 15.6.2.3 Sorted Index Builds
MySQL在创建或者重建索引时，采用的是批量加载并创建索引的方式，而不是每次加载一条数据然后插入一条索引的方式。这种批量创建索引的方式被称为排序索引构建(Sorted Index Builds)。排序索引构建不支持空间索引(Spatial Indexes)。
采用排序索引构建创建索引分为三个阶段。在第一个阶段，通过扫描聚簇索引产生需要构建索引的索引项并放到排序缓冲区中。当排序缓冲区满时，这些索引项会被排序并且写入到一个临时文件中。这步处理也被称为run。在第二个阶段，当一个或多个runs被写入临时文件，会对这些临时中的所有索引项进行合并排序。在第三个阶段，也即最终阶段，这些排过序的索引项会被插入到B-tree中。
在引入排序索引构建之前，索引项插入到B-tree的插入动作时通过特定的插入APIs一条记录一条记录依次插入的。这种方式首先通过乐观的方式打开B-tree索引游标，找到插入的位置，然后向找到的B-tree索引页插入一条记录。如果因为页满造成插入失败，则转为悲观插入方式，即打开B-tree索引游标，对页进行拆分然后进行插入动作。这种从上向下(top-down)的方式建立索引的代价就是插入位置的查找以及B-tree节点的拆分和合并。
排序索引构建则采用从下向上的方式构建索引。通过采用这种方式，可以使用持有最后叶子节点页，并且可以按需进行最右叶子节点页的分配和索引项插入。当一个叶节点页满时，会分配一个新的兄弟页，然后在其父节点插入一个指针指向新分配的兄弟页。这个过程将一直重复知道所有的索引项插入完毕。当一个兄弟页分配后，指向原先叶子节点页的引用将释放，新分配的兄弟页则成为新的最右节点页并作为新的默认插入位置（译者注：通过这种方式避免了插入位置的查找）。
- 为后续修改或新增数据保留一定的
B-tree节点页空间
为了在每个页保留一定的页空间为后续可能存在的插入和修改操作做准备，可以通过innodb_fill_factor参数配置需要保留B-tree页空间的百分比。例如，设置innodb_fill_factor=80，则会在排序构建索引时保留20%的空间为后续使用做准备。这个设置会同时对B-tree的叶子节点和非叶子节点生效。但是对TEXT和BLOB类型的外部页不生效。需要注意的是程序实际实现时保留的空间并不是严格等于参数innodb_fill_factor设置的值，该参数设置的值只是一个参考值并不是一个硬标准。
