索引一直是数据库中非常重要的概念,所以了解索引相关的知识是转入后端开发中必不可少的一环。这篇文章是我从开始做后端开发之后至今学习关于索引知识的一个总结,从原先很多概念的模糊和不理解到现在大致有一个比较清楚的认知,尽量会把关于索引的一些点以及为什么需要这么做给解释明白,包括使用 InnoDB 引擎的 MySQL 索引的相关概念,以及如何针对 InnoDB 进行索引的设计和使用,以及三星索引的概念,会从我所了解到的知识去解释为什么需要这样,如果有错误的地方还请指出。
B+ Tree
在 InnoDB 中,索引使用的数据结构是 B+ Tree,这里的 B 是 Balance 的意思。B 类树的一个很鲜明的特点就是树的层数比较少,而每层的节点都非常多,树的每个叶子节点到根节点的距离都是相同的(这也是为什么叫 Balance Tree 的原因),另外,树的每一个节点都是一个数据页,这样每个节点只需要一次 IO 就可以全部读取。这样的结构保证了查询数据时能尽量少地进行磁盘 IO,同时保证 IO 的稳定性。
B+ Tree 和 B Tree 不同,B+ Tree 中,只能将数据存储在叶子结点中,内部节点将只包含指针,而 B Tree 可以将数据存储在内部的叶节点中。因此 B+ Tree 的关键优势是中间节点不包含数据,因此 B+ Tree 的大小远小于 B Tree,并且可以将更多数据存储到存储器中。另外,B+ Tree 的每一个叶子节点包含了到相邻的节点的链接,这样可以快速地进行范围遍历。
在上面的叶子节点下,假设有多个名为 BX 和 iCell 的员工,他们的年龄都不太一样,是先按照 name 排序,再按照 age 进行排序。
查询 1:
SELECT * FROM employees WHERE name='BX' AND age=19 AND gender=0;
上述这种查询,根据 (name, age, gender) 这个索引树来查找,找到 id 为 2 的索引数据符合条件,然后通过相邻的节点链接继续查找,发现下一个数据不符合条件,最终命中索引的就是 id 为 2 的这一条数据,因为是要查找行的所有数据,所以再根据 id 为 2 去主键索引树中继续回表查找,得到结果数据。
查询 2:
SELECT * FROM employees WHERE name='iCell';
根据 (name, age, gender) 这个索引树来查找,找到 id 为 3 的索引数据符合条件,然后通过相邻的节点链接继续查找,发现下一个数据也符合条件,继续根据节点链接查找,直到发现数据已经不符合条件了,于是命中索引的就是 id 为 3,4,5 的几条数据,然后继续根据这几个 id 值进行回表操作,得到结果数据。
查询 3:
SELECT * FROM employees WHERE age=17;
根据“最左前缀”原则,并不存在 age 为前缀的索引,所以这个查询无法使用 (name, age, gender) 这个索引树进行数据查找,得去主索引中进行全表扫描,这无非是非常慢的。所以如果想让这个查询命中索引,得单独为 age 添加索引或者添加 age 为前缀的联合索引。或者,这类情况还有一种方法,就是给跳过的索引列使用 IN 的查询方式让其发生“最左前缀”匹配,但是在这里 name 这个字段不适合用 IN 这种查询方法。
查询 4:
SELECT * FROM employees WHERE name like 'B%' AND age=17;
SELECT * FROM employees WHERE name='iCell' AND age > 18 AND gender=1;
由于 B+ Tree 的限制,当查询中出现有某个列的范围查询,则这个范围查询后面的列都无法使用索引。上面的查询中,like B%和 age > 18都是范围查询,所以后面的查询不能通过索引树来直接查找。
对于此种情况,MySQL 5.6 版本增加了 Index Condition Pushdown 技术,如果查询中 where 语句可以使用索引中已有的字段(比如这里就是 name,age, gender),在遍历索引时对这些字段先做判断直接过滤掉不满足条件的值,减少引擎层访问表的次数和 MySQL Server 层访问存储引擎的次数。但是这种技术跟“最左前缀”并无冲突,只是做了数据过滤的优化。
查询 5:
SELECT * FROM employees WHERE employee_id=11;
注意看之前的数据表定义,employee_id 是 varchar 类型,但这个查询语句中将其与数字类型做比较,这时候会触发 MySQL 的隐式类型转换,将字符串转换成数字进行比较,也就是说上述的语句相当于:
SELECT * FROM employees WHERE CAST(employee_id AS int)=11;
SELECT age, gender FROM employees WHERE name='iCell';
这种情况类似于查询 2 中所举的例子,但是这个查询的结果要求只返回 age 和 gender,而 age 和 gender 的值是包含在索引中的,这样就可以直接返回而不用再进行回表查询了。如果一个索引包含所有需要查询的字段的值,则为覆盖索引,使用覆盖索引不需要进行回表操作,能增加数据查询效率
ORDER BY 如何使用索引
要说 ORDER BY 如何利用索引进行排序,得先弄清楚 ORDER BY 本身是如何进行排序的。在 MySQL 中,会给每个线程分配一块内存空间 buffer 用于排序,还有一个参数叫做 max_length_for_sort_data,这个参数作用是用来规定排序返回行的字段长度,默认值是 1024,最小值为 4,如果排序返回行的字段长度没有超过这个参数的值,就会使用一次访问排序,否则使用二次访问排序。
现在我们还是通过上面这张 employees 表来说明问题,有以下语句:
SELECT name, age, employee_id FROM employees WHERE name='iCell' ORDER BY employee_id;
现在我要查的排序的返回字段只包括 name, age 和 employee_id,在默认情况下肯定不会超过 1024,所以会使用一次访问排序,流程如下:
初始化 buffer
根据最左匹配原则命中 name 为 'iCell' 的值,根据辅助索引找出主键 id;
根据主键 id 取出整行的值,然后将 name, age 和 employee_id 这三个返回列的的值存入到 buffer 中;
根据主键 id 取出整行的值,然后将排序行 employee_id 以及 primary key 的值存入到 buffer 中;
重复以上 2 和 3 的步骤,直到不再满足查询条件为止;
对 buffer 中的数据根据 employee_id 进行排序;
根据排序结果中的 primary key,就会回表操作,并将最终结果返回;
以上两种排序,无非是 MySQL 认为内存够不够用,够用的话就多利用内存而避免过多的回表操作从而增加磁盘访问。那如果排序申请的内存空间不过用了怎么办?参数 sort_buffer_size 就是控制排序内存空间大小的,如果内存不够用,就会使用磁盘临时文件做外部归并排序。
知道了以上排序操作,再结合之前覆盖索引以及 B+ Tree 索引的逻辑,是不能就有办法去优化 ORDER BY 的流程了。首先,不管是一次访问排序还是二次访问排序,都要在 buffer 对数据做排序操作,而 B+ Tree 本身的叶子结点就是有序排列的,所以只要能做到排序行也能按照最左匹配原则匹配到索引,就可以避免内存排序的步骤了。另外,上述的排序步骤中还需要进行回表操作,那么只要查询的语句能命中覆盖索引,是不是就能够避免回表操作了。进一步,如何可以使用同一个索引既满足排序又用于查找行那就相当不错了。
三星索引
在《高性能 MySQL》书中提到了一本书叫《Relational Database index design and the optimizers》,书中有一个概念是“三星索引”,它是这样定义的:
满足第一颗星:取出 WHERE 语句后的相关的列,将这些列作为索引最开始的列,这样可以利用索引来尽可能的过滤不必要的数据,减少数据处理的规模;
满足第二颗星:将 ORDER BY 列加入到索引中,不改变这些列的顺序,不考虑第一颗星已经出现的列,利用索引进行排序;