深入理解mysql的联合索引

最近在学习MySQL的存储引擎和索引的知识。看了许多篇介绍MyISAM和InnoDB的索引的例子，都能理解。

像这张索引图：

PS:该图来自大神张洋的《MySQL索引背后的数据结构及算法原理》一文。

但许多文章讲述的都是单列索引，我很好奇 联合索引对应的结构图是怎样的。

比方说联合索引 (col1, col2,col3)，我知道在逻辑上是先按照col1进行排序再按照col2进行排序最后再按照col3进行排序。因此如果是select * from table where col1 = 1 and col3 = 3的话，只有col1的索引部分能生效。但是其物理结构上这个联合索引是怎样存在的，我想不懂。

上网查阅了许多资料，总算有点眉目了。

假设这是一个多列索引(col1, col2,col3)，对于叶子节点，是这样的：

PS:该图改自《MySQL索引背后的数据结构及算法原理》一文的配图。

也就是说，联合索引(col1, col2,col3)也是一棵B+Tree，其非叶子节点存储的是第一个关键字的索引，而叶节点存储的则是三个关键字col1、col2、col3三个关键字的数据，且按照col1、col2、col3的顺序进行排序。

配图可能不太让人满意，因为col1都是不同的，也就是说在col1就已经能确定结果了。自己又画了一个图（有点丑），col1表示的是年龄，col2表示的是姓氏，col3表示的是名字。如下图：

PS:对应地址指的是数据记录的地址。

如图，联合索引(年龄, 姓氏,名字)，叶节点上data域存储的是三个关键字的数据。且是按照年龄、姓氏、名字的顺序排列的。

因此，如果执行的是：

select * from STUDENT where 姓氏='李' and 名字='安'

或者

select * from STUDENT where 名字='安'

那么当执行查询的时候，是无法使用这个联合索引的。因为联合索引中是先根据年龄进行排序的。如果年龄没有先确定，直接对姓氏和名字进行查询的话，就相当于乱序查询一样，因此索引无法生效。因此查询是全表查询。

如果执行的是：

select * from STUDENT where 年龄=1 and 姓氏='李'

那么当执行查询的时候，索引是能生效的，从图中很直观的看出，age=1的是第一个叶子节点的前6条记录，在age=1的前提下，姓氏=’李’的是前3条。因此最终查询出来的是这三条，从而能获取到对应记录的地址。

如果执行的是：

select * from STUDENT where 年龄=1 and 姓氏='黄' and 名字='安'

那么索引也是生效的。

而如果执行的是：

select * from STUDENT where 年龄=1 and 名字='安'

那么，索引年龄部分能生效，名字部分不能生效。也就是说索引部分生效。

因此我对联合索引结构的理解就是B+Tree是按照第一个关键字进行索引，然后在叶子节点上按照第一个关键字、第二个关键字、第三个关键字…进行排序。

而之所以会有最左原则，是因为联合索引的B+Tree是按照第一个关键字进行索引排列的。

联合索引在B+树上的结构介绍

《mysql索引背后的数据结构及算法原理》百度网盘pdf最新全集下载:

链接: https://pan.baidu.com/s/1c-AnaxEqIfFdcsLOvD_vuA

?pwd=fraj 提取码: fraj

简介：本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。  

1、B+树索引(O(log(n)))：关于B+树索引，可以参考 MySQL索引背后的数据结构及算法原理

2、hash索引：

a 仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询

b 其检索效率非常高，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 索引的查询效率要远高于 B-Tree 索引

c 只有Memory存储引擎显示支持hash索引

3、FULLTEXT索引（现在MyISAM和InnoDB引擎都支持了）

4、R-Tree索引（用于对GIS数据类型创建SPATIAL索引）

---