InnoDB 中的 B+ 树的增删改

版本

• 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() 调用:

 ------------
|    ...     |
 ------------
   |
   |    /* 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游标来定位我们需要插入的位置:

  /* 调用 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()悲观插入:

B+ tree 的加锁流程

• 乐观插入

乐观插入使用的 mode 为 BTR_MODIFY_LEAF, 加锁顺序是先对 dict_index_t 加 S 锁, 再针对所有的 non-leaf page 加 S 锁, 因为需要对 leaf page 进行修改，所以对 leaf page 加 X 锁.

row_ins_clust_index_entry_low(flags, BTR_MODIFY_LEAF, index, n_uniq,
                              entry, thr, dup_chk_only);

• 悲观插入

悲观插入使用的 mode 为 BTR_MODIFY_TREE, 加锁顺序是先对 dict_index_t 加 SX 锁, 在 search 过程中不会针对 page 加任何锁(RW_NO_LATCH), 但会保留整个 branch 涉及的 block, 最后针对路径涉及的所有 block 加 X 锁.

row_ins_clust_index_entry_low(flags, BTR_MODIFY_TREE, index, n_uniq,
                              entry, thr, dup_chk_only);

Record 的删除操作

  /* 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 模块和事务锁系统模块.