MySQL源码学习(四):从insert看btr

举报
爱咬人的猫 发表于 2018/02/11 19:11:29 2018/02/11
【摘要】 Btr: B+ Tree,是innodb的核心数据结构,它作为数据的索引,让数据库能够快速找到指定的数据。B+ Tree的相关说明网上已经很多,本文通过insert操作的调用栈,来分析btr的操作过程。· Btr操作在insert的哪个过程中被调用?图1 insert的函数调用栈(btr部分)图1是一次insert操作打印的trace日志。大家可以看到第一行write_record

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

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

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

image.png

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

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

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

·         row_ins

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

image.png

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_LEPAGE_CUR_GEInsert使用PAGE_CUR_LE这种方式进行搜索。

 

·         分配index

image.png

3 index的获取

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

·         插入数据

image.png

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函数中的流程:

image.png

5 获取btr中的cursor

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

image.png

6 btr_pcur_get_btr_cur宏定义

·         pcurcursor的关系

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

image.png

7 btr_pcur_t依赖于btr_cur

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

image.png

8 通过cursor拿到page

请看图9中的btr_cur_optimistic_insert方法:

image.png

9 数据的插入

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

image.png

10 插入流程

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

 


【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。