MySQL-innodb存储引擎为什么采用B+树

Posted recently Updated recently

By Administrator

18~23 min read

为什么 InnoDB 使用 B+树

高效的磁盘 I/O 操作
- B+树的非叶子节点不存储数据，只存储索引值。这使得每个节点可以容纳更多的索引值，从而降低树的高度。
- B+树的叶子节点通过链表相连，方便范围查询，进一步减少磁盘访问次数。
适合范围查询
- B+树的叶子节点按顺序存储所有关键字，并且通过链表相连，非常适合范围查询和排序查询，而普通 B 树或二叉树需要进行全树遍历。
平衡性
- B+树和 B 树一样，始终保持平衡，确保插入、删除、查找的时间复杂度为 O(log⁡n)O(\log n)，适合大规模数据场景。
顺序访问优化
- B+树的叶子节点链表使得顺序遍历更高效，适合 MySQL 的 ORDER BY 和区间查询。

如果采用其他树结构，会有什么问题？

1. 普通二叉树

问题
不平衡问题：普通二叉树在插入数据时，如果数据本身有序，会退化成链表，查找复杂度可能变为 O(n)O(n)，性能极差。
低节点利用率：每个节点只存储一个关键字，大量空闲空间浪费，导致磁盘 I/O 次数增加。
后果
查询性能不稳定，数据量大时，性能下降明显。
磁盘空间利用率低，I/O 开销高。

2. B树

问题
非叶子节点存储数据：B树的每个节点都存储索引值和数据，占用更多空间，导致每个节点能存储的关键字数量减少，树的高度增加。
范围查询效率低：B树的范围查询需要遍历多个节点，性能不如 B+树，特别是大范围查询时。
后果
增加了磁盘 I/O 次数，查询效率下降。
范围查询性能不足，排序和区间操作效率较低。

3. 红黑树

问题
高度较高：红黑树的高度接近 O(log⁡n)O(\log n)，比 B+树高，因为每个节点只存储一个关键字。这样需要更多的磁盘 I/O。
不支持范围查询：红黑树没有叶子节点的链表结构，无法高效支持范围查询。
后果
范围查询时需要全树遍历，性能低下。
树高度增加导致磁盘访问次数更多，性能不如 B+树。

总结

特性	二叉树	B树	B+树	红黑树
是否平衡	否	是	是	是
范围查询效率	差	一般	高	差
节点存储内容	关键字和数据	关键字和数据	关键字（数据在叶子）	关键字和数据
磁盘 I/O 次数	多	较少	最少	多

InnoDB 选择 B+树 是基于数据库对范围查询、高并发和磁盘 I/O 性能的综合需求，避免了普通树结构在平衡性和查询效率方面的局限性。

让我们深入理解你提到的两个关键问题：

1. B+树非叶子节点不存储数据，那数据存储在哪里？

在 B+树 中：

非叶子节点 只存储索引值（关键字），作为引导下层节点的路径指针，不存储实际的数据。
实际数据 都存储在 叶子节点 中。

数据存储方式

索引节点（非叶子节点）：
- 仅保存关键字和子节点指针，用于导航。
- 例如，如果索引是 10, 20, 30，这些值帮助确定数据存储在哪个子节点中。
叶子节点：
- 保存关键字和对应的数据。
- 如果是 主键索引，叶子节点直接保存完整的行记录（即数据）。
- 如果是 二级索引（非主键索引），叶子节点保存关键字和指向对应主键行的指针。
链表结构：
- 叶子节点通过双向链表连接在一起，支持快速的范围查询。

举例

假设有数据记录：

[1, A], [5, B], [10, C], [20, D], [30, E]

B+树的结构如下：

非叶子节点

：

[10, 20, 30] -> 指向子节点

叶子节点

（存数据）：

[1, A] -> [5, B] -> [10, C] -> [20, D] -> [30, E] (通过链表连接)

2. 为什么其他场景不都使用 B+树？

虽然 B+树 很优秀，但它并不适合所有场景。以下是 B+树适用性和局限性的分析：

适合 B+树的场景

范围查询：
- 由于叶子节点按顺序存储，且通过链表连接，B+树能快速找到范围内的数据。
- 数据库索引、文件系统 中，范围查询和排序是常见需求，因此 B+树非常适合。
磁盘 I/O 敏感场景：
- 非叶子节点仅存储索引值，占用空间少，减少磁盘访问次数。
- 適合处理大规模数据、频繁查询的场景（如数据库）。

不适合 B+树的场景

