MySQL源码学习（四）：从insert看btr

Btr: B+ Tree，是innodb的核心数据结构，它作为数据的索引，让数据库能够快速找到指定的数据。

B+ Tree的相关说明网上已经很多，本文通过insert操作的调用栈，来分析btr的操作过程。

·         Btr操作在insert的哪个过程中被调用?

图1 insert的函数调用栈(btr部分)

图1是一次insert操作打印的trace日志。大家可以看到第一行write_record函数，这个步骤是在mysql_insert函数中调用的。下面先调用innobase的write_row接口来执行pimary key的auto_increment操作，生成主键。然后再调用row_ins方法来向btr中插入数据。

本文要关注的流程主要在row_ins中的流程。

·         row_ins

该函数在storage/innobase/row/row0ins.cc文件中，可以看出这是跟存储引擎相关的操作。

图2 row_ins的主要流程

其中，Trace日志中打印了其中的3个流程，就包含在“插入index和数据”这个步骤中”：

row_ins_index_entry_step

|  row_ins_cluster_index_entry_low

|  |  btr_cur_search_to_nth_level

row_ins_index_entry_step：向表中插入一个索引

row_ins_cluster_index_entry_low: cluster_index这里是指聚簇索引，很熟悉的词吧。这里会插入一个聚簇索引，并且忽略外键的限制。如果发现主键已经存在（主键冲突），那么除非这条已经有的记录已经被事务标记为“已删除”，否则就会报主键冲突错误。

btr_cur_search_to_nth_level:  在btr上搜索指定的索引，并把cursor定位到指定的level。改函数支持两种模式，PAGE_CUR_LE和PAGE_CUR_GE。Insert使用PAGE_CUR_LE这种方式进行搜索。

·         分配index

图3 index的获取

row_ins函数第一部分，通过dict_table_get_first_index(node->table)来获取索引。Row_ins_get_row_from_select和row_ins_get_row_from_values分别对应了INSERT … SELECT语句和INSERT … values语句（包括多个values）。这两个函数中会把value值保存到node对象中。

·         插入数据

图4 index和数据的插入

如图4所示，row_ins_index_entry_step方法是执行index插入的入口方法。返回如果成功，则说明插入成功。如果返回错误码是DB_DUPLICTE_KEY，则会判断是否包含了on duplicate update的语法，如果有的话，则会将索引保存到node->duplicate对象中，以便后面继续执行。如果没有包含on duplicate update的语法，则直接返回主键冲突的错误。

row_ins_index_entry_step中的三个主要流程上面已经介绍过。这里重点看row_ins_clust_index_entry_low函数中的流程：

图5 获取btr中的cursor

btr_pcur_open方法，获取到这个新生成的index到底放到btr的哪个位置。这个位置，就由Cursor来标记标记。

图6 btr_pcur_get_btr_cur宏定义

·         pcur和cursor的关系

pcur是persistent cursor。因为btr是会分裂和变动的，当btr被分裂时，cursor的位置也会对应的进行变化。因此通过一层pcur的封装，将cursor的变化对外屏蔽，针对一个index，我们只需要通过一个固定的pcur去获取当前的cursor就可以了。

图7 btr_pcur_t依赖于btr_cur

获取到了真实的cursor后，就可以拿到对应的leaf节点，就是具体的page。如图8所示，btr的leaf是page，而不是record，从这两个代码就可以证明。而插入的数据最终，是写入到rec_t中的。这里只是对page是否有记录做了初步的判断，记录的插入请看图9:。

图8 通过cursor拿到page

请看图9中的btr_cur_optimistic_insert方法:

图9 数据的插入

该方法会把记录写入到record中，同时如果需要重做btr，会着这里面进行调整。

图10 插入流程

如图10所示，首先通过cursor拿到page，并记录下插入之间的record地址。通过page_cur_tuple_direct_insert方法插入记录后。再次通过相同cursor拿到record地址，并判断插入前和插入后的record地址是否相同。如果不同，说明btr发生了重构。这也证明了corsor指向的btr位置是在不断变化的。Corsor是在btr上的绝对位置，而这个位置上的数据会因为btr的重构而改变，因此外面加入了一层psersistent cursor，使得能够通过同一个index快速找到cursor。