深入理解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+树上的结构介绍

        索引覆盖是指如果查询的列恰好是索引的一部分,那么查询只需要在索引文件上进行,不需要回行到磁盘再找数据。这种查询速度非常快,称为”索引覆盖”

        1查询频繁    2区分度高    3长度小    4尽量能覆盖常用查询字段

        索引长度直接影响索引文件的大小,影响增删改的速度,并间接影响查询速度(占用内存多)。因此对于一些长短不同的字节，我们会针对列中的值,从左往右截取部分,来建索引。但是：

        1:截的越短, 重复度越高,区分度越小, 索引效果越不好

        2:截的越长, 重复度越低,区分度越高, 索引效果越好,但带来的影响也越大--增删改变慢,并间影响查询速度.

        所以,我们要在  区分度 + 长度  两者上,取得一个平衡（ distinct 去重 ）

        select count (distinct left (word,6)) / count (*) from tablename

        对于一般的系统应用区别度能达到 0.1 ,索引的性能就可以接受.

        alter table tablename add index word(word(4))

        给字符串类型的字段建立索引效率不高，但是必须要经常查这个字段怎么建索引？

        比如说一个字段url，类型是字符串。那么可以建一个字段 crcurl 来存储url字段crc32后的值，并给 crcurl 建立索引。

        crc32：循环冗余校验。根据网上数据包或计算机文件等数据产生简短固定位数校验码的一种散列函数，主要用来检测或校验数据传输或者保存后可能出现的错误。生成的数字在传输或者存储之前计算出来并且附加到数据后面，然后接收方进行检验确定数据是否发生变化。一般来说，循环冗余校验的值都是32位的整数。

        crc32 是整形，在MySQL中，给整形字段建立索引效率比较高，crc32虽然不能确保唯一性，但是无碍，相同的机率也是极小，关键是可以大大减少查询的范围，给crcurl这个字段建立索引，查询的时候带上crcurl字段就可以利用到索引。

            不允许翻过100页（百度搜索一般到70页左右） 

            首先我们直接大数据分页limit 5000000,10  发现耗时4.41秒

            接下来我们转换方式使用where条件查询，只耗时0.02秒

            2次的查询结果不一致，这是因为数据被物理删除过有空洞.，因此我们可以追加软删除功能

            分析:优化思路是 不查,少查,查索引,少取.

            我们现在必须要查,则只查索引,不查数据,得到id.

            再用id去查具体条目.  这种技巧就是延迟索引.

        分析：limit是先查询再越过，也就是说我们先查询出所有数据再进行跳跃，上图我们越过500W页，还使用了inner join  内存并没有崩掉，这是因为我们子句tmp临时表中只查询了id（索引覆盖，不需要回行去磁盘找数据了）然后拿到这10个id 分别查询这10条数据 。

        排序可能发生2种情况:

        1:对于覆盖索引,直接在索引上查询时,就是有顺序的, using index

        2:先取出数据,形成临时表做filesort(文件排序,但文件可能在磁盘上,也可能在内存中)

        我们的争取目标：取出来的数据本身就是有序的! 利用索引来排序,那么什么时候发生索引排序呢？即查询索引和order by的字段是同一个字段

        goods表中 cat_id与shop_price组成联合索引：

            select goods_id,cat_id,shop_price from goods where cat_id=4 order by shop_price    可以直接利用索引来排序,

             using where按照shop_price索引取出的结果,本身就是有序的

             select goods_id,cat_id,shop_price from goods order by click_count

              using filesort用到了文件排序,即取出的结果再次排序

        重复索引是指 在同1个列(如age), 或者顺序相同的几个列(age,school), 建立了多个索引,称为重复索引,重复索引没有任何帮助,只会增大索引文件,拖慢更新速度。

        冗余索引是指2个索引所覆盖的列有重叠, 称为冗余索引。比如x,m,列，加索引 index x(x),  index xm(x,m) x,xm索引, 两者的x列重叠了,  这种情况,称为冗余索引. （mx, xm 不是重复的,因为列的顺序不一样）

索引是满足某种特定查找算法的数据结构，而这些数据结构会以某种方式指向数据，从而实现高效查找数据。

具体来说 MySQL 中的索引，不同的数据引擎实现有所不同，但目前主流的数据库引擎的索引都是 B+ 树实现的，B+ 树的搜索效率，可以到达二分法的性能，找到数据区域之后就找到了完整的数据结构了，所有索引的性能也是更好的。

---