B+树与B-树详解

1. 基本概念

1.1 B-树（B Tree）

• 一种自平衡的树数据结构
• 每个节点包含键值和数据
• 所有叶子节点位于同一层

1.2 B+树（B+ Tree）

• B-树的变种
• 数据只存储在叶子节点
• 非叶子节点仅包含键值和指针

2. 结构图解

2.1 B-树结构

        [P1|10|P2|20|P3]
          /    |    \
     [5|7]  [15|17]  [25|30]

2.2 B+树结构

        [10|20]
        /     \
[5|7|10] -> [15|17|20] -> [25|30]

3. 优缺点对比

3.1 B-树

优点：

• 数据分布在整个树中，查询效率稳定
• 适合随机访问

缺点：

• 节点结构复杂
• 范围查询效率较低

3.2 B+树

优点：

• 叶子节点形成链表，范围查询高效
• 非叶子节点更小，可容纳更多键值
• 更适合磁盘存储

缺点：

• 随机访问可能比B-树稍慢
• 需要额外维护叶子节点链表

4. MySQL中的应用

4.1 InnoDB存储引擎

• 使用B+树作为索引结构
• 主键索引（聚簇索引）
• 二级索引（非聚簇索引）

4.2 索引结构示例

        [10|20]
        /     \
[5|7|10] -> [15|17|20] -> [25|30]
  |           |            |
[data]      [data]       [data]

4.3 性能优化

• 合理设计主键
• 使用覆盖索引
• 避免索引失效

7. 总结

特性	B-树	B+树
数据存储位置	所有节点	仅叶子节点
查询效率	随机访问快	范围查询快
空间利用率	较低	较高
适用场景	内存数据库	磁盘数据库

在MySQL中，B+树因其高效的磁盘I/O性能和优秀范围查询能力，成为主流索引结构。