昨天在面试中被问到“联合索引节点结构”这个问题，当时没有答出来，今天在网上查了下各家的答案。发现不少答案存在问题。评论中争论最多的点就是非叶子节点是只包括最左索引字段还是所有索引字段，经过一些资料查找，最终确认非叶子节点中存的是所有索引字段信息。
 
一些认为非叶子节点是只包括最左索引字段的文章
 
https://blog.csdn.net/zgjdzwhy/article/details/84062105
 https://blog.csdn.net/weixin_30531261/article/details/79329722
 ps：贴出来没有任何恶意，只是探讨技术问题。
 
查证非叶子节点结构
 
资料一：在上面链接的博客评论中找到的
 
 上图为https://pdfs.semanticscholar.org/0d7b/8b9172a69fa069c9c38b5f01bd37a498563c.pdf 第7页的图
 
首先，文中指出再非叶子节点中，存了所有索引字段的信息，然后根据字典序，（从左向右权重依次降低，最左匹配原则，可以理解为数字比较大小时，十位与个位的关系，对应于索引字段中第一个与第二个字段，更多字段索引可类推。只有前一个字段为等值时，后续字段索引才有意义。）
 
资料二：
 
 图为《MySQL技术内幕 innoDB存储引擎》一书第二版P216页截图
 图中明确阐述，针对多个键值的B+树索引，每个节点内字段排序与索引排序相同，数据根据节点信息进行分割的逻辑与单列索引相同，差别在于判断数据放在下一层的第几个节点时，需要利用所有字段信息判断字典序。上图中，可以理解为索引第一字段为数字十位，第二字段为个位。因此上图可以理解为，将11，12，21，24，31，32六个数字与上层节点中24进行比较，然后11，12，21比24小所以分到了24左子节点，24，31，32大于等于24，因此分配到右子节点。
 
以上是对于这个问题的一些见解，如有错误希望各位批评指正。

联合索引
 
联合索引（也叫组合索引、复合索引、多列索引）是指对表上的多个列进行索引。联合索引的创建方法跟单个索引的创建方法一样，不同之处仅在于有多个索引列。
 
例如，创建如下表，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';		-- 开启索引下推
 
话说，正常情况下，我们有什么理由来关闭这么好用的功能呢？

一、本文主要讲解的内容有：
 
联合索引在B+树上的存储结构
联合索引的查找方式
为什么会有最左前缀匹配原则
 
在分享这篇文章之前，我在网上查了关于MySQL联合索引在B+树上的存储结构这个问题，翻阅了很多博客和技术文章，其中有几篇讲述的与事实相悖。庆幸的是看到搜索引擎列出的有一条是来自思否社区的问答，有答主回答了这个问题，贴出一篇文章和一张图以及一句简单的描述。PS：贴出的文章链接已经打不开了。
 所以在这样的条件下这篇文章就诞生了。
 
二、联合索引的存储结构
 
下面就引用思否社区的这个问答来展开我们今天要讨论的联合索引的存储结构的问题。
 
来自思否的提问，联合索引的存储结构，有码友回答如下：
 
 联合索引 bcd , 在索引树中的样子如图 ， 在比较的过程中 ，先判断 b 再判断 c 然后是 d 。
 
例子：
 
 
 
首先，表T1有字段a,b,c,d,e，其中a是主键，除e为varchar其余为int类型，并创建了一个联合索引idx_t1_bcd(b,c,d)，然后b、c、d三列作为联合索引，在B+树上的结构正如上图所示。联合索引的所有索引列都出现在索引数上，并依次比较三列的大小。上图树高只有两层不容易理解，下面是假设的表数据以及我对其联合索引在B+树上的结构图的改进。PS：基于InnoDB存储引擎
 
 
T1表的表数据如下：
 
 bcd联合索引在B+树上的结构图：
 
 我们先看T1表，他的主键暂且我们将它设为整型自增的 (PS：至于为什么是整型自增章《MySQL索引那些事》有详细介绍这里不再多说) ，InnoDB会使用主键索引在B+树维护索引和数据文件，然后我们创建了一个联合索引（b，c，d）也会生成一个索引树，同样是B+树的结构，只不过它的data部分存储的是联合索引所在行的主键值（上图叶子节点紫色背景部分），至于为什么辅助索引data部分存储主键值《MySQL索引那些事》也有介绍，感兴趣或还不知道的可以去看一下。
 
