Skip to content

为什么 MySQL 采用 B+ 树作为索引

MySQL 的数据持久化存储在磁盘上。磁盘是一种慢速存储设备，其访问速度以毫秒计，远慢于纳秒级的内存访问。数据库操作中，通过索引查找数据需要先从磁盘读取索引到内存，再根据索引找到数据行并读入内存。这个过程涉及多次磁盘 I/O。因此，一个优秀的索引数据结构，其核心目标是尽可能减少查询过程中的磁盘 I/O 次数。

对索引数据结构的要求： 1. 查询时，磁盘 I/O 操作次数要尽可能少。 2. 能高效地支持单点查询和范围查询。

数据结构的演进

  1. 二分查找与数组

    • 优点：对于有序数组，二分查找法效率很高，时间复杂度为 O(logn)。
    • 缺点：数组是线性结构，插入和删除元素时，需要移动大量后续元素，这个开销在磁盘上是无法接受的。

  2. 二叉查找树 (Binary Search Tree)

    • 优点：它是一种天然的二分结构，解决了数组插入和删除困难的问题。查询时，通过比较节点值决定向左或向右子树查找，无需计算中间位置。
    • 缺点：存在极端情况。如果插入的元素总是有序的（例如，总是插入最大值），二叉查找树会退化成一个链表。此时，查询时间复杂度从 O(logn) 下降到 O(n)，树的高度随之增加，导致磁盘 I/O 次数增多，性能严重下降。

  3. 自平衡二叉树 (Self-Balancing Binary Search Tree, 如 AVL 树、红黑树)

    • 优点：通过特定的约束条件（如 AVL 树中任意节点的左右子树高度差不超过1）来维持树的平衡，避免了退化成链表的情况，确保查询时间复杂度稳定在 O(logn)。
    • 缺点：本质上仍然是二叉树，每个节点最多只有两个子节点。当数据量非常大时，树的高度依然会很高。树的高度直接关系到磁盘 I/O 的次数（假设每个节点对应一次 I/O），因此高耸的树会影响查询效率。

  4. B 树 (B-Tree)

    • 为了降低树的高度，B 树被提了出来。它是一个多叉树，允许每个节点拥有超过两个子节点（M > 2），M 称为 B 树的阶。
    • 特点：节点可以存储多个索引值和多个子节点指针。这使得树变得“矮胖”，极大地降低了树的高度。
    • 查询过程：从根节点开始，比较索引值，然后顺着对应的子节点指针向下查找。
    • 缺点：
      • 每个节点都同时存储索引键和数据记录。如果数据记录本身很大，会导致一个节点（即一个磁盘页）内能存储的索引键数量变少，从而间接增加了树的高度。
      • 在查询过程中，会加载许多非目标节点的无用数据记录到内存中，占用了资源。
      • 范围查询效率低。B 树进行范围查询需要进行中序遍历，可能涉及多个不相邻节点的磁盘 I/O，效率不高。

B+ 树

B+ 树是对 B 树的优化和升级，也是 MySQL InnoDB 存储引擎最终采用的索引结构。

B+ 树与 B 树的核心差异： 1. 数据存储位置：非叶子节点只存储索引键，不存储实际的数据记录。所有的数据记录都存放在叶子节点中。 2. 索引冗余：非叶子节点中的索引，会同时存在于其子节点中，并且是子节点中索引的最大值或最小值。 3. 叶子节点链表：所有的叶子节点通过一个链表相互连接，形成一个有序序列。 4. 查询路径：任何数据的查询都必须从根节点走到叶子节点才能完成，查询路径长度固定。

B+ 树的优势： 1. 更少的磁盘 I/O：由于非叶子节点不存储数据记录，只存储索引，所以单个节点（一个磁盘页，如 16KB）可以容纳更多的索引键。这使得 B+ 树比同样数据量的 B 树更加“矮胖”，树的高度更低，查询时所需的磁盘 I/O 次数更少。 2. 插入和删除效率更高：B+ 树有大量的冗余节点。在删除节点时，通常可以直接从叶子节点中进行，对非叶子节点的影响较小，不需要像 B 树那样进行复杂的树结构变形。 3. 范围查询极其高效：这是 B+ 树最显著的优势。当需要进行范围查询时（如查找某个时间段内的订单），只需先定位到范围的起始叶子节点，然后通过叶子节点之间的链表，顺序向后遍历即可，无需反复从根节点开始查找。B 树则必须进行多次树的遍历才能完成。

MySQL (InnoDB) 中的 B+ 树特性

InnoDB 存储引擎对 B+ 树进行了进一步的实现和优化。 1. 双向链表：叶子节点之间通过一个双向链表连接，既可以向后遍历，也可以向前遍历。 2. 数据页：B+ 树的节点在 InnoDB 中被称为数据页（Page），每个数据页默认大小为 16 KB，里面存放了用户记录和元信息。 3. 索引类型： * 聚簇索引 (Clustered Index)：叶子节点直接存放完整的用户记录（行数据）。每个表必须有一个且只能有一个聚簇索引（通常是主键）。 * 二级索引 (Secondary Index)：也叫非聚簇索引。其叶子节点存放的不是行数据，而是该行数据对应的主键值。当使用二级索引查询时，会先找到对应的主键，然后再用该主键去聚簇索引中查找完整的行数据，这个过程称为“回表”。