6 Insert 路径解析
介绍完 Innodb 中 Btree 组织形式、搜索和并发控制策略，我们此时来看 Innodb 中 btree 是如何插入一条数据的。Innodb 在插入时需要对主键索引和二级索引分开考虑，先插入主键索引，再插入二级索引。
整个插入流程函数在 row_ins 中，插入前会先判断主键索引是否 unique（即是否定义主键），不是则会先分配 row id 来唯一标识一条 record。
无论主键索引还是二级索引，都需要先构建插入的完整行记录的内存版本（row，dtuple type），再基于 row 和各个索引（dict_index_t）的列信息构建真正需要插入索引中存储的版本（entry，dtuple type），进行 cursor 搜索定位到最后一个小于等于该 dtuple 的 rec_t 后，从 page 内部申请空间插入 entry 的内容。
6.1 主键索引的 insert 路径
主键索引的插入流程在 row_ins_clust_index_entry 函数中，先进行加锁范围更小的乐观插入流程，如果插入失败（page 空间不足），会进行悲观插入流程，加锁范围更大，并触发结点分裂流程，这也和 cursor 的乐观悲观搜索相对应。
控制乐观和悲观插入流程在 row_ins_clust_index_entry_low 中，根据 latch_mode 进行判断，每次都开启一个新的 mtr 流程，我们先看乐观插入:
- 先进行乐观 cursor 搜索 (BTR_MODIFY_LEAF)，定位到 leaf page 的 rec_t 中。
- duplicate check: 检查定位的 rec_t 是否和要插入的 entry 相等，存在重复，会将可能相等的 record 都加上事务锁（普通 insert 加 S lock，insert on duplicate key update 则加 X lock，gap mode 取决于事务隔离级别），保证不被其他事务修改。如果 rec_t 不是 delete mark，向上层返回 duplicate key 错误，如果是 delete mark，将插入流程转为 update-in-place 覆盖写入（row_ins_clust_index_entry_by_modify）。
- 否则进入乐观插入（btr_cur_optimistic_insert），首先会计算插入 entry 空间，先判断 page 中 free list 空间是否足够，free list 空间不够，再判断 page 中未分配的堆的空间，如果还是不够，会判断 reorganize page 后的空间（整理 page 内部的空间碎片），如果存在空闲空间，将 entry 内容 copy 到申请的 rec_t 中，并更新 rec_t 和 page 的元信息，否则会进行悲观插入。
- 真正插入 entry 前，会检查事务锁和记录 undo (btr_cur_ins_lock_and_undo)，检查事务锁 (lock_rec_insert_check_and_lock) 会判断 cursor 定位的下一个 rec_t 上当前有没有锁，有的话加上带有 gap 的插入意向的 X 锁（LOCK_X | LOCK_GAP | LOCK_INSERT_INTENTION ）的显示锁，来等待其他 gap 锁释放，确保要插入的区间没有其他事务访问。同时每一条 Insert 的 rec_t 上都默认有一个隐式锁，它是通过 trx_id 和当前活跃事务数组的 id 来检测的，这么做减少了 lock_sys 的操作，提升性能[6]。为了保证事务回滚，插入 entry 前会记录一条 insert 类型的 undo（trx_undo_report_row_operation），将 entry 的 key fields 写入 undo page 中，便于回滚时找到 record 的位置，并根据 undo page 的 id 和 offset 构建出回滚指针存入插入的 rec_t 中[7]。
- 在写入 entry 之后，会向 mtr 的 log buf 记录 redo log (page_cur_insert_rec_write_log)，用于 WAL 故障恢复，通常一条 insert 的 redo log 会记录 page 和 index 信息，以及和 cursor 定位的 rec_t 相比的差异部分（btree的有序特性，相邻的 record 相同部分较多，减少存储的 redo log 大小）：
(Page ID, offset) + (len of each field) + (extra info) + (bytes which differs from cursor record)
6.2 结点分裂
如果 cursor 搜索到的 leaf page 剩余空间不足以容纳待插入的 entry，会触发悲观插入流程，腾出插入的空间：
- 先进行悲观的 cursor 搜索流程，将涉及的 page 的 latch 都加上。
- 检查事务锁和记录 undo。
- 进行结点分裂，最后将 entry 插入到分裂后的 page 中，写 redo。
整个结点分裂过程在 btr_page_split_and_insert 中，如图 7 所示，主要是:
- 选择原 page 的分裂点 (split_rec)。 生成新 page，
- 将原 page 的部分 record list 批量 move 到新 page 中，这里会写 move 相关的 redo（包括原 page 的 delete 和新 page 的 insert）。
- 修改前后 page 的指针指向、在 parent page 新增一个 index record 指向新 page（触发新的插入流程）。
- 根据 entry 和 split_rec 的大小关系，将 entry 插入到原 page 或者新 page 中的一个。
图 7: 结点分裂流程
原 page 的分裂点的选择，为了性能考虑，Innodb 采用了两种策略[8]：
- 将原始页面中 50% 数据移动到新页面，这是最普通的分裂方法。
- 为了优化上述中间点分裂在顺序插入场景的问题，InnoDB 实现了在插入点分裂的方法，在每个 page 上记录上次插入位置 （PAGE_LAST_INSERT），以此判断本次插入是否递增或者递减，如果判定为顺序插入，就在当前插入点进行分裂。
6.3 二级索引的 insert 路径
前面介绍二级索引由主键索引的部分 value fields 作为 sk（secondary key），主键索引的 pk (primary key) 作为 value。二级索引的插入流程整体和主键索引相差不大，可以参考主键索引流程，但存在以下几个区别：
duplicate check：二级索引 unique 性质是由 sk 决定的，而和主键索引不同，二级索引覆盖一个 delete mark 的 rec_t，需要满足所有 fields 都相等（sk + pk），因此对于一个 unique 的二级索引，可能存在多个被 delete-mark 的相同 sk 不同 pk 的 rec_t，并且跨多个 page。在搜索时，为了保证 unique 性质，需要把所有被 delete-mark 的 rec_t 以及第一个 sk 不相同的 rec_t 都加上 next-key 锁（gap 锁加在下一个 rec），阻止其他事务插入相同的 sk 的 record 造成 unique 不一致。
由于插入都是以 PAGE_CUR_LE 模式插入，所以插入时候搜索会定位到最后一个相等 sk 的 rec_t 上，然而由于相等 rec_t 可能跨 page，为了符合加锁顺序，在 duplicate check 的时候，会把上一个 mtr 提交，开启一个以 PAGE_CUR_GE 模式的 cursor 搜索过程来加 gap 锁。
由于 gap 锁加了第一个与 sk 不相同的 rec_t，当这中间的 gap 很大时，会造成即使在 RC 隔离级别下，也会很容易发生死锁问题，也是官方遗留很多年的问题，这在文章 [9] 有很好的例子、解释以及方案讨论，感兴趣的可以仔细阅读。
二级索引不需要通过记录 undo 来支持事务回滚和 MVCC 一致性读。
7 总结
本文介绍了以下几个方面： btree 的背景、Innodb 中 btree 的组织形式，包括索引组织表逻辑形式以及 btree 索引页和记录的物理格式。接下来介绍了从 Innodb 中定位 record 的方法和如何保证 btree 的一致性，包括了 cursor 搜索逻辑和并发控制流程。最后介绍了 Innodb 整个 insert 路径，以及如何考虑其他模块如 事务锁、undo、redo、BP 等。btree 索引是数据库的核心，是直接操纵数据的模块，通过 btree 来看 Innodb，对整个数据库都会有更深层次的理解。
笔者也在学习过程，如有任何问题欢迎评论和私信进行指正和讨论。
8 引用
[1] POLARDB · B+树并发控制机制的前世今生.
[2] POLARDB · 敢问路在何方 — 论B+树索引的演进方向（上）.
[3] Modern B-Tree Techniques.
[4] InnoDB btree latch 优化历程
[5] MySQL innodb BLOB 演进与实现
[6] InnoDB 事务锁源码分析
[7] 庖丁解InnoDB之Undo LOG
[8] InnoDB B-tree 顺序插入优化及问题
[9] #issue 68021 MySQL unique check 问题
6 Insert 路径解析
介绍完 Innodb 中 Btree 组织形式、搜索和并发控制策略，我们此时来看 Innodb 中 btree 是如何插入一条数据的。Innodb 在插入时需要对主键索引和二级索引分开考虑，先插入主键索引，再插入二级索引。
整个插入流程函数在 row_ins 中，插入前会先判断主键索引是否 unique（即是否定义主键），不是则会先分配 row id 来唯一标识一条 record。
无论主键索引还是二级索引，都需要先构建插入的完整行记录的内存版本（row，dtuple type），再基于 row 和各个索引（dict_index_t）的列信息构建真正需要插入索引中存储的版本（entry，dtuple type），进行 cursor 搜索定位到最后一个小于等于该 dtuple 的 rec_t 后，从 page 内部申请空间插入 entry 的内容。
6.1 主键索引的 insert 路径
主键索引的插入流程在 row_ins_clust_index_entry 函数中，先进行加锁范围更小的乐观插入流程，如果插入失败（page 空间不足），会进行悲观插入流程，加锁范围更大，并触发结点分裂流程，这也和 cursor 的乐观悲观搜索相对应。
控制乐观和悲观插入流程在 row_ins_clust_index_entry_low 中，根据 latch_mode 进行判断，每次都开启一个新的 mtr 流程，我们先看乐观插入:
- 先进行乐观 cursor 搜索 (BTR_MODIFY_LEAF)，定位到 leaf page 的 rec_t 中。
- duplicate check: 检查定位的 rec_t 是否和要插入的 entry 相等，存在重复，会将可能相等的 record 都加上事务锁（普通 insert 加 S lock，insert on duplicate key update 则加 X lock，gap mode 取决于事务隔离级别），保证不被其他事务修改。如果 rec_t 不是 delete mark，向上层返回 duplicate key 错误，如果是 delete mark，将插入流程转为 update-in-place 覆盖写入（row_ins_clust_index_entry_by_modify）。
- 否则进入乐观插入（btr_cur_optimistic_insert），首先会计算插入 entry 空间，先判断 page 中 free list 空间是否足够，free list 空间不够，再判断 page 中未分配的堆的空间，如果还是不够，会判断 reorganize page 后的空间（整理 page 内部的空间碎片），如果存在空闲空间，将 entry 内容 copy 到申请的 rec_t 中，并更新 rec_t 和 page 的元信息，否则会进行悲观插入。
- 真正插入 entry 前，会检查事务锁和记录 undo (btr_cur_ins_lock_and_undo)，检查事务锁 (lock_rec_insert_check_and_lock) 会判断 cursor 定位的下一个 rec_t 上当前有没有锁，有的话加上带有 gap 的插入意向的 X 锁（LOCK_X | LOCK_GAP | LOCK_INSERT_INTENTION ）的显示锁，来等待其他 gap 锁释放，确保要插入的区间没有其他事务访问。同时每一条 Insert 的 rec_t 上都默认有一个隐式锁，它是通过 trx_id 和当前活跃事务数组的 id 来检测的，这么做减少了 lock_sys 的操作，提升性能[6]。为了保证事务回滚，插入 entry 前会记录一条 insert 类型的 undo（trx_undo_report_row_operation），将 entry 的 key fields 写入 undo page 中，便于回滚时找到 record 的位置，并根据 undo page 的 id 和 offset 构建出回滚指针存入插入的 rec_t 中[7]。
- 在写入 entry 之后，会向 mtr 的 log buf 记录 redo log (page_cur_insert_rec_write_log)，用于 WAL 故障恢复，通常一条 insert 的 redo log 会记录 page 和 index 信息，以及和 cursor 定位的 rec_t 相比的差异部分（btree的有序特性，相邻的 record 相同部分较多，减少存储的 redo log 大小）：
(Page ID, offset) + (len of each field) + (extra info) + (bytes which differs from cursor record)
6.2 结点分裂
如果 cursor 搜索到的 leaf page 剩余空间不足以容纳待插入的 entry，会触发悲观插入流程，腾出插入的空间：
- 先进行悲观的 cursor 搜索流程，将涉及的 page 的 latch 都加上。
- 检查事务锁和记录 undo。
- 进行结点分裂，最后将 entry 插入到分裂后的 page 中，写 redo。
整个结点分裂过程在 btr_page_split_and_insert 中，如图 7 所示，主要是:
- 选择原 page 的分裂点 (split_rec)。 生成新 page，
- 将原 page 的部分 record list 批量 move 到新 page 中，这里会写 move 相关的 redo（包括原 page 的 delete 和新 page 的 insert）。
- 修改前后 page 的指针指向、在 parent page 新增一个 index record 指向新 page（触发新的插入流程）。
- 根据 entry 和 split_rec 的大小关系，将 entry 插入到原 page 或者新 page 中的一个。
图 7: 结点分裂流程
原 page 的分裂点的选择，为了性能考虑，Innodb 采用了两种策略[8]：
- 将原始页面中 50% 数据移动到新页面，这是最普通的分裂方法。
- 为了优化上述中间点分裂在顺序插入场景的问题，InnoDB 实现了在插入点分裂的方法，在每个 page 上记录上次插入位置 （PAGE_LAST_INSERT），以此判断本次插入是否递增或者递减，如果判定为顺序插入，就在当前插入点进行分裂。
6.3 二级索引的 insert 路径
前面介绍二级索引由主键索引的部分 value fields 作为 sk（secondary key），主键索引的 pk (primary key) 作为 value。二级索引的插入流程整体和主键索引相差不大，可以参考主键索引流程，但存在以下几个区别：
duplicate check：二级索引 unique 性质是由 sk 决定的，而和主键索引不同，二级索引覆盖一个 delete mark 的 rec_t，需要满足所有 fields 都相等（sk + pk），因此对于一个 unique 的二级索引，可能存在多个被 delete-mark 的相同 sk 不同 pk 的 rec_t，并且跨多个 page。在搜索时，为了保证 unique 性质，需要把所有被 delete-mark 的 rec_t 以及第一个 sk 不相同的 rec_t 都加上 next-key 锁（gap 锁加在下一个 rec），阻止其他事务插入相同的 sk 的 record 造成 unique 不一致。
由于插入都是以 PAGE_CUR_LE 模式插入，所以插入时候搜索会定位到最后一个相等 sk 的 rec_t 上，然而由于相等 rec_t 可能跨 page，为了符合加锁顺序，在 duplicate check 的时候，会把上一个 mtr 提交，开启一个以 PAGE_CUR_GE 模式的 cursor 搜索过程来加 gap 锁。
由于 gap 锁加了第一个与 sk 不相同的 rec_t，当这中间的 gap 很大时，会造成即使在 RC 隔离级别下，也会很容易发生死锁问题，也是官方遗留很多年的问题，这在文章 [9] 有很好的例子、解释以及方案讨论，感兴趣的可以仔细阅读。
二级索引不需要通过记录 undo 来支持事务回滚和 MVCC 一致性读。
7 总结
本文介绍了以下几个方面： btree 的背景、Innodb 中 btree 的组织形式，包括索引组织表逻辑形式以及 btree 索引页和记录的物理格式。接下来介绍了从 Innodb 中定位 record 的方法和如何保证 btree 的一致性，包括了 cursor 搜索逻辑和并发控制流程。最后介绍了 Innodb 整个 insert 路径，以及如何考虑其他模块如 事务锁、undo、redo、BP 等。btree 索引是数据库的核心，是直接操纵数据的模块，通过 btree 来看 Innodb，对整个数据库都会有更深层次的理解。
笔者也在学习过程，如有任何问题欢迎评论和私信进行指正和讨论。
8 引用
[1] POLARDB · B+树并发控制机制的前世今生.
[2] POLARDB · 敢问路在何方 — 论B+树索引的演进方向（上）.
[3] Modern B-Tree Techniques.
[4] InnoDB btree latch 优化历程
[5] MySQL innodb BLOB 演进与实现
[6] InnoDB 事务锁源码分析
[7] 庖丁解InnoDB之Undo LOG
[8] InnoDB B-tree 顺序插入优化及问题
[9] #issue 68021 MySQL unique check 问题
