MySQL索引背后的数据结构及算法原理(三)

已有 3346人阅读此文 - - 数据库

情况六:范围查询。

EXPLAIN SELECT * FROM employees.titles WHERE emp_no < '10010' and title='Senior Engineer';+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 4       | NULL |   16 | Using where |+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

范围列可以用到索引(必须是最左前缀),但是范围列后面的列无法用到索引。同时,索引最多用于一个范围列,因此如果查询条件中有两个范围列则无法全用到索引。

EXPLAIN SELECT * FROM employees.titlesWHERE emp_no < '10010'AND title='Senior Engineer'AND from_date BETWEEN '1986-01-01' AND '1986-12-31';+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 4       | NULL |   16 | Using where |+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方,那就是仅用explain可能无法区分范围索引和多值匹配,因为在type中这两者都显示为range。同时,用了“between”并不意味着就是范围查询,例如下面的查询:

EXPLAIN SELECT * FROM employees.titlesWHERE emp_no BETWEEN '10001' AND '10010'AND title='Senior Engineer'AND from_date BETWEEN '1986-01-01' AND '1986-12-31';+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 59      | NULL |   16 | Using where |+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

看起来是用了两个范围查询,但作用于emp_no上的“BETWEEN”实际上相当于“IN”,也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配,否则会对MySQL的行为产生困惑。

情况七:查询条件中含有函数或表达式。

很不幸,如果查询条件中含有函数或表达式,则MySQL不会为这列使用索引(虽然某些在数学意义上可以使用)。例如:

EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND left(title, 6)='Senior';+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+| id | select_type | table  | type | possible_keys | key     | key_len | ref   | rows | Extra       |+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+|  1 | SIMPLE      | titles | ref  | PRIMARY       | PRIMARY | 4       | const |    1 | Using where |+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

虽然这个查询和情况五中功能相同,但是由于使用了函数left,则无法为title列应用索引,而情况五中用LIKE则可以。再如:


EXPLAIN SELECT * FROM employees.titles WHERE emp_no - 1='10000';+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows   | Extra       |+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+|  1 | SIMPLE      | titles | ALL  | NULL          | NULL | NULL    | NULL | 443308 | Using where |+----+-------------+--------+------+---------------+------+---------+------+--------+-------------+

显然这个查询等价于查询emp_no为10001的函数,但是由于查询条件是一个表达式,MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度,因此在写查询语句时尽量避免表达式出现在查询中,而是先手工私下代数运算,转换为无表达式的查询语句。

索引选择性与前缀索引

既然索引可以加快查询速度,那么是不是只要是查询语句需要,就建上索引?答案是否定的。因为索引虽然加快了查询速度,但索引也是有代价的:索引文件本身要消耗存储空间,同时索引会加重插入、删除和修改记录时的负担,另外,MySQL在运行时也要消耗资源维护索引,因此索引并不是越多越好。一般两种情况下不建议建索引。

第一种情况是表记录比较少,例如一两千条甚至只有几百条记录的表,没必要建索引,让查询做全表扫描就好了。至于多少条记录才算多,这个个人有个人的看法,我个人的经验是以2000作为分界线,记录数不超过 2000可以考虑不建索引,超过2000条可以酌情考虑索引。

