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_leafFalse): self.keys [] # 键值列表 self.children [] # 子节点指针非叶子节点 self.data [] # 数据记录叶子节点 self.next_leaf None # 指向下一个叶子节点 self.is_leaf is_leaf性能优化建议合理选择主键自增整数主键可避免频繁分裂随机主键如UUID可能导致写放大。覆盖索引通过联合索引避免回表操作提升查询速度。页填充因子可通过参数调整平衡写入与查询效率如innodb_fill_factor。B树的设计充分考虑了磁盘I/O和范围查询的场景是数据库索引的理想选择。