B+Tree
B+Tree 是一种平衡多路搜索树，广泛应用于数据库和文件系统等领域，其核心优势在于优化磁盘存储效率和查询性能.
MySQL的InnoDB存储引擎使用的索引结构就是 B+树，它是B树的一个重要变种。
1. 从B树到B+树
B树：一种自平衡的、多路的搜索树。它允许每个节点有多个子节点（多于两个，所以不是二叉树）。
B+树：在B树基础上优化而来的数据结构，是现代数据库系统中事实上的标准索引结构。
MySQL的InnoDB使用的正是 B+树。
2. 为什么数据库需要B+树？
要理解B+树，必须先理解它的设计目标。数据库的数据存储在磁盘上，磁盘I/O（读写磁盘）的速度比内存访问慢几个数量级。因此，数据库索引的核心目标是：最大限度地减少磁盘I/O次数。
B+树通过以下方式完美地实现了这一目标：
矮胖：与“瘦高”的二叉树相比，B+树每个节点可以存储非常多的键，这使得树的层级非常少（通常只有3-4层），从而保证在亿万级数据量下，查找任何一条记录最多只需要3-4次磁盘I/O。
顺序访问友好：B+树非常适合磁盘的预读特性，能够高效地进行范围查询。
3. B+树的详细结构
它由两种类型的节点组成：内部节点 和 叶子节点。
内部节点（非叶子节点）
作用：仅充当导航目录。
存储内容：只存储键值（索引列的值）和指向子节点的指针。
不存储：实际行的数据。
叶子节点
作用：存储实际的数据。
存储内容：
在 主键索引（聚簇索引） 中：叶子节点存储的就是完整的行数据。
在 辅助索引（二级索引） 中：叶子节点存储的是该索引的键值和对应的主键值。
关键特性：所有叶子节点通过指针相互连接，形成了一个有序的双向链表。这是B+树与B树的一个核心区别。
4. B+树的核心特性与优势（对比B树）
| 特性 | B树 | B+树 | B+树的优势 |
|---|---|---|---|
| 数据存储位置 | 内部节点和叶子节点都存储数据。 | 只有叶子节点存储数据，内部节点仅为索引。 | 更“矮胖”的树。因为内部节点不存数据，所以一个节点能容纳的键更多，扇出（子节点数）更大，树高更低，I/O次数更少。 |
| 叶子节点链接 | 叶子节点之间没有链接。 | 叶子节点通过双向链表连接。 | 无敌的范围查询。要查询age BETWEEN 20 AND 30的所有记录，B+树只需找到20，然后顺着链表遍历即可。B树则需要不断地在树的中上层和下层之间来回跳跃，性能极差。 |
| 扫描和全表遍历 | 需要对整棵树进行复杂的中序遍历。 | 只需遍历底层的链表即可获得所有数据，非常高效。 | 对数据仓库、聚合查询等场景非常友好。 |
| 查询稳定性 | 由于数据可能在内部节点找到，查询时间不稳定。 | 任何查询都必须走到叶子节点，查询时间非常稳定。 | 保证了可预测的性能。 |
5. 在MySQL中的具体体现：聚簇索引
在MySQL InnoDB中，主键索引就是一颗B+树，并且这棵B+树的叶子节点直接存储了完整的行数据。这种索引组织表的方式被称为“聚簇索引”。
表数据文件本身就是按B+树结构组织的一个索引文件。
如果你没有定义主键，InnoDB会选择一个唯一的非空索引代替，如果没有这样的索引，它会隐式地定义一个主键。
辅助索引（二级索引） 也是一颗B+树，但它的叶子节点存储的是该索引列的值和对应记录的主键值。当通过二级索引查找数据时，需要先找到主键，再回到主键索引（聚簇索引）中查找完整数据，这个过程称为“回表”。
6. 总结
MySQL（InnoDB）使用的 B+树 是一种为磁盘存储而精心设计的“矮胖”树形数据结构，其核心设计哲学是最小化磁盘I/O。
它的两大杀手级特性是：
高扇出带来的低树高：使点查询极其高效。
叶子节点的双向链表：使范围查询和全表扫描极其高效。
正是这些特性，使得B+树在过去几十年里，一直是关系型数据库索引技术的基石。