mysql的执行计划

MySQL 中广泛使用了 B+ 树（B-Tree Plus）作为索引的数据结构，特别是在其 InnoDB 存储引擎中。B+ 树是一种自平衡的树数据结构，能够保持数据有序，允许搜索、顺序访问、插入和删除操作都在对数时间内完成。相比于 B 树，B+ 树在数据库和文件系统的实现中更为常见，主要因为它的几个特点非常适合这些应用场景。

B+ 树的特点

所有值都在叶子节点：在 B+ 树中，所有的值（或指向数据记录的指针）都存储在叶子节点中，而内部节点仅用于索引，存储键（关键字）信息以指导搜索过程。这意味着非叶子节点不存储与记录内容有关的数据，这使得内部节点能够存储更多的键，从而提高了树的分支因子（每个节点可以拥有的子节点的最大数量），进而减少了树的高度，提高了搜索效率。
叶子节点之间互相链接：B+ 树的叶子节点之间通过指针相连，形成了一个双向链表。这使得范围查询变得非常高效，因为可以在叶子节点之间直接遍历，而无需返回根节点重新搜索。
分支因子高：由于内部节点不存储数据，只存储键和子节点的指针，因此可以有更多的子节点，这提高了树的分支因子。分支因子越高，树的高度就越低，从而减少了查找数据所需的磁盘I/O次数（因为每次磁盘I/O可以读取更多的节点）。
保持平衡：B+ 树是一种自平衡树，这意味着在插入或删除节点时，树会自动调整以保持其平衡状态，确保查找、插入和删除操作的时间复杂度保持在 O(log n) 级别。

在 MySQL 中的应用

在 MySQL 的 InnoDB 存储引擎中，B+ 树被用于实现表的主键索引和二级索引（也称为辅助索引或非聚集索引）。主键索引的叶子节点包含了表中行的完整数据（或指向数据的指针），而二级索引的叶子节点则包含了索引列的值和主键的值（或指向主键值的指针），这使得 InnoDB 能够通过二级索引快速定位到主键，然后再通过主键索引找到完整的行数据。

这种设计既提高了查询效率，也支持了高效的索引覆盖扫描（即查询的列完全包含在索引中，无需访问表数据），同时还支持了事务处理、行级锁定和外键约束等高级数据库功能。