从上面我们看到的都是单列索引的结构,那么联合索引是如何存储建立索引的呢?其实联合索引只不过比单值索引多了几列,而这些索引列全都出现在索引树上。存储引擎会首先根据第一个索引列排序,如果第一列相等则再根据第二列排序,依次类推。
如图,表有字段 id,a,b,c,其中 id 是主键,并创建了一个联合索引包含列 a,b,c,那么生成如上图所示的的 B+ 树索引结构。
查找过程
还是以上表为例,我们执行语句: select * from T1 where a = 12 and b = 14 and c = 3。存储引擎首先从根节点(一般常驻内存)开始查找,第一个索引的第一个索引列为 1,12 大于 1 小于第二个索引列 56,于是从这俩索引的中间读到下一个节点的磁盘文件地址,从磁盘上 Load 这个节点,通常伴随一次磁盘 IO,然后在内存里去查找。当 Load 叶子节点的第二个节点时又是一次磁盘 IO,比较第一个元素 a = 12,再比较 b 列 c 列查询到符合条件的索引,于是找到该索引下的 data 元素即表的主键值,再从主键索引树上找到最终数据。
最左前缀匹配原则
之所以会有最左前缀匹配原则和联合索引的索引构建方式及存储结构是有关系的。我们创建的idx_t1_bcd(b,c,d) 索引,相当于创建了 (b)、(b,c)、(b,c,d) 三个索引。
联合索引是首先使用多列索引的第一列构建的索引树,用上面 idx_t1_bcd(b,c,d) 的例子就是优先使用 b 列构建(相当于创建了索引(b)),当b列值相等时再以 c 列排序(相当于创建了索引(b,c)),若 c 列的值也相等则以 d 列排序。这种数据存储结构决定了联合索引只能从第一列开始依次进行查找,否则根据无法定位数据。
使用联合索引支持指定前序字段查询,按照后续字段排序。但是要注意查询不能是范围查询如 >、<、in,否则只能取出数据内存排序了。
索引树高度计算
从上面的知识我们知道了索引的构建方式,而决定查询快慢的主要条件就是查询的次数,其实也就是索引树的高度。索引树的高度决定了查询的效率,如果一棵索引树过高势必会影响查询速度,那么数据库的索引树高度究竟是多少呢?
假设:表的记录数是n,每一个 B+Tree 节点平均有 m 个索引 KEY。