联合索引在B+Tree上的存储结构

有一个T1表，数据如上图。创建了一个联合索引idx_t1_bcd(b,c,d)，b、c、d三列作为联合索引，所有索引列都出现在索引树上，并依次比较三列的大小，在B 树上的结构图如下：

我们先看T1表，他的主键暂且我们将它设为整型自增的 ，InnoDB会使用主键索引在B 树维护索引和数据文件，然后我们创建了一个联合索引（b，c，d）也会生成一个索引树，同样是B 树的结构，只不过它的data部分存储的是联合索引所在行记录的主键值 （上图叶子节点紫色背景部分）。为什么是主键值，而不是整个行记录呢？ 因为这个联合索引是个非聚簇索引。

对于联合索引来说只不过比单值索引多了几列，而这些索引列全都出现在索引树上。对于联合索引，存储引擎会首先根据第一个索引列排序，如上图我们可以单看第一个索引列，如，1 1 5 12 13…它是单调递增的；如果第一列相等则再根据第二列排序，依次类推就构成了上图的索引树，上图中的1 1 4 ，1 1 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. 存储引擎首先从根节点（一般常驻内存）开始查找，第一个索引的第一个索引列为1,12大于1，第二个索引的第一个索引列为56,12小于56，于是从这俩索引的中间读到下一个节点的磁盘文件地址（此处实际上是存在一个指针的，指向的是下一个节点的磁盘位置）。
2. 进行一次磁盘IO，将此节点值加载后内存中，然后根据第一步一样进行判断，发现
   数据都是匹配的，然后根据指针将此联合索引值所在的叶子节点也从磁盘中加载后内存，此时又发生了一次磁盘IO，最终根据叶子节点中索引值关联的主键值 。
3. 根据主键值回表去主键索引树（聚簇索引）中查询具体的行记录。
   

联合索引的最左前缀原则：

之所以会有最左前缀匹配原则和联合索引的索引构建方式及存储结构是有关系的。

首先我们创建的idx_t1_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列索引。

这篇好文章是转载于：学新通技术网