联合索引的分支块包含索引键值列以及相应的指针，但不是叶子块的所有键值都列举在分支块里，具体跟分支块的指针有关系：
不管是联合索引还是单列索引，分支块都包含两种指针，一种叫LMC，另一种就是分支块的索引行对应的指针。
1.LMC，left most child，每个分支块都会有一个，而且只会有一个，这个指针指向一个索引叶子块，这个LMC指针的特征是，所指向的叶子块，其所包含的索引键值的最大值，小于该分支块所有索引键值的最小值。例如分支的索引键值为(AD,AK，...)，那么LMC所指向的叶子块的索引列值只能是排在AD前面的键值，例如AB,AC等；
2.分支块的索引行对应的指针，首先明确，一个分支块指向多个叶子块，但并不是叶子块里的所有键值都列举在叶子块里。叶子块的内容除了上述说的LMC，其余的即是索引键值+对应的指针，而这个指针所指向的叶子块，其所包含的最小键值都要比该指针在分支块里对应的索引键值大。例如分支块的索引行是AD+指针，那么这个指针所指向的叶子块的最小键值必须比AD大，可以是ADF，可以是AK，但不能是AC。也就是说，分支块的每一个索引行对应的指针，都指向一个叶子块，且指向的叶子块的索引键的最小值，都比这个索引键值大。
图就不画了，脑补吧~

前言
最近在学习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是按照第一个关键字进行索引排列的。
有助于理解联合索引的一个例子
from csdn论坛：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
假设数据 表T (a,b,c) rowid 为物理位置
rowid a b c
(1)   1 1 1
(2)   2 1 13
(3)   2 2 14
(4)   1 3 3
(5)   2 3 12
(6)   1 2 5
(7)   2 3 9
(8)   1 2 2
(9)   1 3 6
(10)  2 2 11
(11)  2 2 8
(12)  1 1 7
(13)  2 3 15
(14)  1 1 4
(15)  2 1 10
当你创建一个索引create index xxxon t(a,b),
则索引文件逻辑上等同于如下
a b rowid
1 1 1
1 1 12
1 1 14
1 2 6
1 2 8
1 3 4
1 3 9
2 1 2
2 1 15
2 2 3
2 2 10
2 2 11
2 3 5
2 3 7
2 3 13
当select *from Twhere a=1and b=3 的时候，
数据库系统可以直接从索引文件中直接二分法找到A=1的记录，
然后再B=3的记录。
但如果你where b=3 则需要遍历这个索引表的全部！
最后
这样的解释，参考过别人的文章，自己也有思考过，但并不能确定实际上的结构就是这种。但是，也算是学到了许多东西，像是明白了为什么会有最左原则的存在。
原文链接

 

 

单列索引其实也可以看做联合索引，索引列为1的联合索引，从下图就可以看出联合索引的底层存储跟单列索引时类似的，区别在于联合索引是每个树节点中包含多个索引值，在通过索引查找记录时，会先将联合索引中第一个索引列与节点中第一个索引值进行匹配，匹配成功接着匹配第二个索引列和索引值，直到联合索引的所有索引列都匹配完；如果过程中出现某一个索引列与节点相应位置的索引值不匹配的情况，则无需再匹配节点中剩余索引列，前往下一个节点。



 

 

 

