B+树的基本概念

B+树是MySQL中InnoDB存储引擎默认的索引数据结构，适用于磁盘存储的平衡多路查找树。与B树相比，B+树的非叶子节点仅存储键值（不存储数据），所有数据记录都存储在叶子节点，且叶子节点通过指针连接形成有序链表。

B+树的特点

• 层级结构：非叶子节点仅作为索引，叶子节点存储完整数据（或数据指针）。
• 有序性：所有叶子节点按键值大小顺序排列，支持高效的范围查询。
• 高扇出：单个节点可存储大量键值，减少树的高度，降低磁盘I/O次数。

B+树的索引优势

• 范围查询高效：叶子节点的链表结构支持快速的范围扫描（如WHERE id BETWEEN 10 AND 100）。
• 稳定性：查询时间复杂度为O(log n)，且树高通常为3-4层（假设千万级数据）。
• 适合磁盘存储：节点大小通常设计为磁盘页大小（如16KB），最大化I/O效率。

B+树在InnoDB中的应用

• 聚簇索引：主键索引的叶子节点直接存储行数据，表数据本身就是按B+树组织的。
• 二级索引：非主键索引的叶子节点存储主键值，查询需回表（通过主键二次查找）。

节点分裂与合并

• 分裂条件：插入数据导致节点键值数超过阈值（如InnoDB的16KB页限制）。
• 合并条件：删除数据后节点键值数低于填充因子，可能触发与兄弟节点的合并。

与B树的区别

• 数据存储位置：B树所有节点都可能存储数据；B+树数据仅存于叶子节点。
• 查询效率：B+树范围查询更快，B树随机查询可能更优（但实际场景中B+树综合表现更好）。

代码示例（模拟B+树节点结构）

class BPlusTreeNode: def __init__(self, is_leaf=False): self.keys = [] # 键值列表 self.children = [] # 子节点指针（非叶子节点） self.data = [] # 数据记录（叶子节点） self.next_leaf = None # 指向下一个叶子节点 self.is_leaf = is_leaf

性能优化建议

• 合理选择主键：自增整数主键可避免频繁分裂（随机主键如UUID可能导致写放大）。
• 覆盖索引：通过联合索引避免回表操作，提升查询速度。
• 页填充因子：可通过参数调整平衡写入与查询效率（如innodb_fill_factor）。

B+树的设计充分考虑了磁盘I/O和范围查询的场景，是数据库索引的理想选择。