为什么 InnoDB 存储引擎选用 B+ 树而不是 B 树呢？

参考回答

InnoDB 存储引擎选用 B+树 而非 B树，主要是因为 B+树在数据库场景中具有以下优势：

1. 叶子节点链表结构便于范围查询：B+树的叶子节点通过双向链表连接，可以方便地进行范围查询（如 BETWEEN 或 > 操作）。
2. 更高的磁盘读写效率：B+树的非叶子节点只存储键值，而不存储实际数据，因此单个节点可以容纳更多的键值，树的高度更低，减少磁盘 I/O。
3. 便于扫描和排序：B+树的所有数据都存储在叶子节点中，天然有序，支持高效的全表扫描和排序操作。

相比之下，B树的非叶子节点也存储数据，这会导致节点存储能力变小，树的高度增加，从而增加磁盘 I/O，降低性能。

详细讲解与拓展

1. B树与 B+树的结构对比

• B树：
  • 每个节点存储键值和实际数据。
  • 数据既存在叶子节点，也存在非叶子节点。
  • 各节点之间无链表连接。
• B+树：
  • 非叶子节点只存储键值，用于索引定位，不存储实际数据。
  • 数据仅存储在叶子节点中。
  • 所有叶子节点通过链表连接，便于顺序访问。

示意图：

• B树：

    [10 | data]      [30 | data]
    /      \         /      \
  [5 | data] [15 | data]  [25 | data] [35 | data]
  

• B+树：

     [10]          [30]
    /    \        /    \
  [5]--->[15]--->[25]--->[35]
  

2. 为什么选择 B+树

(1) 更高的磁盘 I/O 效率

• 数据库大部分数据存储在磁盘上，查询时需要通过索引读取数据。
• B+树的非叶子节点只存储键值，不存储实际数据，每个节点可以容纳更多键值，树的高度更低。
• 结果：减少磁盘 I/O 次数，提高查询性能。

对比示例：
假设单个磁盘页大小为 4KB，键值大小为 16 字节，数据大小为 1KB：
– B树：一个节点可存储 ~3 个键值和数据。
– B+树：一个节点可存储 ~250 个键值。
– 效果：B+树的树高更低，I/O 次数更少。

(2) 便于范围查询

• B+树的叶子节点通过链表连接，天然支持范围查询和顺序遍历。
• B树的数据分散在叶子和非叶子节点中，范围查询需要在不同层级扫描，效率较低。

示例：
查询 WHERE id BETWEEN 10 AND 50：
– B树：需要从根节点到多个层级逐一查找范围内的所有数据。
– B+树：定位到起始叶子节点后，通过链表顺序扫描即可完成。

(3) 便于全表扫描和排序

• 数据库经常需要执行全表扫描（如 SELECT * FROM table）。
• B+树的所有数据存储在叶子节点，天然有序，通过链表可以顺序访问所有数据，性能较高。
• B树的全表扫描需要访问每个节点，遍历效率较低。

(4) 更稳定的查询性能

• B树的数据分布在多个节点，查询可能需要从根节点到不同深度的叶子节点，不同查询的耗时可能不一致。
• B+树的数据全部存储在叶子节点，树高固定，查询性能更稳定。

3. InnoDB 的实际使用场景

在 InnoDB 中：
1. 主键索引（聚簇索引）：
– 数据存储在 B+树的叶子节点。
– 主键索引直接将数据和索引结合，减少额外的磁盘读取。
2. 辅助索引（非聚簇索引）：
– B+树的叶子节点存储主键值的指针，通过主键定位数据，减少存储开销。

4. 总结：B+树对比 B树的优势

总结

InnoDB 选用 B+树而不是 B树，主要是因为 B+树在磁盘 I/O、范围查询、排序和全表扫描等方面具有显著优势。B+树通过叶子节点链表结构和更低的树高，提高了查询性能，降低了磁盘开销，成为数据库索引的最佳选择。

帅地永久会员

打赏 收藏 海报挣佣金 推广链接