版本
- 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()，以一个中间 record 进行分裂。
B+ tree 的分裂
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 锁；释放 page 的 s 锁，释放顺序是从上至下。
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 涉及的 page.
- 对于路径上不会发生 SMO 的 page 全部都释放。
- 最后针对路径可能涉及 SMO 的所有 page 加 X 锁。
- SMO 过程中保留dict_index_t 的 sx 锁和可能涉及 SMO 的 page 的 x 锁。
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.
merge 的过程中可能造成 non-leaf level 的 node ptr 被删除，如果向左 merge，则保留左边 page 的 node ptr；如果向右 merge，则保留当前 page 的 node ptr，删除右边 page 的 node ptr.
所以 InnoDB B+ tree 中的 node ptr 都是小于等于下层 page 的最小的 user record (小于的情况是因为可能存在下层的最小的 user record 被删除的情况，在标记为 DELETE MARK 的场景里并不会直接更新 node ptr).
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 模块和事务锁系统模块。