MySQL叶子节点为啥使用双向链表？不使用单向呢？

文章内容收录到个人网站，方便阅读：http://hardyfish.top/

文章内容收录到个人网站，方便阅读：http://hardyfish.top/

文章内容收录到个人网站，方便阅读：http://hardyfish.top/

MySQL 中的 B+ 树索引（尤其是 InnoDB 存储引擎的默认聚簇索引）采用 双向链表来连接叶子节点，而不是单向链表，这种设计主要是为了提高查询效率，尤其是在进行范围查询（例如 BETWEEN）时。具体的原因包括：

1. 支持双向范围查询（提升查询灵活性）

双向链表使得叶子节点之间的遍历更加灵活，能够支持 顺序查询 和 倒序查询 两种场景。对于范围查询和排序操作，使用双向链表能提高效率：

• 顺序扫描：通过双向链表，MySQL 可以从指定的起始叶子节点顺序扫描到下一个叶子节点，执行范围查询或排序时，顺序访问非常高效。

• 倒序扫描：如果需要倒序查询或倒排索引查询，双向链表提供了方便的支持。通过指向前一个叶子节点的指针，可以很方便地实现从高值到低值的扫描，而无需再次从头开始遍历 B+ 树。

  例如，ORDER BY column DESC 查询时，双向链表能够允许 MySQL 从最大值开始，按逆序快速遍历节点。

2. 减少不必要的回溯

如果使用单向链表，在倒序查询时，MySQL 必须重新进行回溯（即从根节点重新开始查找），从而增加了不必要的额外工作和查询延迟。双向链表通过每个节点保存指向上一个节点的指针，可以快速找到前一个叶子节点，从而避免了回溯操作。

3. 范围查询优化

在进行 范围查询 时，双向链表有助于优化查询性能。例如，SELECT * FROM table WHERE column BETWEEN X AND Y 这种查询，MySQL 可以在找到第一个符合条件的叶子节点后，顺序地向后遍历获取后续的符合条件的记录。如果查询需要向前扫描，使用双向链表也能快速访问前面的记录，避免回到树的根节点重新查找。

4. 插入和删除操作的优化

在插入和删除操作时，双向链表可以减少链表重新排列的复杂度。在插入新数据到叶子节点时，如果是顺序插入，双向链表可以确保每个节点之间的顺序关系不被打乱；删除操作时也能快速定位前一个和下一个节点，避免破坏链表结构。

5. 降低范围查询的执行时间

由于双向链表能够支持双向扫描，可以大幅度减少范围查询的时间，尤其是在大数据量的情况下。如果查询需要倒序进行，单向链表就需要重新从根节点开始查找，甚至多次跳跃查找数据，这会显著影响查询的效率。

6. 一致性和完整性

使用双向链表的设计，使得 B+ 树的叶子节点之间的关系更加一致，查询操作更加直观和简便。每个叶子节点都不仅指向下一个叶子节点，还指向前一个叶子节点，从而保持了索引数据结构的完整性，减少了结构的不一致问题。

7. 适应性更强

双向链表结构相比单向链表提供了更多的灵活性，特别是在查询执行过程中。MySQL 的查询执行引擎不仅仅要执行普通查询，还可能涉及复杂的 联接查询 或 排序操作，而双向链表使得这些操作更加高效和易于实现。

总结：

MySQL 的 B+ 树使用 双向链表 来连接叶子节点，主要是为了：

• 提供更高效的 顺序扫描 和 倒序扫描；
• 支持 范围查询 和 倒序范围查询，提高查询灵活性和性能；
• 避免倒序查询时的回溯操作，减少额外的计算开销；
• 提高 插入 和 删除 操作的效率；
• 保证索引操作的一致性和完整性。

这种设计使得 B+ 树在执行复杂查询时具有显著的性能优势，尤其是在数据量大、查询频繁的场景下。