Innodb 中的 Btree 实现 (一) · 引言 & insert 篇
最新回答
吥荟吢庝
2021-12-25 13:59:00
Innodb 中的 Btree 实现 (一) · 引言 & insert 篇
Innodb 中的 Btree 实现 (二) · select 篇
本文内容基于 MySQL Community 8.0.13 Version
1 背景
Btree 结构是关系型数据库的核心数据组织形式，通过多路分叉实现数据范围的逐级缩小，显著提升数据查找效率。在数据库操作中，如插入、删除、更新等，Btree 的基础操作已有详尽文献介绍。面对高并发与事务处理场景，Btree 索引需考虑数据一致性与事务的 ACID 特性。本文深度解析 Innodb 引擎中 Btree 的实现，聚焦于高并发环境下的数据与结构一致性，以及事务处理的细节。
2 索引组织表 (IOT)
Innodb 采用行存储引擎，每条记录对应数据库表的一行数据，包含自定义字段与隐式字段。主键索引（或聚集索引）以记录的前若干字段为键，其余字段为值，构成数据组织的核心。对于二级索引，利用主键索引的值作为键，构造新的索引结构，以主键索引的键作为值，避免全表扫描，提升查询效率。
3 索引页和行结构
数据库操作最终通过磁盘文件访问实现，Innodb 的 Btree 结构由页组成，每页固定大小（默认16KB）。主键索引的键和值存储在叶子结点，非叶子结点存储子节点键的最小值及页号。页面包含元信息、索引元信息、记录空间及目录槽空间，记录格式分为 Compact 和 Redundant，其中 Compact 格式是 MySQL 5.1 之后的默认格式。
4 cursor 搜索
通过 SQL 指令操作数据，MySQL server 层解析后传递给 innodb 引擎，使用 dtuple 格式转换用户记录。通过 cursor 搜索定位记录的物理位置，根据搜索模式、并发控制的加锁模式及操作行为，进行高效定位与操作。
5 并发控制
并发控制策略对于 OLTP 系统至关重要，保证 Btree 结构的一致性。innodb 中的页面操作封装在 mini-transaction（mtr）中，操作过程中将访问的页指针、请求的锁 latch 及产生的 redo log 记录。提交 mtr 时，redo log 同步到全局日志缓冲，脏页加入刷新队列，释放 latch，确保修改原子性。
6 Insert 路径解析
Innodb 插入数据时，先插入主键索引，再插入二级索引。整个流程涉及页分配、行记录构建、索引构建、页分裂等步骤。主键索引插入遵循乐观与悲观策略，二级索引插入需考虑 unique 性质与跨页范围的锁定。
7 总结
本文全面介绍了 Innodb Btree 的组织形式、搜索策略、并发控制机制及插入路径。通过理解 Btree 在 Innodb 中的角色，可以深入掌握数据库底层原理与优化技巧，提升数据操作的性能与一致性。
热门标签
