DSA数据结构与算法工程实践
关于
MySQL/InnoDB 聚簇索引

优先在叶页内插入，必要时再修改树结构

InnoDB 插入聚簇索引时先尝试叶页内修改；空间或布局条件不满足才重新以允许修改树结构的方式下降，执行分裂或根提升。

3b99be40f存储与数据放置核验 2026-10-12
相关概念
B / B+ 树

工程问题#

多数索引写入可能在已有叶页中完成。若每次插入都预先按分裂所需范围保护树结构，会增加同步开销；但页空间不足、压缩或预留空间约束又要求更广的结构修改。

实际实现#

row_ins_clust_index_entry 首先以 BTR_MODIFY_LEAF 调用底层插入；仅在返回 DB_FAIL 时改用 BTR_MODIFY_TREE 重试。btr_cur_optimistic_insert 检查页内可用空间和记录布局，必要时在同一页内重组；树修改路径仍先尝试页内插入，失败后才调用 btr_cur_pessimistic_insert，后者选择根提升或页分裂。

处理流程#

  1. 按索引键定位叶页，先采用 BTR_MODIFY_LEAF 的修改路径。
  2. 估算转换后的记录大小，检查重组后的空间、压缩约束与聚簇页的预留空间要求。
  3. 能在本页处理时进行记录锁检查、undo 记录及页插入；未压缩普通页必要时先重组再插入。
  4. 若结果为 DB_FAIL，上层重新以 BTR_MODIFY_TREE 下降；锁等待、重复键等其他结果不会都被当作分裂请求。
  5. 结构修改路径中再次尝试页内插入，仍失败才预留文件空间，并进行根提升或页分裂。

源码片段#

固定版本 · 原文摘录
storage/innobase/row/row0ins.cc3b99be40f8a31d9396cad10accfd3ba51647d613 · L3157–L3169
查看原文件
3157    err = row_ins_sorted_clust_index_entry(BTR_MODIFY_LEAF, index, entry, thr);3158  } else {3159    err = row_ins_clust_index_entry_low(flags, BTR_MODIFY_LEAF, index, n_uniq,3160                                        entry, thr, dup_chk_only);3161  }31623163  DEBUG_SYNC(thr_get_trx(thr)->mysql_thd,3164             "after_row_ins_clust_index_entry_leaf");31653166  if (err != DB_FAIL) {3167    DEBUG_SYNC_C("row_ins_clust_index_entry_leaf_after");3168    return err;3169  }
row_ins_clust_index_entry：叶页尝试

普通分支调用 BTR_MODIFY_LEAF，随后只有 DB_FAIL 会继续进入结构重试；其他返回值原样交给上层。片段首行属于 intrinsic 表的另一分支，本例分析 else。

