PolarDB-X DN InnoDB B+ tree
结构及记录操作详解

本文将详细介绍 InnoDB 中的 B 树数据结构以及对这些树中的记录执行的各种操作。B 树是 InnoDB 的基础，因为它构成了所有索引的基础，能够以对数时间复杂度
提供高效的数据访问。

介绍

InnoDB 使用 B+ 树作为其所有索引的底层数据结构。B+ 树是平衡树结构，其中：

• 所有数据记录存储在叶节点中
• 内部节点仅包含键和指向子节点的指针
• 叶节点在双向链表中链接在一起，以实现高效的顺序访问
• 树的高度保持平衡，确保对数搜索时间

在InnoDB中，有两种类型的索引：

• 聚集索引 - 将实际数据记录存储在叶节点中
• 二级索引 - 存储索引字段值以及对应的指向聚集索引的主键值

B 树为搜索、插入和修改数据库记录提供了高效的操作，同时在并发操作期间保持结构完整性。

页面结构

在 InnoDB 中，B 树由页面组成，页面是存储和组织的基本单位。

页面类型和组织

InnoDB 表空间中的页面在 B 树结构中具有不同的用途：

• 索引页（包含 B 树节点）
• 根页面
• 内部节点（非叶节点）
• 叶节点
• 系统页面（包含元数据）
• undo日志页
• Blob 页面（用于页外存储）

每个页面都有标准大小（默认通常为 16KB）并遵循特定格式：

记录格式

页内的记录以特定格式组织，旨在实现高效的存储和检索。InnoDB 支持多种行格式：

COMPACT/DYNAMIC（最常用）的记录格式包括：

对于聚集索引记录，系统字段包括：

• 事务 ID (TRX_ID) - 标识最后修改记录的事务
• 回滚指针（ROLL_PTR） - 指向此记录对应的undo日志条目
• 行 ID（DB_ROW_ID） - 仅当表没有主键时使用

B树操作

搜索

在 B 树中搜索涉及从根到叶节点的遍历：

搜索操作在btr_cur_search_to_nth_level()
中实现，其中：

• 从根页面开始，并将搜索键与页面中的键进行比较
• 根据比较结果，指向子页面的适当指针
• 继续，直到到达叶子页
• 将游标定位在匹配记录或最接近的位置
• 返回记录或位置信息

插入

记录插入遵循以下步骤：

InnoDB 实现了两种插入算法：

• 乐观插入（btr_cur_optimistic_insert()
  ）- 尝试插入而不锁定整个树
• 悲观插入（btr_cur_pessimistic_insert()
  ）- 获取必要的锁以确保操作成功

如果页面已满，则会发生页面拆分：

• 分配新页面
• 记录分布在原始页面和新页面之间
• 使用适当的键和指针更新父节点
• 记录被插入到适当的页面

删除

记录删除涉及：

与插入类似，InnoDB 实现了乐观和悲观的删除算法：

• 乐观删除（btr_cur_optimistic_delete()
  ）- 无需锁定的简单情况
• 悲观删除（btr_cur_pessimistic_delete()
  ）— 需要锁的复杂情况

当页面变得太空时，它们可能会与兄弟页面合并以保持树的效率。

更新

记录更新更为复杂，因为它们可能会改变记录的物理位置：

InnoDB 执行两种类型的更新：

• 就地更新 - 当更改不影响排序或记录大小时
• 删除-插入更新 - 当更改影响排序或显著改变记录大小时

记录操作

记录创建和修改

更高级别的记录操作在 Row 模块中实现：

这些操作包括：

• 行插入（row_ins_step()
  ）- 在聚集索引和二级索引中创建新记录
• 行更新（row_upd_step()
  ）- 修改现有记录
• 行删除(row_del_mark_step()
  ) - 将记录标记为已删除

每个操作都会经历几个阶段：

• 获取并发控制的锁
• 验证约束
• 更新索引
• 事务日志

多版本并发控制（MVCC）

InnoDB 实现 MVCC 以允许并发读写操作：

MVCC 确保：

• 读事务可以看到数据库的一致快照
• 写入不会阻止读取
• 并发事务之间的隔离

可见性检查将记录的事务 ID 与读取视图(快照信息)
的事务信息进行比较，以确定记录版本是否对当前事务可见。

优化

插入缓冲区（更改缓冲区）

插入缓冲区（ibuf）优化了二级索引操作：

插入缓冲区：

• 通过批量修改二级索引来减少随机 I/O
• 将操作存储在特殊的 B 树中
• 在目标页面加载时或在后台处理期间合并更改
• 处理插入、删除和更新操作

缓冲池交互

B 树操作与缓冲池交互以进行内存管理：

缓冲池：

• 将经常访问的页面缓存在内存中
• 实现改良的 LRU 页面替换算法
• 管理脏页（已修改的页面），直到它们被刷新到磁盘
• 使用刷新列表, 用年龄跟踪修改的页面

高级主题

页面拆分和合并算法

通过页面分裂和合并维持B树平衡：

这些操作确保：

• B树保持最佳高度
• 页面不太空或太满
• 树保持平衡以实现高效访问

拆分和合并是事务性的，并采用锁以确保并发操作期间的一致性。

MVCC (记录版本控制)

InnoDB 实现记录版本控制以实现事务隔离：

当记录被修改时：

• 当前版本存储在undo日志中
• 记录就地更新或被替换
• 回滚指针指向上一个版本
• 事务ID更新为当前事务

然后，事务可以根据其读取视图(快照信息)访问适当的版本。

小结

InnoDB 的 B 树实现构成了其存储和索引功能的基础。B 树操作、记录管理和缓冲池交互之间的复杂相互作用使 InnoDB 能够在保持事务完整性的同时提供高效的数据访问。

了解这些机制对于使用 InnoDB 优化性能和解决问题的数据库管理员和开发人员至关重要。