【华为云MySQL技术专栏】InnoDB B+树页面分裂与合并:物理结构、机制与优化
1、背景介绍
高效管理动态数据是数据库的核心挑战之一。MySQL InnoDB引擎通过页面分裂和页面合并两大关键机制来动态调整存储结构,不仅能确保数据的逻辑完整性和逻辑顺序正确,还能保证数据库的整体性能。这些机制发生于InnoDB的B+树索引结构内部,其具体操作是:
页面分裂:当已满的索引页无法容纳新记录时,创建新页并重新分配记录。
页面合并:当页内记录因删除/更新低于阈值时,与相邻页合并以优化空间。
深入理解上述机制至关重要,因为页面的分裂与合并将直接影响存储效率、I/O模式、加锁行为及整体性能。因此,本文将聚焦页面分裂与合并的实现机制、详细性能影响分析、优化策略来展开阐述。
2、InnoDB B+树结构及其物理存储
要深入理解页面分裂与合并机制,必须首先掌握其作用的数据结构-B+树,并理清该逻辑结构如何映射到磁盘的物理存储。
2.1 逻辑结构
除空间索引(Spatial Index)和全文索引(Fulltext Index)外,InnoDB所有索引均采用B+树数据结构来实现。该结构的核心优势在于:
1.节点大小固定:与InnoDB页(默认16KB)严格对齐。
2.对数级检索复杂度:时间复杂度为O(log N) 。
3.可预测的磁盘IO:最大磁盘访问次数仅由树深度决定。
核心结构如下:
-
聚簇索引(主键索引)
1.表数据按主键(PK)排序存储在B+树中。
2.叶节点包含完整行数据(即数据即索引)。
-
树层级组件
1.根页(Root Page):索引树的唯一入口。
2.非叶子节点(Non-Leaf Pages):根页与叶页之间的中间节点,不存储行数据,仅存储键值与下层页指针。
3.叶子节点(Leaf Page):
存储实际索引记录(树的最低层Level 0)。
通过FIL_PAGE_PREV/FIL_PAGE_NEXT构成双向链表,支持高效范围扫描。
图1 B+树组织结构
2.2 物理存储
InnoDB的B+树是通过多层结构映射在磁盘上的,从它的逻辑存储结构来看,所有数据都被有逻辑地存放在一个空间中,这个空间就叫做表空间(tablespace)。表空间由段(segment)、区(extent)、页(page)组成。
● 表空间(Tablespaces)
👉表空间是一个逻辑容器,表空间存储的对象是段,在一个表空间中可以有一个或多个段。
👉独立表空间(.ibd文件):innodb_file_per_table=ON时,每个表数据及索引存储在单独的.ibd文件中。
● 段(Segment)
👉每个B+树索引使用两个独立段:
索引段:非叶子节点部分;
数据段:叶子节点部分。
👉分离数据段和索引段维护了存储数据的叶节点的物理连续性。
● 区(Extent)
👉区是页的集合,一个区包含64个物理连续的页,默认大小为 1MB (64*16K,页大小可以通过innodb_page_size配置)。
👉空间分配以区为单位进行。
● 页(Page)
👉基础I/O单元(默认16KB,通过innodb_page_size配置)。
👉所有类型的页结构都包含文件头(File Header,38字节)和文件尾(File Tailer,8字节),文件头记录页号、类型、checksum值和LSN等关键元数据信息。
3、页面分裂机制
当页达到填充上限时会触发分裂,主要场景是:
插入满页(INSERT):新记录需按序插入但页面空闲空间不足。
更新扩容(UPDATE):更新存量记录,数据长度增加导致页无法容纳(如VARCHAR填充)。
3.1 分裂流程
1.满页判定:目标页(叶/内部页)无法容纳新记录。
2.新页分配:从表空间对应段分配空闲页(优先使用碎片区,必要时分配新区)。
3.分裂点选择:按键值顺序选择记录,目标为近似均分数据。
4.记录重分配:
分裂点后记录迁移至新页。
触发分裂的记录按序插入原页或新页。
5.指针更新:
-
页指针(双向链表):新页插入到B+树相应层的双向链表中,调整原页、新页、相邻页的FIL_PAGE_PREV/NEXT,维护双向链表。
-
父页指针(非叶节点):
👉在父页插入新页的最小键值及页指针。
👉若父页满则递归触发分裂(直至根页)。
伪代码核心逻辑(简化版):
FUNCTION btr_page_split_and_insert(cursor,tuple, mtr):
//1. 尝试将记录插入到右页面
rec= btr_insert_into_right_sibling(cursor, tuple, mtr);
IF rec != nullptr
return rec;
END IF
//2. 确定如何分裂当前页面
split_point_record, insert_tuple_on_left_page =determine_split_point_and_side(cursor, tuple)
//3. 分配新页面
new_page = allocate_new_btr_page(index, mtr)
initialize_new_page(new_page)
//4. 调整B+树结构
link_pages_in_tree(current_page, new_page, split_point_record,split_direction, mtr)
//5. 从分裂点将当前页面的记录移动到新页面
left_block, right_block = move_records_between_pages(current_page,new_page, split_point_record, mtr)
//6. 确定新纪录插入位置
IF insert_tuple_on_left_page THEN
target_block= left_block
ELSE
target_block = right_block
END IF
//7. 插入记录
position_cursor_for_insert(page_cursor, target_block, tuple)
inserted_record = insert_tuple_on_page(page_cursor, tuple, mtr)
RETURN inserted_record
END FUNCTION
3.2 顺序插入 vs 随机插入
-
严格按照降序或者升序插入时,插入操作始终发生在最左页或者最右页。
-
触发页面分裂时,仅迁移少量记录(甚至只涉及新纪录),原页维持满页状态,后续从新页插入。
-
页填充率高(~15/16),分裂频率低,物理上更有序。
随机插入(如UUID主键或者Hash主键)
-
随机插入可以发生在任何一个页面位置,触发页面分裂。
-
当页面分裂发生在树中部,页面记录近似50%需要移动。
-
页填充率低(~50%),页面分裂频繁,因此会进一步加剧页面内外部碎片化问题,详见5.1的解释。
插入模式从根本上决定了页分裂频率、存储密度(页填充率)以及索引碎片化程度。顺序键插入(如AUTO_INCREMENT)在降低分裂频率与维持高存储密度方面具有显著优势。
4、页面合并机制
页面合并是页面分裂的互补操作,通过页面合并可以释放低填充页占用的物理存储,提升页内有效数据占比。当页内记录占比低于合并阈值(MERGE_THRESHOLD,默认50%)时会触发合并,主要场景是:
删除(DELETE):物理删除记录并释放页面内空间(delete操作仅标记记录删除,最终由Purge线程清除标记记录后,实际回收空间)。
更新缩容(UPDATE):更新导致的记录物理长度降低时(如VARCHAR从100→10字节)降低页面填充率。
4.1 合并流程
1.低填充判定:当可能降低页填充率的DML操作(如DELETE或UPDATE缩容)执行后,InnoDB会检测受影响页的填充率(Fill Factor)是否低于MERGE_THRESHOLD阈值。
2.相邻页检查:当页的填充率低于阈值,InnoDB会通过FIL头部的FIL_PAGE_PREV和FIL_PAGE_NEXT指针来定位相邻页。
3.合并条件验证:InnoDB检查是否触发页面合并需满足当前页填充率 < MERGE_THRESHOLD(默认50%),且任一邻居页有足够空间容纳当前页记录。
4.记录迁移:满足页面合并条件后,目标页记录按序迁移至邻居页。
5.页释放:迁移完成后释放空页。
空页归还表空间,更新XDES位图或段空闲区链表。
6.指针更新:
页指针:调整相邻页的FIL_PAGE_PREV/NEXT绕过释放页。
父页指针:移除父页中对释放页的指针,若父页删除条目后页面填充率低于MERGE_THRESHOLD阈值则递归触发合并。
伪代码核心逻辑:
FUNCTION btr_compress(cursor, adjust_cursor,mtr):
//1. 页面当前层只有一个页面的场景,考虑和父节点合并
IF CURSOR_PAGE_IS_ONLY_CHILD_ON_LEVEL(cursor) THEN
merged_into_block = LIFT_CURSOR_PAGE_CONTENT_TO_PARENT(cursor, mtr)
IF adjust_cursor THEN
REPOSITION_CURSOR(cursor, merged_into_block,original_record_position_info)
END IF
RETURN true
END IF
//2. 检查相领页是否满足合并条件
merge_target_sibling, merging_with_left =FIND_MERGEABLE_SIBLING_FOR_CURSOR_PAGE(cursor, mtr)
IF merge_target_sibling IS NULL THEN
RETURN false // No suitable sibling
END IF
// (保存记录的原始位置信息)
IF adjust_cursor THEN
original_record_info = GET_RECORD_INFO_FOR_CURSOR_ADJUSTMENT(cursor)
END IF
//3. 将全部记录迁移到合并页面
MOVE_ALL_RECORDS_TO_SIBLING(cursor_page, merge_target_sibling,merging_with_left, mtr)
// (保存记录的原始位置信息)
IF adjust_cursor THEN
original_record_info = GET_RECORD_INFO_FOR_CURSOR_ADJUSTMENT(cursor)
END IF
//4. 调整父节点指针
UPDATE_PARENT_AFTER_MERGE(cursor_page, merge_target_sibling,merging_with_left, mtr)
//5. 释放页面
FREE_ORIGINAL_CURSOR_PAGE(cursor_page, mtr)
//6. 重新定位游标位置
IF adjust_cursor THEN
ADJUST_CURSOR_POSITION_IN_MERGED_PAGE(cursor,merge_target_sibling, original_record_info, merging_with_left)
END IF
4.2 效果与局限
5、性能影响
页面分裂/合并是InnoDB非常重要的操作,但是当其频繁触发或者效率低时,也会对数据库性能带来较大的负面影响。
5.1 索引碎片化
内部碎片:页面分裂和合并都会带来页内空间的浪费,随机插入触发分裂会导致50%的填充率,合并阈值限制会导致删除操作的残留碎片不能马上回收。低密度页会导致磁盘空间膨胀以及较低的缓冲池利用率。
外部碎片:页面分裂时新页随机分配会破坏物理连续性,页面合并时释放页会加剧物理离散性,导致逻辑连续的页在磁盘物理位置上离散,范围扫描性能劣化。
图2 外部碎片化例子
5.2 I/O操作增加
读放大:内部碎片化会导致需要更多页来存储相同数据,从而增加读页数。
随机I/O:外部碎片化会打破页面的物理连续性,影响InnoDB的预读(Read-Ahead)效率,原本的顺序扫描也将退化为随机IO。
5.3 缓冲池效率下降
内存浪费:由于碎片页与高密度页占用的缓冲池槽位相同,因此当碎片页过多时,会导致缓冲池内大量的页面空间是空闲状态,实际缓存的有效数据较少。
命中率降低:页内碎片化会使相同的数据量需要缓存更多的页面,而内存浪费会导致更多的磁盘读取操作,从而导致缓冲池页面的频繁换入换出。
5.4 锁竞争
分裂/合并需短暂持有闩锁(Latch),但高并发写入时可能会引发竞争。
6、优化策略
针对页分裂与合并的性能影响,尤其是碎片化问题,在实际业务使用中可以通过以下几个优化策略来降低负面影响。
6.1 主键设计优化
主键的选择是影响分裂和合并行为以及由此产生的碎片化的最重要因素。
优先顺序键:业务逻辑允许的前提下,最优先选用能生成顺序或单调递增值的字段类型作为主键。典型实现是在INT或BIGINT列上使用AUTO_INCREMENT属性。顺序插入能最大限度降低页分裂频率并维持高填充率(约15/16),提高范围扫描效率。
避免随机键:若系统对性能敏感,尽量避免采用基于随机值的主键,如UUIDv4或哈希主键,随机插入可能会比顺序键场景更频繁触发更多页面的分裂,从而导致内部及外部碎片化严重。
有序UUID替代方案:分布式系统等必须使用UUID时,采用以下优化策略降低影响:
-
使用时序UUID,如UUIDv1(基于时间戳+MAC地址)、UUIDv6(UUIDv1(基于时间戳+MAC地址)、UUIDv7(Unix时间戳毫秒+随机数)
-
优化存储并使用字节重排技术,如以BINARY(16)存储并重排字节(将时间戳前置)。
有序UUID是性能妥协方案而非完美解决方案,其效果虽然显著优于完全随机键,但仍无法达到纯自增主键的性能水平。
6.2 调整innodb_fill_factor
作用:控制索引在创建或重建过程(DDL添加索引或者重建索引操作)中的页填充百分比。
代价:会导致页的初始密度低,范围扫描初始性能下降,空间使用膨胀。
适用场景:预期重建后存在高频随机DML操作的表,可以延缓页面首次分裂。
默认行为:未指定时,叶页初始化填充率为100%,能使存储密度最大化,仅保留InnoDB默认强制预留的1/16空间。这种情况适用于以顺序插入为主(如AUTO_INCREMENT表)或重建后只读或低频更新的表。
6.3 表重组
对于有随机主键或者高频DML的表,长期运行会导致碎片化严重,因此定期对表做重建操作以恢复性能是非常重要的。
命令:
o OPTIMIZE TABLE
o ALTER TABLE ... ENGINE=InnoDB
o ALTER TABLE ... FORCE
效果:重建表及其索引,按序生成紧凑页,尽可能的保证新的.ibd文件内页面物理有序,从而消除内部及外部碎片。
在线工具:大表重建操作可能导致持锁时间较长,尤其对老版本MySQL或者ALTER TABLE 使用ALGORITHM=COPY算法这类场景,可以使用Percona Toolkit的pt-online-schema-change或开源社区GitHub里的gh-ost来降低重建表时的锁影响。
6.4 行格式选择
行格式(ROW_FORMAT)的选择也会直接影响页面分裂的频率,尤其对BLOB、 TEXT、 long VARCHAR等大字段类型的列。
DYNAMIC、COMPRESSED:将大字段(BLOB/TEXT)完全存储到溢出页,B+树页仅存20字节指针,减少因更新大字段引发的页面分裂。
COMPACT、REDUNDANT:B+树页存储大字段前缀(≤768字节)以及剩余记录所在溢出页指针,当字段前缀频繁更新时易触发分裂。
因此,如果业务频繁更新BLOB、TEXT、超长VARCHAR等类型的数据,建议使用ROW_FORMAT=DYNAMIC(MySQL 8默认)以此降低页面分裂频率。
7、结论
页面分裂与合并是InnoDB动态维护B+树的核心机制,但频繁地触发页面分裂及合并会对数据库带来较大的负面影响:首先是索引碎片问题,主键插入模式决定了碎片化程度,具体分内部碎片以及外部碎片;其次是I/O性能问题,碎片化会导致读放大与更多的随机I/O;再次是内存利用率问题,碎片化会导致缓冲池缓存更多的低密度页,从而是查询性能开始劣化。
对此本文提出了几个关键的优化方向:采用顺序主键(如AUTO_INCREMENT)是降低分裂及碎片化最为有效的措施;按需调整innodb_fill_factor并定期进行表重建是重要举措;对于大字段行采用合适的行格式。
总的来说,要让MySQL系统和相关应用高效运行起来,深入理解InnoDB的B+树的物理结构与分裂/合并机制是必不可少的一环。
- 点赞
- 收藏
- 关注作者
评论(0)