B+Tree

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+树，但它的叶子节点存储的是该索引列的值和对应记录的主键值。当通过二级索引查找数据时，需要先找到主键，再回到主键索引（聚簇索引）中查找完整数据，这个过程称为“回表”。...