下面我们结合这两个图来解释一下：
 对于联合索引来说只不过比单值索引多了几列，而这些索引列全都出现在索引树上。对于联合索引，存储引擎会首先根据第一个索引列排序，如上图我们可以单看第一个索引列，横着看，如，1 1 5 12 13....他是单调递增的；如果第一列相等则再根据第二列排序，依次类推就构成了上图的索引树，上图中的b列都等于1时，则根据c排序，此时c列也相等则按d列排序，如：1 1 4 ，1 1 5，c=4在c=5前面，以及13 12 4,13 16 1,13 16 5就可以说明这种情况。`
 
三、联合索引的查找方式
 
当我们的SQL语言可以应用到索引的时候，比如select * from T1 where b = 12 and c = 14 and d = 3; 也就是T1表中a列为4的这条记录。存储引擎首先从根节点（一般常驻内存）开始查找，第一个索引的第一个索引列为1,12大于1，第二个索引的第一个索引列为56,12小于56，于是从这俩索引的中间读到下一个节点的磁盘文件地址，从磁盘上Load这个节点，通常伴随一次磁盘IO，然后在内存里去查找。当Load叶子节点的第二个节点时又是一次磁盘IO，比较第一个元素，b=12,c=14,d=3完全符合，于是找到该索引下的data元素即ID值，再从主键索引树上找到最终数据。
 
 
四、最左前缀匹配原则
 
之所以会有最左前缀匹配原则和联合索引的索引构建方式及存储结构是有关系的。首先我们创建的index_bcd(b,c,d)索引，相当于创建了(b)、（b、c）（b、c、d）三个索引，看完下面你就知道为什么相当于创建了三个索引。我们看，联合索引是首先使用多列索引的第一列构建的索引树，用上面idx_t1_bcd(b,c,d)的例子就是优先使用b列构建，当b列值相等时再以c列排序，若c列的值也相等则以d列排序。我们可以取出索引树的叶子节点看一下。
 
 索引的第一列也就是b列可以说是从左到右单调递增的，但我们看c列和d列并没有这个特性，它们只能在b列值相等的情况下这个小范围内递增，如第一叶子节点的第1、2个元素和第二个叶子节点的后三个元素。由于联合索引是上述那样的索引构建方式及存储结构，所以联合索引只能从多列索引的第一列开始查找。所以如果你的查找条件不包含b列如（c,d）、(c）、(d)是无法应用缓存的，以及跨列也是无法完全用到索引如(b,d)，只会用到b列索引。
 
五、后记
 
MySQL索引及知识非常广泛，本文只是涉及到其中一部分。如与排序（ORDER BY）相关的索引优化及覆盖索引（Covering index）的话题本文并未涉及，同时除B-Tree索引外MySQL还根据不同引擎支持的哈希索引、全文索引等等本文也并未涉及。如果有机会，希望再对本文未涉及的部分进行补充吧。
 
本文转自：https://juejin.im/post/6844904073955639304

最近在学习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是按照第一个关键字进行索引排列的。
 
有助于理解联合索引的一个例子
 
假设数据 表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 xxx on 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 T where a=1 and b=3 的时候，
数据库系统可以直接从索引文件中直接二分法找到A=1的记录，
然后再B=3的记录。
但如果你 where b=3 则需要遍历这个索引表的全部！
 
这样的解释，参考过别人的文章，自己也有思考过，但并不能确定实际上的结构就是这种。但是，也算是学到了许多东西，像是明白了为什么会有最左原则的存在。