另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性(Selectivity),是指不重复的索引值(也叫基数,Cardinality)与表记录数(#T)的比值:

Index Selectivity = Cardinality / #T

显然选择性的取值范围为(0, 1],选择性越高的索引价值越大,这是由B+Tree的性质决定的。例如,上文用到的employees.titles表,如果title字段经常被单独查询,是否需要建索引,我们看一下它的选择性:

SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles;+-------------+| Selectivity |+-------------+|      0.0000 |+-------------+

title的选择性不足0.0001(精确值为0.00001579),所以实在没有什么必要为其单独建索引。

有一种与索引选择性有关的索引优化策略叫做前缀索引,就是用列的前缀代替整个列作为索引key,当前缀长度合适时,可以做到既使得前缀索引的选择性接近全列索引,同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。

从图12可以看到employees表只有一个索引<emp_no>,那么如果我们想按名字搜索一个人,就只能全表扫描了:

EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido';+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+| id | select_type | table     | type | possible_keys | key  | key_len | ref  | rows   | Extra       |+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+|  1 | SIMPLE      | employees | ALL  | NULL          | NULL | NULL    | NULL | 300024 | Using where |+----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+

如果频繁按名字搜索员工,这样显然效率很低,因此我们可以考虑建索引。有两种选择,建<first_name>或<first_name, last_name>,看下两个索引的选择性:

SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees;+-------------+| Selectivity |+-------------+|      0.0042 |+-------------+SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees;+-------------+| Selectivity |+-------------+|      0.9313 |+-------------+

<first_name>显然选择性太低,<first_name, last_name>选择性很好,但是first_name和last_name加起来长度为30,有没有兼顾长度和选择性的办法?可以考虑用first_name和last_name的前几个字符建立索引,例如<first_name, left(last_name, 3)>,看看其选择性:

SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;+-------------+| Selectivity |+-------------+|      0.7879 |+-------------+

选择性还不错,但离0.9313还是有点距离,那么把last_name前缀加到4:

SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;+-------------+| Selectivity |+-------------+|      0.9007 |+-------------+

这时选择性已经很理想了,而这个索引的长度只有18,比<first_name, last_name>短了接近一半,我们把这个前缀索引 建上:

ALTER TABLE employees.employeesADD INDEX `first_name_last_name4` (first_name, last_name(4));

此时再执行一遍按名字查询,比较分析一下与建索引前的结果:

SHOW PROFILES;+----------+------------+---------------------------------------------------------------------------------+| Query_ID | Duration   | Query                                                                           |+----------+------------+---------------------------------------------------------------------------------+|       87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' ||       90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' |+----------+------------+---------------------------------------------------------------------------------+

性能的提升是显著的,查询速度提高了120多倍。

前缀索引兼顾索引大小和查询速度,但是其缺点是不能用于ORDER BY和GROUP BY操作,也不能用于Covering index(即当索引本身包含查询所需全部数据时,不再访问数据文件本身)。

InnoDB的主键选择与插入优化

在使用InnoDB存储引擎时,如果没有特别的需要,请永远使用一个与业务无关的自增字段作为主键。

经常看到有帖子或博客讨论主键选择问题,有人建议使用业务无关的自增主键,有人觉得没有必要,完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点,大多数论据都是业务层面的。如果从数据库索引优化角度看,使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。

上文讨论过InnoDB的索引实现,InnoDB使用聚集索引,数据记录本身被存于主索引(一颗B+Tree)的叶子节点上。这就要求同一个叶子节点内(大小为一个内存页或磁盘页)的各条数据记录按主键顺序存放,因此每当有一条新的记录插入时,MySQL会根据其主键将其插入适当的节点和位置,如果页面达到装载因子(InnoDB默认为15/16),则开辟一个新的页(节点)。

如果表使用自增主键,那么每次插入新的记录,记录就会顺序添加到当前索引节点的后续位置,当一页写满,就会自动开辟一个新的页。如下图所示:

blob.png

图13

这样就会形成一个紧凑的索引结构,近似顺序填满。由于每次插入时也不需要移动已有数据,因此效率很高,也不会增加很多开销在维护索引上。

如果使用非自增主键(如果身份证号或学号等),由于每次插入主键的值近似于随机,因此每次新纪录都要被插到现有索引页得中间某个位置:

1427121327300087244.png

图14

此时MySQL不得不为了将新记录插到合适位置而移动数据,甚至目标页面可能已经被回写到磁盘上而从缓存中清掉,此时又要从磁盘上读回来,这增加了很多开销,同时频繁的移动、分页操作造成了大量的碎片,得到了不够紧凑的索引结构,后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。

因此,只要可以,请尽量在InnoDB上采用自增字段做主键。


期待你一针见血的评论,Come on!