Mysql联合索引在B+树上的存储结构及数据查找方式

您所在的位置:网站首页 索引树结构 Mysql联合索引在B+树上的存储结构及数据查找方式

Mysql联合索引在B+树上的存储结构及数据查找方式

2023-10-23 15:22| 来源: 网络整理| 查看: 265

假设我们有一个表user,字段a,b,c,d,e,其中a是主键,除e为varchar其余为int类型,并创建了一个联合索引idx_t1_bcd(b,c,d),然后b、c、d三列作为联合索引,那么执行下面几个SQL,来看一下索引执行情况: 

 select * from user where b= 12 and c= 14 and d = 3 // 索引全匹配

select * from user where b= 12 and c= 14 // 索引部分匹配

select * from user where b= 12 and d = 3 // 索引部分匹配

select * from user where c= 12 and d = 3 // 索引无法匹配

可以看到,对于联合索引,全部命中索引字段可以执行索引;部分命中并符合最左匹配原则,也可能会执行索引;不满足最左匹配原则,则无法命中索引,那么这是为什么呢? 我们来分析一下对于联合索引的B+树的数据结构。

联合索引的B+树结构

B+树结构图:

表内容图:

我们先看表,他的主键暂且我们将它设为整型自增的,InnoDB会使用主键索引在B+树维护索引和数据文件,然后我们创建了一个联合索引(b,c,d)也会生成一个索引树,同样是B+树的结构,只不过它的data部分存储的是联合索引所在行的主键值。

好了大致情况都介绍完了。下面我们结合这俩图来解释一下。

对于联合索引来说只不过比单值索引多了几列,而这些索引列全都出现在索引树上。对于联合索引,存储引擎会首先根据第一个索引列b排序,如上B+树结构图我们可以单看第一个索引列(横着看),如,1 1 5 12 13....他是单调递增的;如果第一列相等则再根据第二列排序,依次类推就构成了上图的索引树,上图中(竖着看)的1 1 4 以及13 12 4,13 16 1,13 16 5就可以说明这种情况。

联合索引的查找方式

当我们的SQL语言可以应用到索引的时候,比如 select * from user where b = 12 and c = 14 and d = 3; 也就是表中a列为4的这条记录。

存储引擎首先从根节点(一般常驻内存)开始查找,第一个索引的第一个索引列为1,12大于1,第二个索引的第一个索引列为56,12小于56, 于是从这俩索引的中间读到下一个节点的磁盘文件地址,从磁盘上Load这个节点,通常伴随一次磁盘IO,然后在内存里去查找。 当Load叶子节点的第二个节点时又是一次磁盘IO,比较第一个元素,b=12,c=14,d=3完全符合,于是找到该索引下的data元素即ID值,再从主键索引树上找到最终数据

最左前缀匹配原则

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

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

参考:zhuanlan.zhihu.com/p/109623980



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3