MySQL多列索引的工作原理是什么？其采用什么底层数据结构？

首先明确结论：MySQL常见存储引擎（InnoDB、MyISAM）的多列索引（也叫联合索引、复合索引）底层依然是B+树，不存在为多列场景单独设计的特殊数据结构。你之前认为B树仅支持单列属于常见误解，B树的索引键本身支持使用有序复合元组。

多列索引的具体工作逻辑 #

• 索引键的排序规则：创建联合索引时比如INDEX idx_a_b_c(a,b,c)，B+树的每个节点存储的键是(a值, b值, c值)的有序元组，排序优先级从左到右依次递减：先按a字段全局排序，a值相同的条目再按b字段排序，a、b值都相同的条目最后按c字段排序。
• 节点查找逻辑：查找逻辑和单列B+树完全一致，只是对比键的时候从左到右逐字段匹配，直到找到目标节点或者确定匹配项不存在。比如查询a=1 AND b=2 AND c=3可以直接从根节点逐级对比三元组，快速定位到对应行；查询a=1 AND b>2时也可以先定位到a=1的起始位置，再遍历b>2的所有连续节点。
• 最左匹配原则的由来：正是因为复合键的排序逻辑是左字段优先，所以如果查询条件不包含最左字段，比如仅查b=2，B+树无法直接定位匹配范围——b字段仅在a值相同的区间内有序，跨a值的b字段没有全局顺序，这种场景就无法使用该联合索引。

举个直观的例子，联合索引idx_age_name(age, name)的键值序列会是这样的：
(18, "张三"), (18, "李四"), (20, "王五"), (20, "赵六"), (22, "孙七")
你可以很容易找到所有age=18的name，也可以找age=18且name>"李"的项，但没法直接找到所有name="王五"的项，因为name的排序是依附于age字段的。

另外补充：InnoDB的聚簇索引本身也是特殊的联合索引，结构为(主键值, 事务ID, 回滚指针, 所有非主键列)，排序逻辑和普通联合索引完全一致。

内容的提问来源于stack exchange，提问作者GigiWithoutHadid