联合指数的最左侧前缀原则属于高频面试题,大多数学生都必须知道,但不符合最左侧前缀的部分会发生什么(指数向下推)
[En]
The leftmost prefix principle of the joint index belongs to the high-frequency interview questions, which most students must know, but what happens to those parts that do not meet the leftmost prefix (index push down)
指数下推并不是一个高频问题,应该没有多少学生知道它(但这并不意味着它很难,它很容易)。学着打包一个浪杯。
[En]
Index push down is not a high-frequency problem, there should not be many students who know it (but that doesn’t mean it’s difficult, it’s easy). Learn to pack a wave cup.
老规矩,背诵版在文末。点击 大厂面试火箭计划 可以直达我收录整理的各大厂面试真题
引子
看下面这张用户表,包含主键 id、身份证号 id_card、姓名 name、年龄 age和性别 sex,并且在 id_card 上建立了辅助索引(普通索引/非聚集索引)
如果现在有一个 高频请求,要根据市民的身份证号查询他的姓名:
select name from user where id_card = xxx;
众所周知,这会导致回表查询,通过 id_card 这棵辅助索引树只能找到主键 id,然后需要再回到主键索引(聚集索引)树上根据主键 id 查找相应的 name。
所以,这个时候,我们可以建立一个 (id_card, name) 的联合索引来进行优化,对于这条语句来说,也就是覆盖索引,在这个高频请求上用到覆盖索引,不再需要回表查整行记录,大幅减少了语句的执行时间。
然而,维护索引字段总是要付出代价的。如果您为每个查询设计一个联合索引,那么索引是否过多?相反,为单个不频繁的请求创建联邦索引是否有点浪费。因此,我们在构建冗余索引以支持覆盖索引时需要做一些权衡。
[En]
However, the maintenance of index fields always comes at a cost. If you design a federated index for each query, is there too many indexes? Conversely, * is it a bit wasteful to create a federated index for a single infrequent request * . So we need to make some tradeoffs when building * redundant indexes * to support overlay indexes.
具体地说,我们应该做什么?
[En]
Specifically, what should we do?
最左前缀原则
B+ 树这种索引结构,可以利用联合索引的 “最左前缀” 来定位记录。
联邦索引的最左边的前缀原则是什么?
[En]
What is the leftmost prefix principle of federated indexes?
从本质上来说,联合索引也是一棵 B+ 树,不同的是联合索引的键值的数量不是 1,而是大于等于 2。我们来看下两个整型列组成的联合索引,假定两个键值的名称分别为 a、b
从图中可以看到多个键值的 B+ 树情况, 键值都是排序的。通过叶子节点可以逻辑上顺序读取所有数据,就上面图中所示,即为 (1,1)、(1、2)、(2、1)、(2、4)、(3、1)、(3、2),数据是按照 (a, b) 的顺序进行存放。
📌 这里 ” 键值都是排好序” 的这种说法可能会让大伙很疑惑,似乎只有 a 列是排序的,b 列并没有排序啊。
注意!这里的排序意味着确定第一个键,对于具有相同键的记录,查询的结果是对第二个键进行排序。
[En]
Be careful! The sort here means that the first key is determined, and for records with the same key, the result of the query is the sorting of the second key.
这也是 使用联合索引的第二个好处,即已经对第二个键值进行了排序处理,可以避免多一次排序操作。举个例子:有些应用程序都需要查询某个用户的购物情况,并按照时间进行排序,取出最近 n 次的购买记录,这时使用联合索引就可以避免多一次排序操作,因为索引本身在叶子节点已经排序了。
更进一步说,假设有联合索引(a,b,c),下列语句可以直接通过联合索引得到结果:
SELECT ... FROM TABLE WHERE a=xxx ORDER BY b
SELECT ... FROM TABLE WHERE a=xxx AND b=xxx ORDER BY c
但是对于下面的语句,联合索引不能直接得到结果,其还需要执行一次排序操作,因为索引 (a,c) 并未排序:
SELECT ... FROM TABLE WHERE a=xxx ORDER BY c
说了这么多,它似乎与最左边的前缀无关。
[En]
Having said so much, it seems to have nothing to do with the leftmost prefix.
考虑下,对于下面这条语句,能否用到联合索引(a, b)?
select * from table where a = XXX and b= XXX;
这个当然没问题。
那对于 a 列的单独查询,能否用到联合索引(a, b)?
select * from table where a = XXX;
当然也可以,我们不是说了,a 列是已经排好序的
但是对于 b 列的单独查询则不能使用联合索引(a, b)!
select * from table where b = XXX;
因为 把叶子节点中的 b 值单独拎出来看它不是有序的:1、2、1、4、1、2,因此对于 b 的查询是使用不到 (a,b) 这个联合索引的。
同样的道理,对于(a, b, c)联合索引来说,查询 (a, b) 可以用到这个联合索引,但是查询 (b, c) 就没办法使用这个联合索引,因为 b 和 c 列的有序性都是依托于 a 列的存在的。
This,就是联合索引的最左前缀原则, 只要查询的是联合索引的最左 N 个字段,就可以利用该联合索引来加速查询。
基于上面最左边的前缀索引的描述和用户表的例子,我们来讨论一个问题:在建立联合索引时,如何安排索引中的字段顺序?
[En]
Based on the description of the leftmost prefix index above and the example of the user table, let’s discuss a question: * how to arrange the order of fields in the index when establishing a federated index?*
有两点原则。
首先,第一原则, 如果通过调整顺序,可以少维护一个索引,那么这个字段顺序往往就是需要优先考虑采用的
很好理解,当已经有了 (a,b) 这个联合索引后,一般就不需要单独在 a 上建立索引了。
那么,再思考一个问题:如果既有联合查询 (a,b),又有基于 a、b 各自的查询呢?
显然,如果查询条件里面只有 b 的语句,是无法使用 (a,b) 这个联合索引的,这时候你不得不维护另外一个 b 列的索引,也就是说你需要同时维护 (a,b)、(b) 这两个索引。
例如,有三个高频查询要求:
[En]
For example, there are three high-frequency query requirements:
- 根据 name 查询 id:
select id from user where name = xxx;
- 根据 age 查询 id:
select id from user where age= xxx;
- 根据 name 和 age 查询 id:
select id from user where name = xxx and age = xxx;
此时,我们有两个索引选项:
[En]
At this point, we have two options for indexing:
- 联合索引 (age, name) + 单字段索引 (name)
- 联合索引 (name, age) + 单字段索引 (age)
怎么选?
在这个场景中,我们需要考虑的原则是空间。
[En]
In this scenario, the principle we need to consider is * space * .
显然,name 字段是要比 age 字段大的,所以,第二种选择占用的空间要小于第一种选择,推荐大伙儿使用第二种选择:联合索引 (name, age) + 单字段索引 (age)
索引下推
最左边的前缀可以用来定位索引中的记录,那么那些与最左边的前缀不匹配的部分怎么办?
[En]
The leftmost prefix can be used to locate records in the index, so what about those parts that do not match the leftmost prefix?
以用户表的联合索引(name, age)为例,假设现在有一个需求,找出所有姓 “张” 并且 20 岁的男性:
select * from tuser where name like '张%' and age = 20 and sex = male
《高性能 MySQL》 书中提到: 对于联合索引,如果查询中有某个列的范围查询,则其右边所有列都无法使用索引进行快速定位
所以对于这条语句来说,其实并不能完全踩中 (name, age) 这个联合索引,他只能踩到 name。
具体来说,这个语句在搜索(name,age)的联合索引树的时候,并不会去看 age 的值,只是按顺序把 “name 第一个字是张” 的记录一条条取出来,然后开始回表,到主键索引上找出数据行,再一个一个判断其他条件是否满足。从下图可以看出来,需要回表 3 次。
这是 MySQL 5.6 之前的做法,简单总结,当进行索引查询时,首先根据索引来查找记录,然后再根据 where 条件来过滤记录
而 MySQL 5.6 开始,数据库在取出索引的同时,会根据 where 条件直接过滤掉不满足条件的记录,减少回表次数。这就是 索引下推 (Index Condition Pushdown,ICP) ,一种根据索引进行查询的优化方式
从图中可以看出来,InnoDB 在 (name,age) 索引内部就判断了 age 是否等于 20,对于不等于 20 的记录,直接判断并跳过,所以只需要对 ID1 这条记录进行回表判断就可以了。
🥸 面试官:讲一下联合索引的最左前缀原则,为什么得最左匹配,不按照这个来为什么失效?
😎 小牛肉:最左前缀原则就是只要查询的是联合索引的最左 N 个字段,就可以利用该联合索引来加速查询。
不按照最左匹配来为什么失效,其原因就在于联合索引的 B+ 树中的键值是排好序的。不过,这里指的排好序,其实是相对的,举个例子,有 (a, b, c) 联合索引,a 首先是排序好的,而 b 列是在 a 列排序的基础上做的排序,同样的 c 是在 a,b 有序的基础上做的排序。所以说,如果有where a = xxx order by b = xxx
这种请求的话,是可以直接在这颗联合索引树上查出来的,不用对 b 列进行额外的排序;而如果是where a = xxx order by c = xxx
这种请求的话,还需要额外对 c 列进行一次排序才行。
另外,如果有对 a,b,c 的联合条件查询的话,并且 a 是模糊匹配或者说是范围查询的话,其实并不能完全踩中联合索引(a,b,c),a 列右边的所有列都无法使用索引进行快速定位了。所以这个时候就需要进行回表判断。也就是说数据库会首先根据索引来查找记录,然后再根据 where 条件来过滤记录。
不过在 MySQL 5.6 中支持了索引下推 ICP,数据库在取出索引的同时,会根据 where 条件直接过滤掉不满足条件的记录,减少回表次数
大厂面试火箭计划
点击 大厂面试火箭计划 直达
目前,网上提供的面试问题答案大多只有几行,没有逻辑。面试官一听到这句话就知道它已经被记住了。我认为这不能满足大多数学生的要求。
[En]
At present, most of the answers to the interview questions provided on the Internet are just a few lines, and there is no logic. The interviewer knows it is memorized as soon as he hears it. I don’t think this can meet the demands of most of the students.
如何让面试官知道我不是背诵?如何知道它是什么,为什么?
[En]
How to let the interviewer know that I am not a recite? How to know what it is and why?
So,我希望的是以面试题为导向,建立完整的知识体系,让八股文变得有价值,而不是东一锤西一棒
后续准备以牛客上的面经帖子为指导,为每个面试问题提供口语化朗诵版+更专业的详解版。已经知道的学生呢可以直接阅读背诵的版本,不太了解的学生可以和详细的讲解版本一起阅读。
[En]
The follow-up preparation is guided by the noodle scripture posts on Niu Ke, providing a colloquial recitation version + a more professional detailed explanation version for each interview question. Students who already know, uh, can read the recitation version directly, and those who don’t know much about it can read it together with the detailed explanation version.
所有的面试问题都已经按照知识体系的顺序进行了排序,我会增加一些补充问题来改进。
[En]
All the interview questions have been sorted according to the order of the knowledge system, and I will add some supplementary questions for improvement.
Original: https://www.cnblogs.com/cswiki/p/15701065.html
Author: 飞天小牛肉
Title: 最左前缀有手就会,那索引下推呢?
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/507952/
转载文章受原作者版权保护。转载请注明原作者出处!