mysql的B+树
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和范围查询的场景，是数据库索引的理想选择。