索引设计与执行机制⚓︎

摘要

本篇笔记主要梳理了 MySQL 中以 B+ 树为核心的索引结构与逻辑分类，总结了聚簇索引与非聚簇索引的区别、组合索引的最左前缀匹配与覆盖索引的高效使用原理，并简述了多表连接（JOIN）的模式与关联驱动机制。

索引数据结构⚓︎

MySQL 中最核心的索引数据结构是 B+ 树，其查询时间复杂度通常处于 $O(\log n)$ 级别。不同存储引擎对特定数据结构的支持情况存在差异：

B+ 树索引：适用面最广，叶子节点之间通过双向链表相连，特别适合排序与范围区间查询。
Hash 索引：由于散列表是无序的，因此仅能满足等值（=、IN、<=>）查询，无法执行范围查询。哈希索引的检索只需一次计算即可定位，避免了 B+ 树逐层查找的 I/O 开销。
- Memory 引擎显式支持该结构；
- InnoDB 提供自适应哈希索引（Adaptive Hash Index, AHI）。当系统监控到某些 B+ 树索引页被频繁通过等值条件访问时，会在内存中自动为这些页面建立哈希映射，从而提升等值查询的性能。有关 AHI 的完整工程机制，详见 InnoDB 四大核心特性：自适应哈希索引。
全文索引（FULLTEXT）：主要应用于长文本的检索匹配，目前 MyISAM 与 5.7+ 版本的 InnoDB 均原生支持。
空间索引（R-Tree）：为空间数据类型（如 GEOMETRY、POINT、POLYGON 等）构建的多维关联查询支持结构。

索引的逻辑分类⚓︎

从业务逻辑特征与约束规则的维度划分，MySQL 中的索引主要分为以下几种类型：

主键索引（Primary Key Index）：一种特殊的唯一索引，强制要求索引列的值必须唯一且不允许为空（NOT NULL）。每张表有且仅能有一个主键。
唯一索引（Unique Index）：确保索引列的所有值域各不相同，以维护业务层面的数据一致性，但通常允许存在空值（NULL）。
普通/单列索引（Normal/Single-Column Index）：仅在单个确定的数据列上创建的常规索引，没有任何唯一性约束限制，其核心目的仅为提速条件查询。
复合/多列索引（Composite Index）：在多个数据字段上联合创建的单一索引实体。其触发和使用必须严格遵循最左前缀匹配原则（即查询条件中必须存在定义该索引时的首个字段位起算的连续序列前缀）。
空间索引（Spatial Index）：专门针对如 GEOMETRY、POINT、LINESTRING、POLYGON 等空间计算数据类型创建。建表或建索引时需通过 SPATIAL 关键字指定，同时目标列必须声明为 NOT NULL。传统历史上这主要依赖 MyISAM 引擎，但自 MySQL 5.7 版本以后，InnoDB 也已经正式确立了对此类空间检索数据结构的底层树形支持。

聚簇索引与非聚簇索引⚓︎

InnoDB 会基于聚簇索引（Clustered Index）的结构物理存储整表数据。

基本区别原理⚓︎

聚簇索引：每张表必须且仅能存在唯一一个聚簇索引。该索引的叶子节点直接存放完整的行记录数据。如果表未定义主键，系统将自动选择首个非空唯一索引；若均不存在，则会自动生成隐藏列（Row ID）充当聚簇索引。
非聚簇索引（二级索引）：可以定义多个，主要用于加速特定列上的过滤操作或满足连接查询需求。在 InnoDB 中，二级索引的叶子节点仅存储被索引字段的值以及对应行记录的主键值。

回表的磁盘开销

由于二级索引的叶子节点仅包含主键和索引列属性，如果查询投影列（如 SELECT *）或过滤条件包含了未被该二级索引覆盖的列，执行引擎必须携带获取到的主键值，回溯到聚簇索引树重新查找完整的行数据，这一过程称为回表。

组合索引与匹配原则⚓︎

当针对涉及跨列串联的高频查询需求时（如同时在 WHERE 条件中判断多列的边界），工程实践上推荐构建组合索引。

创建组合索引的工程收益⚓︎

降低维护开销：创建一个 (col1, col2, col3) 的组合索引，在查询效果上等价于分别拥有了 (col1)、(col1, col2) 与 (col1, col2, col3) 三组索引，从而避免了维护多棵单列 B+ 树带来的额外插入与更新成本。
覆盖索引消除回表：如果查询投影恰好为 SELECT col1, col2, col3，由于所需字段已全部包含在该组合索引树中，查询引擎可直接从该索引获取结果并返回，完全消除了昂贵的回表操作。
综合过滤效率高：组合索引能够综合多个列的选择性（Selectivity）进行累乘过滤，相较于分别对单列使用索引再在内存中取交集而言，数据扫描量更小。

最左前缀匹配原则⚓︎

使用组合索引 (col1, col2, col3) 的先决条件是：查询过滤条件的匹配必须从该指引定义的最左侧第一列开始，且中间不能跳过。

查询语句的 WHERE 条件中只要包含了组合索引的最左侧字段（本例中即 col1），该索引的部分结构便能被有效利用。

多表连接与执行驱动⚓︎

MySQL 在关系代数层面主要通过横向连接提取关联列，并在纵向层面合并结果集。

横向关联操作⚓︎

所有参与横向关联连接的查询需区分执行方向。主流的关联方式包括：

内连接（Inner Join）：在集合论中表示提取出两表中满足连接条件的共有数据集，丢弃未匹配的记录（关键字 INNER 可省略）。
左外连接（Left Join）：以左表为基准驱动执行，全量保留左表数据。若右表存在匹配项则关联展示，若无匹配项则右表字段用 NULL 占位填充。
右外连接（Right Join）：机制与左连接对称。只是在 SQL 语句的结构上调换了主表与从表的驱动顺序。

数据连接维度关系

连接操作的结果规模会受表间的对应关系（如一对多与多对多）影响：在涉及一对多关联时：左表的一条记录会根据匹配右表的条数进行扩展复制。在涉及多对多关联时：双方的数据交叉行将按照笛卡尔积性质倍增，若无准确的过滤条件，会导致结果集严重膨胀并产生冗余重复。

纵向叠加操作⚓︎

并集（UNION）：将两张结构相同的查询结果在纵向行级合并。引擎会施加额外的去重操作，剔除结果集中完全重复的行。
全集（UNION ALL）：将两组查询结果直接追加串联，跳过去重校验与合并排序。由于没有去重带来的 CPU 与临时表开销，其执行效率远高于 UNION。

执行器当中的连接原理引擎⚓︎

对于内部执行计划的生成，MySQL 在物理层面需要决策表之间的关联顺序，从而确定“驱动表”与“被驱动表”角色：

驱动表（Driving Table） 作为查询处理起点的基准表。执行计划首先会基于驱动表的各类过滤条件（如 WHERE 谓词）结合索引扫描出一批初步合法的数据集。
被驱动表（Driven Table） 循环接收驱动表传递过来的一行或一批评估记录，并以该记录的关联字段作为条件，在被驱动表的全量数据或索引树中触发相应的扫描与检索动作，完成两张表记录的最终拼接。