为什么范围后索引会失效 存储引擎不能使用索引中范围条件右边的列

x33g5p2x  于2022-02-21 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(515)

比如说有三个字段 a b c,建立复合索引a_b_c。此时叶子节点的数据排序后可能为

(a=1 b=1 c=1) (a=1 b=2 c=1) (a=1 b=2 c=3)
(a=2 b=2 c=3) (a=2 b=2 c=5) (a=2 b=5 c=1) (a=2 b=5 c=2)
(a=3 b=0 c=1) (a=3 b=3 c=5) (a=3 b=8 c=6)

查找

select a,b,c from table where a = 2 and b = 5 and c = 2

先根据a = 2找到第二行的四条数据

(a=2 b=2 c=3) (a=2 b=2 c=5) (a=2 b=5 c=1) (a=2 b=5 c=2)

然后根据b=5查到两条

(a=2 b=5 c=1) (a=2 b=5 c=2)

最后根据c=2查到目标数据

(a=2 b=5 c=2)

现在使用了范围条件

select a,b,c from table where a = 2 and b >1 and c = 2

先根据a = 2找到第二行的四条数据

(a=2 b=2 c=3) (a=2 b=2 c=5) (a=2 b=5 c=1) (a=2 b=5 c=2)

然后根据b>1查到四条数据

(a=2 b=2 c=3) (a=2 b=2 c=5) (a=2 b=5 c=1) (a=2 b=5 c=2)

此时要查找c=2了,但发现四条数据的c分别是3,5,1,2无序!所以索引失效!

总结

因为前一个条件相同的情况下 当前条件才会是有序的。当前一个条件不同 那么无法保证当前条件为有序的 所以索引失效

再进一步,假设有以下数据

1(b=2,c=4)
2(b=2,c=5)
3(b=3,c=1)
4(b=3,c=2)

此时对于b 这四个数据都是有序的。
但对于c 只有(1,2)和(3,4)两组数据内部分别有序,如果想让他有序 则需要进行再一次的排序。但是排序的时间复杂度高于遍历数据的时间复杂度 ps:再慢也不会慢过o(n),所以会直接遍历所有数据索引失效。

至于为什么在c后面的索引也会失效(范围后全失效),难道不能查完c之后,把c的结果当成索引继续吗?
再举一组例子
假设有以下数据

1(b=1,c=4,d = 10)
2(b=2,c=5,d = 6)
3(b=2,c=5,d = 7)
4(b=3,c=1,d = 2)
5(b=3,c=5,d = 1)

查找 b>1且 c = 5,d=6,先查出
b>1:

2(b=2,c=5,d = 6)
3(b=2,c=5,d = 7)
4(b=3,c=1,d = 2)
5(b=3,c=5,d = 1)

此时索引失效了。遍历一次结果(假设只对比c的值,这样更快)找到三条数据
c = 5:

2(b=2,c=5,d = 6)
3(b=2,c=5,d = 7)
5(b=3,c=5,d = 1)

这时候发现要查找字段d还是乱的,继续o(n)。
综上所述,范围后的查询字段都不是有序的,所以索引都失效了。

相关文章