CPPGPL-2.0-only（含文件头附加链接许可）
storage/innobase/btr/btr0cur.cc3b99be40f8a31d9396cad10accfd3ba51647d613 · L2770–L2790
查看原文件
2770  if (page_has_garbage(page)) {2771    if ((max_size < rec_size || max_size < BTR_CUR_PAGE_REORGANIZE_LIMIT) &&2772        page_get_n_recs(page) > 1 &&2773        page_get_max_insert_size(page, 1) < rec_size) {2774      goto fail;2775    }2776  } else if (max_size < rec_size) {2777    goto fail;2778  }27792780  /* If there have been many consecutive inserts to the2781  clustered index leaf page of an uncompressed table, check if2782  we have to split the page to reserve enough free space for2783  future updates of records. */27842785  if (leaf && !page_size.is_compressed() && index->is_clustered() &&2786      page_get_n_recs(page) >= 2 &&2787      dict_index_get_space_reserve() + rec_size > max_size &&2788      (btr_page_get_split_rec_to_right(cursor, &dummy) ||2789       btr_page_get_split_rec_to_left(cursor, &dummy))) {2790    goto fail;
btr_cur_optimistic_insert：空间与预留条件

先检查重组后是否能容纳新记录，还可能为聚簇索引后续更新预留空间。因而失败不只表示当前连续空闲区不足。max_size 在前文由 page_get_max_insert_size_after_reorganize 计算。

CPPGPL-2.0-only（含文件头附加链接许可）
storage/innobase/btr/btr0cur.cc3b99be40f8a31d9396cad10accfd3ba51647d613 · L2863–L2874
查看原文件
2863    /* If the record did not fit, reorganize */2864    if (!btr_page_reorganize(page_cursor, index, mtr)) {2865      ut_d(ut_error);2866      ut_o(goto fail);2867    }28682869    ut_ad(page_get_max_insert_size(page, 1) == max_size);28702871    reorg = true;28722873    *rec = page_cur_tuple_insert(page_cursor, entry, index, offsets, heap, mtr);2874
btr_cur_optimistic_insert：页内重组

这是普通未压缩页在首次插入未成功后的重组与重试分支。重组发生在同一页内，与申请新页并改变父子关系的分裂不同。

CPPGPL-2.0-only（含文件头附加链接许可）
storage/innobase/row/row0ins.cc3b99be40f8a31d9396cad10accfd3ba51647d613 · L3181–L3188
查看原文件
3181  if (index->table->is_intrinsic() && dict_index_is_auto_gen_clust(index)) {3182    err = row_ins_sorted_clust_index_entry(BTR_MODIFY_TREE, index, entry, thr);3183  } else {3184    err = row_ins_clust_index_entry_low(flags, BTR_MODIFY_TREE, index, n_uniq,3185                                        entry, thr, dup_chk_only);3186  }31873188  return err;
row_ins_clust_index_entry：树修改重试

叶页路径返回 DB_FAIL 后，普通表分支重新用 BTR_MODIFY_TREE 进入底层。它不是拿着原有叶页修改状态直接无条件分裂。

CPPGPL-2.0-only（含文件头附加链接许可）
storage/innobase/row/row0ins.cc3b99be40f8a31d9396cad10accfd3ba51647d613 · L2583–L2596
查看原文件
2583      DEBUG_SYNC_C("before_insert_pessimitic_row_ins_clust");25842585      err = btr_cur_optimistic_insert(flags, cursor, &offsets, &offsets_heap,2586                                      entry, &insert_rec, &big_rec, thr, &mtr);25872588      if (err == DB_FAIL) {2589        err =2590            btr_cur_pessimistic_insert(flags, cursor, &offsets, &offsets_heap,2591                                       entry, &insert_rec, &big_rec, thr, &mtr);25922593        if (index->table->is_intrinsic() && err == DB_SUCCESS) {2594          row_ins_temp_prebuilt_tree_modified(index->table);2595        }2596      }
row_ins_clust_index_entry_low：延迟调用分裂路径

即使已经采用树修改路径，仍先尝试 optimistic_insert；只有再次 DB_FAIL 才调用 pessimistic_insert，避免在条件变化后做不必要的结构修改。

CPPGPL-2.0-only（含文件头附加链接许可）
storage/innobase/btr/btr0cur.cc3b99be40f8a31d9396cad10accfd3ba51647d613 · L3017–L3027
查看原文件
3017  if (dict_index_get_page(index) ==3018      btr_cur_get_block(cursor)->page.id.page_no()) {3019    /* The page is the root page */3020    *rec = btr_root_raise_and_insert(flags, cursor, offsets, heap, entry, mtr);3021  } else {3022    *rec = btr_page_split_and_insert(flags, cursor, offsets, heap, entry, mtr);3023  }30243025  if (!*rec) {3026    return DB_OUT_OF_FILE_SPACE;3027  }
btr_cur_pessimistic_insert：根提升或页分裂

完成前面的锁、undo 与文件空间检查后，根据游标页是否为根页选择根提升或普通页分裂，并检查空间失败。具体分裂算法在 btr0btr.cc。

CPPGPL-2.0-only（含文件头附加链接许可）

六段原文连接上层重试、页内空间处理和结构修改分派；不把这几段当作完整事务提交或页分裂实现。各函数的 mini-transaction 与闩锁要求见相邻源码注释。

收益与取舍#

工程分析

带来的收益

  • 将常见的页内更新和较少发生的结构修改分开，减少不必要的树结构同步。
  • 先利用页内重组恢复可用空间，避免把每次局部插入失败都直接变成页分裂。
  • 由明确的 DB_FAIL 信号升级处理范围，使调用方可以区分结构重试和真正的其他错误。

付出的代价

  • 需要升级时会再次下降和检查，单次写入可能做重复工作。
  • 页分裂仍会带来页分配、记录移动与父层更新，缓冲池、日志和锁等待也影响实际延迟。
  • “乐观插入”仍持有页闩锁并可能检查记录锁、写 undo；它不是无锁算法，也不是数据库隔离级别中的乐观并发控制。

可比较的选择

一开始按结构修改路径下降可减少失败后的重试，但常见的页内插入也会承担更广的同步成本。

LSM-tree 写入缓冲先积累内存有序记录、再批量生成和合并磁盘文件，改变了写入方式；需承担读路径合并与后台整理成本，不能只比较一次页分裂。

版本与适用范围#

固定 MySQL 提交 3b99be40f8a31 的 InnoDB 普通聚簇索引插入分支。排除 intrinsic 表专用快速路径、空间索引和完整大字段页外存储流程。源码采用 B-tree 命名；这里分析的是数据库页组成的索引树，不是内存二叉搜索树。DB_FAIL 也可能源于压缩和预留空间策略，不能简单解释为物理页已经填满。

参考来源#

源码、官方文档与原始论文
01
mysql · row_ins_clust_index_entry / row_ins_clust_index_entry_low

storage/innobase/row/row0ins.cc · row_ins_clust_index_entry / row_ins_clust_index_entry_low

源码3b99be40f8a31d9396cad10accfd3ba51647d613
02
mysql · btr_cur_optimistic_insert / btr_cur_pessimistic_insert

storage/innobase/btr/btr0cur.cc · btr_cur_optimistic_insert / btr_cur_pessimistic_insert

源码3b99be40f8a31d9396cad10accfd3ba51647d613
03
mysql · btr_page_split_and_insert / btr_root_raise_and_insert

storage/innobase/btr/btr0btr.cc · btr_page_split_and_insert / btr_root_raise_and_insert

源码3b99be40f8a31d9396cad10accfd3ba51647d613

相关实现与比较#

2 个相关案例
SQLite·数据库文件与页version-3.46.0

用页式 B-tree 组织表与索引

SQLite 将表和索引组织成数据库页上的 B-tree，用一个节点容纳多个键，支持有序定位与范围遍历。

B / B+ 树
附源码片段 · 存储与数据放置
↑↓ 选择 Enter 打开Esc 关闭
9 个匹配案例