MySQL索引原理：B-Tree与B+Tree的核心区别

B-Tree（多路平衡查找树）的基本特征

B-Tree是一种自平衡的多路搜索树。其核心特点是所有节点（包括内部节点和叶子节点）都会存储数据（Key + Value）。树的结构保持有序性，每个节点内的关键字从小到大排列，左子树小于父节点，右子树大于父节点。

• 数据存储：任何关键字出现且只出现在一个节点中，数据和索引混合存储。
• 查询特性：搜索可能在非叶子节点结束。这意味着如果在中间层找到关键字，就直接返回结果，无需遍历到最底层。
• 平衡性：所有叶子节点位于同一层级，保证查询稳定。

B+Tree（多路平衡查找树变体）的核心特点

B+Tree是B-Tree的变种，专门针对数据库索引优化。它保留了B-Tree的排序和平衡特性，但改变了数据的存储位置：

• 非叶子节点：不存储数据（Value），仅存储索引键（Key）。这使得每个节点能容纳更多的索引项。
• 叶子节点：包含完整的数据记录，并且所有叶子节点通过双向指针连接成一个有序链表。
• 层级结构：由于非叶子节点只存键，单个节点可容纳更多指针，从而大幅降低树的层级高度。

两种索引结构的性能差异对比

第1步：理解单次查询的IO开销

在数据库系统中，磁盘读取以“页”（Page）为单位。InnoDB存储引擎中，Page是磁盘与内存交换的最小单位，默认大小为16KB（可通过innodb_page_size参数查看或修改）。

假设一个页需要存储50个索引项：

• B-Tree：每个节点都存数据，导致节点内能存储的键值对数量较少（因为数据占用空间大）。这会导致树的高度增加。查询时可能需要访问更多层级的磁盘页，产生更多IO操作。
• B+Tree：非叶子节点只存键，不存数据。同样大小的页面可以存放成倍的索引项。树的高度显著降低。通常情况下，3层B+Tree即可存储数百万条记录。

第2步：评估全表扫描与范围查询效率

• B-Tree：如果需要进行范围查询（如 BETWEEN 10 AND 100），需要先定位到起始位置，然后在中序遍历的过程中逐个获取数据。由于数据分散在不同节点的叶子中，遍历过程相对复杂，无法直接利用顺序性。
• B+Tree：所有数据都在叶子节点，且叶子节点通过指针串联成双向链表。一旦定位到范围的起始索引，只需顺着叶子节点的指针进行顺序遍历即可快速找到后续所有记录。这对于数据库的范围查询（Range Query）是巨大的性能优势。

第3步：确定性查询与缓存友好度

• 查询长度固定：B+Tree的任何查询都必须走到叶子节点，每次查询的IO次数是确定的（即树的高度）。而B-Tree可能在任意层级命中，查询长度不固定。
• 局部性原理：B+Tree的非叶子节点通常比叶子节点小得多，更容易被加载到内存缓冲池中，从而提高缓存命中率。

B+Tree为何成为MySQL(InnoDB)的首选?

综合上述分析，B+Tree相比B-Tree在MySQL场景下具有以下决定性优势：

1. 更低的树高：非叶子节点仅存储键值，使得单节点扇出更高，树更矮胖，显著减少磁盘IO次数。
2. 高效的范围查询：叶子节点的双向链表结构，使其在处理 ORDER BY 和范围过滤时极其高效。
3. 稳定的查询性能：所有查询均访问叶子节点，性能波动小。

以上就是MySQL索引B-Tree与B+Tree区别及性能的详细内容，更多关于MySQL B-Tree与B+Tree应用资料请关注本站其它相关文章！