Author: 西格
InnoDB的二级索引创建进入的主要函数为row_merge_build_indexes()，其整个过程大致可以分为三个步骤：扫描主建索引row_merge_read_clustered_index()、按照新的key排序row_merge_sort()、建立新的索引树row_merge_insert_index_tuples()。我们将按照这三个步骤来介绍二级索引的创建过程。
row_merge_read_clustered_index()由于在InnoDB中，所有的记录都保存在主键的B+树中，所以在建立新的二级索引之前，先要去主键索引的B+树中把全部的记录都读取出来。
使用btr_pcur_open_at_index_side()函数以BTR_SEARCH_LEAF的模式打开一个b+树最左边的叶子结点的游标（cursor）。这个过程首先获取整个index的S锁，从根节点开始，一层一层向下，每一层调用buf_page_get_gen()并获取途径的page和它们的S锁，直到到达最后一层，获取到B+树叶子层最左边的一个page，获取该page的锁。并调用mtr_release_s_latch_at_savepoint()释放index的S锁和mtr_release_block_at_savepoint()释放掉沿途page的锁。
在一个page内，每次调用page_cur_get_rec()函数获取cursor位置的一条记录。读完一个page的所有记录之后，就会调用btr_block_get()函数把cursor定位到下一个page，并获取下一个page的S锁，并调用btr_leaf_page_release()函数释放当前page的S锁，直到读完主键索引的所有记录。
读取记录的时候，如果记录已经被标记了删除的标志，则会跳过这条记录。如果是online的方式创建索引，为了保证索引创建完成之后，row_log_table_apply()应用新增log时不会看到更新版本的记录，在读取记录时，还需要判断该记录对当前事务视图的可见性，如果记录的版本对当前的视图不可见，则需要去获取老版本的记录。
从主键索引的B+树上直接拿到的record记录是物理记录，需要调用row_build_w_add_vcol()函数把他们转化为逻辑记录。为了减少之后外部排序的次数，在读取记录时会做一些规模很小的排序。row_merge_buf_add()把逻辑记录添加到sort buffer里面，sort buffer的大小保证至少可以放得下一条记录。当sort buffer内存放的记录满了之后，就会对sort buffer内的记录进行一次排序。
如果主键索引中全部的记录只用了一个sort buffer就存下了，那么就不用把sort buffer里这些记录写入到临时文件了，跳过第二步的row_merge_sort()函数，直接用这些记录执行row_merge_insert_index_tuples()函数来插入到新的二级索引建树。否则，需要创建临时文件来保存这些在sort buffer内部完成排序的记录。每次把存满记录的sort buffer写入文件之前，先调用row_merge_buf_write()函数把sort buffer里面的记录写入到一个block里面，这个过程中，会调用row_merge_buf_encode()函数将每条记录转化为COMPACT格式，然后写入block中。之后再调用row_merge_write()函数把block的内容写入临时文件，并清空sort buffer。
重复这样的操作，直到扫描完主键索引中的全部记录。
row_merge_sort()在完成了扫描主键索引的工作之后，我们就得到了一个保存着所有记录的临时文件（除了记录的数量未达到一个sort buffer大小的情况）。这个临时文件由一个一个内部有序的block组成，而这个步骤的任务，就是将这些block进行归并排序，从而达到全局有序。
除了存储了全部记录的临时文件之外，排序中还需要借助另一个临时文件来辅助排序。每个局部有序的连续内容被称为一个run，排序的终点是要把run的数量变成为1，也就是全局有序的状态了。
每一轮的排序row_merge()中，会调用row_merge_blocks()把前一半的所有run与后一半的所有run进行合并，而两个run合并的时候，也是一对记录一对记录的比较，按照从小到大的顺序插入到辅助临时文件中。当一轮合并排序结束之后，run的数量就会减少一半，辅助临时文件中就写满了一个个局部有序的run。在下一轮排序中，就会原本的临时文件作为辅助临时文件，而原本的辅助临时文件，则调换身份为存储全部记录的临时文件。重复这个过程，直到全部的run都合并为一个run，外部排序就完成了。
row_merge_insert_index_tuples()在这个阶段，要用所有已经排好序的记录，为新的二级索引建立b+树。从MySQL 5.7.5开始，提供了Bulk Load的建树方式，采用自下而上的方式完成整个索引树的建立过程。在这里，我们以Bulk Load的方式为例，介绍这个过程。
每次从临时文件中读取一条记录，调用row_rec_to_index_entry_low()函数把记录转化为dtuple_t类型，然后就可以用BtrBulk::insert()来把记录插入索引树，这个插入索引树的过程具体是这么做的。首先，每当需要插入一个dtuple_t记录时，会先找到b+树的最右边的叶子结点，BtrBulk的m_page_bulks是一个记录了b+树每一层最右边一个page的vector，从m_page_bulks中就可以拿到最右边的叶子结点。接下来需要调用prepareSpace()为即将插入的记录准备空间。这个准备空间的过程，是优先用PageBulk::isSpaceAvailable()判断该叶子结点是否具有足够的剩余空间支持插入该条记录，一条记录的插入除了会增加这条记录的数据本身占据的大小，还会增加它带来的directory slots大小的增量，此外，剩余空间还需要考虑fill factor的预留空间和为压缩页预留的padding空间。如果剩余空间足够，就可以往这个page里面插入该条记录，否则，就需要创建新的page来存储记录。PageBulk::init()可以进行新的page的创建与初始化，这个过程中会先调用fsp_reserve_free_extents()申请一个free page的预留空间，预留空间申请成功就会调用btr_page_alloc()函数申请一个新的page，然后调用fil_space_release_free_extents()释放预留的位置。
创建完新的page之后，就把新的page和老的page之间用指针连起来，并把老的page的指针插入到上一层的父节点中，这个插入的过程和前面的一样，同样有可能触发新page的申请和继续递归插入父节点。之后还需要更新m_page_bulks，把所有产生了新的page的层对应的page指针做一个修改，保证m_page_bulks中记录的依然是每一层最右边的page的指针。对于叶子结点的新page产生，还会唤醒page cleaner进行刷脏操作。
经过这一系列的操作之后，我们就拥有了b+树上可以容纳当前记录的最右侧的叶子结点，调用rec_convert_dtuple_to_rec()把dtuple_t类型的记录转化为物理记录，并插入到page中。
当临时表中全部记录都插入到新的b+树之后，创建新的二级索引就完成了。