版本

  • MySQL 8.0.13

背景

InnoDB 使用 B+ 树作为它的索引数据结构, B+ 树作为一种经典的数据结构具备高效的读写查询, 本文主要分析 InnoDB 中 B+ 树对于 Record 的增删改如何实现, 理解 Record 在 InnoDB 中的 B+ 树如何增删改,可以更直观的帮助我们理解 InnoDB 的索引组织方式.

Record 的插入操作

在MySQL中, 一条 Insert 语句就是一个 Record 的插入操作, 我们以插入一条聚簇索引(非压缩)为例, 略过连接建立过程和 SQL parse 阶段, 经过 InnoDB 的 handler::ha_write_row() 调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 ------------
| ... |
------------
|
| /* Cluster Index 聚簇索引的插入 */
| ---------------------------------
--> | row_ins_clust_index_entry_low() |
---------------------------------
|
|
| /* 针对 delete-marked 的记录, 并且该记录的唯一字段和待插入的 Record 一致,则 Inplace Modify. */
| ---------------------------------------
--> | row_ins_clust_index_entry_by_modify() |
| ---------------------------------------
|
|
| /* 乐观插入 */
| -----------------------------
--> | btr_cur_optimistic_insert() |
| -----------------------------
| |
| |
| | /* 加锁并记录 Undo Log */
| | -----------------------------
| --> | btr_cur_ins_lock_and_undo() |
| | -----------------------------
| |
| | /* 插入b+树 */
| | -------------------------
| --> | page_cur_tuple_insert() |
| -------------------------
|
|
| /* 悲观插入 */
| ------------------------------
--> | btr_cur_pessimistic_insert() |
------------------------------

上述的调用过程说明了插入一条 Record 的过程, 具体的分析如下:

  • row_ins_clust_index_entry_low() 函数的参数包括我们需要插入的 Record 和当前的dict_index_t 索引. 首先我们需要通过pcur游标来定位我们需要插入的位置:

    1
    2
    3
    4
    /* 调用 btr_pcur_open() 定位待插入的位置.
    * 参数 entry 是待插入的 Record, search mode 是 PAGE_CUR_LE, 即定位到一个小于等于待插入记录的 Record.
    * 举例假如当前存在 Record 是[1, 2, 3], 我们插入5, 即 cursor 会定位到3. */
    btr_pcur_open(index, entry, PAGE_CUR_LE, mode, &pcur, &mtr);
  • 针对 cursor 返回的 Record 检查主键重复的问题.

  • 调用btr_cur_optimistic_insert()乐观插入:

    • 通过 cursor 定位 leaf page, 计算 Record 的物理长度.

    • 假如 Record 的大小超过了 Page 的剩余空间, 则乐观插入失败,需要调用悲观插入.

      • 对于乐观插入成功的情况下, 调用btr_cur_ins_lock_and_undo()记录 Undo Log.

      • 调用page_cur_insert_rec_low()完成 Page 的插入并记录类型为 MLOG_REC_INSERT 的 Redo Log.

  • 对于需要分裂的 Page 需要调用btr_cur_pessimistic_insert()悲观插入:

Record 的删除操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
  /* Record 删除操作. */
-------------------------
| ha_innobase::delete_row |
-------------------------
|
|
| /* Record 的更新删除操作都经过 row_update_for_mysql() 入口. */
| ------------------------
--> | row_update_for_mysql() |
------------------------
|
|
| ----------------------------------------
--> | row_update_for_mysql_using_upd_graph() |
----------------------------------------
|
|
|
| -----------
--> | row_upd() |
| ------------
|
| ----------------
--> | row_upd_step() |
----------------
|
|
| /* 加锁并记录 Undo Log */
| ------------------------------
--> | row_upd_del_mark_clust_rec() |
------------------------------
|
|
| /* 保存 Record 至 node-> row 用来删除二级索引. */
| ---------------------
--> | row_upd_store_row() |
| ---------------------
|
|
| /* 上锁, 记录 Undo Log, 设置 Record 的标志位为 REC_INFO_DELETED_FLAG. */
| ----------------------------------
--> | btr_cur_del_mark_set_clust_rec() |
----------------------------------

通过源码分析我们可以发现 Record 的删除操作对于聚簇索引并不是真的物理删除,仅仅是标记为 REC_INFO_DELETED_FLAG. 而对于其他的二级索引, 依然采用设置标记为的方法 (btr_cur_del_mark_set_sec_rec()).

Record 的修改操作

对于 Record 的修改操作, 使用了和删除操作一样的接口 row_upd_clust_step(). 对于修改存在多种不同的处理方法:

  1. 对于只修改聚簇索引,而无需修改二级索引的 Update 操作, 调用 row_upd_clust_rec(), 对于仅修改聚簇也存在两种情况: 是否存在 Record 长度的变化.

    • 对于 Update 后长度不变的 Record, 调用 btr_cur_update_in_place() 原地修改.

    • 对于 Update 后引起 Record 长度变化的操作, 依然会根据当前 Page 的剩余空间调用乐观更新(btr_cur_optimistic_update())和悲观更新(btr_cur_pessimistic_update()). 引起 Record 长度变化的 Update 操作都是 append 写入方式, 对于旧的 Record 需要更新其标志位, 插入 Page 的 PAGE_FREE 链表.

  2. 对于会影响排序的字段, 调用 row_upd_clust_rec_by_insert() 更新.

  3. 对于需要同时修改聚簇索引和二级索引的 Update 操作, 依然调用 row_upd_clust_rec() 完成. 与 一样会在使用 row_upd_store_row() 记录旧的 Record 至 row->node, 以供二级索引更新使用.

  4. 对于二级索引的修改操作,全部采用标记删除后重新插入的方式.

总结

我们通过源码分析了 InnoDB 中关于索引部分的增删改步骤, 需要注意的是 B+ tree 中的增删改流程全部处于同一个 trx 的保护中,因此对于聚簇索引和二级索引的修改都保证了原子性, 这里也涉及 InnoDB 的 Undo Log 模块和事务锁系统模块.