联合索引
联合索引（也叫组合索引、复合索引、多列索引）是指对表上的多个列进行索引。联合索引的创建方法跟单个索引的创建方法一样，不同之处仅在于有多个索引列。
例如，创建如下表，idx_name 是联合索引，索引列为 (name,age)
CREATE TABLE `t_user` (
  `id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键',
  `name` varchar(32) NOT NULL COMMENT '姓名',
  `age` tinyint(3) unsigned NOT NULL COMMENT '年龄',
  `gender` tinyint(3) unsigned NOT NULL COMMENT '性别：1男，0女',
  PRIMARY KEY (`id`),
  KEY `idx_name` (`name`,`age`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

假如表中有如下数据




id
name
age
gender




1
LiLei
18
1


2
HanMeimei
17
0


3
Lucy
17
0


4
Lili
16
0


5
WeiHua
32
0


6
ZhangWei
25
1


7
Ann
36
0


8
Lisa
19
0


9
ZhangWei
18
1


10
Kate
17
1


我们来看一下这棵索引树的结构


从图中我们可以看出，叶子节点中的键值都是按顺序存储的，即(“Ann”,36)、(“HanMeimei”,17)、(“Kate”,17)、(“LiLei”,18)、(“Lili”,16)、(“Lisa”,19)、(“Lucy”,17)、(“WeiHua”,32)、(“ZhangWei”,18)、(“ZhangWei”,25)。
索引会先根据 name 排序，如果 name 相同，再根据 age 进行排序。
联合索引的最左匹配原则
索引的目的其实就是为了提高数据查询的效率，联合索引也一样，使用联合索引时，一定要注意符合最左匹配原则：在通过联合索引检索数据时，从索引中最左边的列开始，一直向右匹配，如果遇到范围查询(>、<、between、like等)，就停止后边的匹配。
假如对字段 (a, b, c) 建立联合索引，如下查询语句可以使用到索引：
where a = xxx
where a = xxx and b = xxx
where a = xxx and b = xxx and c = xxx
where a like 'xxx%'
where a > xxx
where a = xxx order by b
where a = xxx and b = xxx order by c
group by a

当然，像如下：
where b = xxx and a = xxx
where a = xxx and c = xxx and b = xxx

这种查询条件书写顺序不影响对联合索引的使用，因为执行 sql 的时候，MySQL优化器会帮我们调整 where 后 a,b,c 的顺序，让我们用上索引。
而还有一些语句是只能用到联合索引的一部分的。
where a = xxx and c = xxx 可以用到 a 列的索引，用不到 c 列索引。
where a like 'xxx%' and b = xxx 可以用到 a 列的索引，用不到 b 列的索引。
where a > xxx and b = xxx 可以用到 a 列的索引，用不到 b 列的索引。
最需要注意类似下边的这些查询
where b = xxx
where c = xxx
where a like '%xxx'			-- 不满足最左前缀
where d = xxx order by a	-- 出现非排序使用到的索引列 d 
where a + 1 = xxx	-- 使用函数、运算表达式及类型隐式转换等

这些查询语句，完全用不到 (a, b, c) 这个联合索引。
如何选择合适的索引列顺序
建立联合索引时，一般我们遵循的经验是：将选择性最高的列放在索引的最前列。这在某些场景下比较有用，但通常不如避免随机IO和排序那么重要。正确的顺序应该依赖于使用该索引的查询，并且同时需要考虑如何更好的满足排序和分组的需要。
where a = xxx and b = xxx and c = xxx 如果我们的查询是这样的，建索引时，就可以考虑将选择性高的列放在索引的最前列，选择性低的放后边。
如果是 where a > xxx and b = xxx 或 where a like 'xxx%' and b = xxx 这样的语句，可以对 (b, a) 建立索引。
如果是 where a = xxx order by b 这样的语句，可以对 (a, b) 建立索引。
索引下推（索引条件下推）
什么是索引下推（Index Condition Pushdown，ICP）呢？我们通过例子来了解下。
假设我们想从一开始创建的表中，查询 name 以 ‘L’ 开头，并且 age 为 17 的人员信息。
select * from t_user where name like 'L%' and age = 17;

在不用索引下推的情况下，根据前边"最左匹配原则"描述的那样，该查询在联合索引中只有 name 列可以使用到索引，age 列是用不到索引的。在扫描 (‘name’, age) 索引树时，根据 name like 'L%' 这个条件，可以查找到 LiLei、Lili、Lisa、Lucy 四条索引数据，接下来，再根据这四条索引数据中的 id 值，逐一进行回表扫描，从聚簇索引中找到相应的行数据，将找到的行数据返回给 server 层。server 层中，再根据 age = 17 这个条件进行筛选，最终只留下 Lucy 用户的数据信息。
不用索引下推的过程，如下图示：


在使用索引下推的情况下，存储引擎层还是先根据 name like 'L%' 这个条件，查找到 LiLei、Lili、Lisa、Lucy 四条索引数据，不过接下来不是直接进行回表操作，而是根据 age = 17 这个条件，对四条索引数据进行判断筛选，将符合条件的索引对应的 id 进行回表扫描，最终将找到的行数据返回给 server 层。（也就是我们把本应该在 server 层进行筛选的条件，下推到存储引擎层来进行筛选判断了。这个下推的前提是索引中有 age 列信息，如果是其它条件，如 gender = 0，这个即使下推下来也没用）
使用索引下推的过程，如下图示：


由上比较可以看出，使用索引下推优化，可以有效减少回表次数，也可以减少 server 层从存储引擎层接收数据的次数，从而大大提升查询效率。
索引下推是 MySQL 5.6 及以上版本上推出的，用于对查询进行优化。默认情况下，索引下推处于启用状态。我们可以使用如下命令来开启或关闭。
set optimizer_switch='index_condition_pushdown=off'; 	-- 关闭索引下推
set optimizer_switch='index_condition_pushdown=on';		-- 开启索引下推

话说，正常情况下，我们有什么理由来关闭这么好用的功能呢？