MySQL · 源码阅读 · 创建二级索引

MySQL · 源码阅读 · 创建二级索引

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。

重复这样的操作,直到扫描完主键索引中的全部记录。

按照新的key排序——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+树之后,创建新的二级索引就完成了。

分享到 :
相关推荐