内存优化的场景：
- 在小型系统或内存数据结构中，像 红黑树 或 AVL树 更适合。
- 因为它们的实现简单，插入和删除速度更快，而不需要复杂的节点分裂操作。
高频插入/删除的场景：
- B+树的插入和删除涉及节点分裂和合并，代价较高。
- 如实时计算场景，频繁更新的情况下可能使用其他数据结构，如跳表或 红黑树。
查找单个值的场景：
- 如果仅需要查找单个值（非范围查询），则 哈希表（如 HashMap）更高效，其查找复杂度为 O(1)O(1)。
内存索引场景：
- 在纯内存存储的索引场景下（如一些内存数据库），因为不涉及磁盘 I/O，B+树的优势不明显，简单的数据结构可能更合适。

举例

数据库 使用 B+树（适合复杂查询和磁盘优化）。
Redis 使用跳表（Skip List），因为它是纯内存操作，插入和删除效率高，范围查询性能接近 B+树。
编程语言容器（如 Java 的 TreeMap）使用 红黑树，因为其实现简单，且适合内存操作。

总结

数据存储

B+树非叶子节点只存索引，数据都存储在叶子节点中，叶子节点通过链表连接，适合范围查询。

B+树的选择性

数据库 等需要频繁范围查询和优化磁盘 I/O 的场景使用 B+树。
其他场景（如内存索引、高频操作）会因需求不同选择更简单、高效的数据结构。B+树并非万能，而是为特定需求设计的结构。

红黑树和AVL树在某些场景下插入和删除速度更快，主要原因是它们的结构和维护平衡的策略更加高效，与 B+树 或其他树型结构相比，它们的操作复杂性较低。以下是具体分析：

1. 红黑树和 AVL 树的特点

红黑树

是一种自平衡二叉搜索树，每次插入或删除后，通过 颜色反转 和旋转操作维持平衡。
高度近似平衡，最坏情况下的高度为 O(log⁡n)O(\log n)。
平衡性维护代价较低：只需少量旋转（最多 2 次）和颜色修改。

AVL树

严格平衡的二叉搜索树，要求每个节点的左右子树高度差最多为 1。
高度平衡性更严格，查找性能较好，但需要更多旋转来维持平衡。
插入和删除操作复杂度为 O(log⁡n)O(\log n)。

2. 插入和删除速度更快的原因

维护平衡的操作代价较低

红黑树的平衡策略更宽松：
- 红黑树通过“允许部分不平衡”来减少调整操作。
- 只需要少量颜色改变和 最多两次旋转 来维持平衡，操作代价较低。
AVL 树旋转成本虽然较高，但仍优于 B+树：
- AVL 树可能需要多次旋转，但仍是局部操作，不涉及多节点移动。
- 适合插入、删除频率较高，但不需要大规模范围查询的场景。

节点存储的数据量小

红黑树和 AVL 树的每个节点只存储一个关键字和指针，因此节点的内存占用较小，插入或删除时无需处理复杂的节点分裂或合并操作。

操作的局部性强

红黑树和 AVL 树的插入、删除操作通常只涉及到路径上的父节点、祖父节点，调整范围小。
相比之下，B+树的插入可能触发节点分裂，删除可能触发节点合并，影响整个树的结构。

内存操作效率高

红黑树和 AVL 树通常用于内存中的数据存储，而不是磁盘。
由于没有磁盘 I/O 的限制，插入和删除速度主要取决于旋转和指针调整的效率。

3. 为什么 B+ 树插入和删除速度较慢

节点分裂和合并的复杂性

插入：如果某个节点已满（达到阶数限制），需要将节点分裂，将一个关键字上移到父节点，可能递归导致父节点分裂，直至根节点。
删除：如果某个节点的关键字数量低于最小值，可能需要从兄弟节点借关键字或与兄弟节点合并，这会引发复杂的调整操作。

涉及大量指针和磁盘 I/O

B+树的节点存储多个关键字和子指针，调整时需要移动或修改较多数据。
如果节点分裂或合并涉及磁盘存储，插入或删除会触发磁盘 I/O 操作，进一步降低速度。

叶子节点的链表调整

B+树的叶子节点通过链表连接，插入和删除操作时可能需要更新链表结构。

4. 红黑树和 AVL 树 vs. B+树：适用场景比较

特性	红黑树	AVL 树	B+ 树
插入速度	较快	较快	较慢
删除速度	较快	较快	较慢
范围查询性能	一般	一般	非常高
平衡维护复杂度	低（宽松平衡）	中（严格平衡）	高（涉及分裂/合并）
适合场景	内存索引、高频更新	内存索引、高频更新	磁盘存储、范围查询

总结

红黑树和 AVL 树插入、删除速度更快的原因：
1. 平衡性维护代价低（少量旋转或颜色变化）。
2. 节点存储的数据量少，调整时涉及的操作范围小。
3. 内存操作效率高，无需处理复杂的磁盘 I/O。
B+树适合范围查询和磁盘优化场景，但插入和删除时，由于需要维护较多关键字、指针及节点结构，会付出更高的代价。

因此，数据结构的选择应根据具体场景和需求，平衡操作效率与功能性。

技术分享

License: CC BY 4.0