InnoDB 关于 B+ tree 的整理

版本

MySQL 8.0.25

背景

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

B+ tree 的插入操作

在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.

B+ tree 的悲观插入

对于需要分裂的 Page 需要调用btr_cur_pessimistic_insert(), 悲观插入会对 B+tree 进行分裂操作:

如果插入点在 Page 的最后, 则尝试分裂btr_insert_into_right_sibling().
如果插入点为顺序插入, 即待插入的位置位于 PAGE_LAST_INSERT 之后, 则直接在当前插入点向后(FSP_UP)分裂 btr_page_get_split_rec_to_right().
如果插入点为递减插入, 即待插入的位置位于 PAGE_LAST_INSERT 之前, 则直接在当前插入点向前(FSP_DOWN)分裂 btr_page_get_split_rec_to_left().
如果插入位置都不位于 PAGE_LAST_INSERT 左右, 则直接进行中间点分裂 page_get_middle_rec(), 以一个中间 reocrd 进行分裂.

B+ tree 的加锁流程

乐观插入

乐观插入使用的 mode 为 BTR_MODIFY_LEAF, 加锁顺序:

先对 dict_index_t 加 S 锁.
查找过程中针对所有的 non-leaf page 加 S 锁, 因为需要目标 leaf page 进行修改，所以对 leaf page 加 X 锁.
到达 leaf level 层后(height == 0), 开始释放 lock: 释放 dict_index_t 的 s 锁;释放所有上层除了 root page 以外其他 page 的 s 锁, 保留 root page 的 s 锁.

1 2	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 锁.

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

BTR_MODIFY_TREE 涉及 B+ tree 的 SMO 操作, 因为 dict_index_t 的 SX 锁的互斥关系, 所以在一个索引 B+tree 上, 同时只能有一个 SMO 操作.

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()).

B+ tree 的悲观删除

InnoDB 中 B+ tree record 的删除操作由 purge 线程来处理, 用户的删除标记为 delete mark 以后, 由 purge 线程来后台清理 record 所占用的空间, purge 的流程为先使用乐观删除, 即待清理 record 的空间回收以后不会发生 SMO 操作, 但是以下条件会判断是否需要进行悲观删除:

ibool btr_cur_can_delete_without_compress(
    btr_cur_t *cursor, /*!< in: btr cursor */
    ulint rec_size,    /*!< in: rec_get_size(btr_cur_get_rec(cursor))*/
    mtr_t *mtr)        /*!< in: mtr */
{
  page_t *page;

  ut_ad(mtr_memo_contains(mtr, btr_cur_get_block(cursor), MTR_MEMO_PAGE_X_FIX));

  page = btr_cur_get_page(cursor);

  /* 是否需要 SMO(merge) 操作
   * 1. 删除这条 record 后该 Page 的剩余空间小于 50%(DICT_INDEX_MERGE_THRESHOLD_DEFAULT).
   * 2. 或者 Page 的前后节点均为 FIL_NULL. (代表这一层只有一个 Page, 没有保留的必要了)
   * 3. 或者 Page 的 user records 数量小于 2. */
  if ((page_get_data_size(page) - rec_size <
       BTR_CUR_PAGE_COMPRESS_LIMIT(cursor->index)) ||
      ((btr_page_get_next(page, mtr) == FIL_NULL) &&
       (btr_page_get_prev(page, mtr) == FIL_NULL)) ||
      (page_get_n_recs(page) < 2)) {

	/* 判断是否为 root page. */
    return (dict_index_get_page(cursor->index) == page_get_page_no(page));
  }

  return (TRUE);
}

悲观删除btr_cur_pessimistic_delete():

对于只剩下一个 Record 且不是 Root Page 的情况, 需要直接删除 Page(btr_discard_page()).
删除的 Record 是 Page 上的第一个, 需要更新父节点的 node ptr.
- 在父节点层更新 node ptr, 也通过悲观删除(btr_cur_pessimistic_delete()) 递归删除.
- 使用 next_rec 重新构建一个 node ptr 插入父节点.
其余的情况直接调用 btr_cur_compress_if_useful() 尝试合并 Page.
- 针对不存在左右节点的 Page, 即代表该层只有这一个 Page, 将 record 合并到父节点.
- 存在左右 Page 的情况下, 首先尝试与左节点 merge, 如果无法与左 Page 合并, 则尝试与右 Page 合并.
- 合并的流程均为拷贝需要释放的 Page 上的 record 至 merge Page 上, 更新左右 Page 指针, 删除 Page 所指向的 node pointer, 更新删除的 Page 上原有的 lock (table lock, record lock) 至 merge Page 上.
- 调用 btr_page_free() 将 Page 放回 segment 的 free list.
- 被删除的 Page 的 node pointer 在删除时可能会导致父节点也发生 merge 操作, 所以可能出现递归 merge 的情况, 在获取 node pointer 时使用的 BTR MODE 是 BTR_CONT_MODIFY_TREE.

Record 的修改操作

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

对于只修改聚簇索引，而无需修改二级索引的 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 链表.

对于会影响排序的字段, 调用 row_upd_clust_rec_by_insert() 更新.
对于需要同时修改聚簇索引和二级索引的 Update 操作, 依然调用 row_upd_clust_rec() 完成. 与一样会在使用 row_upd_store_row() 记录旧的 Record 至 row->node, 以供二级索引更新使用.
对于二级索引的修改操作，全部采用标记删除后重新插入的方式.

总结

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