8 May 2016 • on MySQL

MySQL索引

原文出处: 张洋

此文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。MySQL支持诸多储存，而各种储存引擎对索引的支持也各不相同，因此MySQL数据库支持入:BTree索引，哈希索引，全文索引等等。本文只关注BTree索引。

数据库索引背后的数据结构

多路查找树的特点是其每一个结点的孩子数可以多于两个，且每一个节点处可以存储多个元素。当然，所有元素之间存在某种排序关系。大多数数据库系统及文件系统都采用B-Tree(B树)或其变种B+Tree作为索引结构。

MySQL索引实现

在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。

MyISAM索引实现

MyISAM索引使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。

这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引(Primary key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引(Primary Key)和辅助索引(Secondary key)在结构上没有任何区别，只是主索引要求Key是唯一的，而辅助索引的Key可以重复。如果我们在Col2上建立一个辅助索引，则此索引的结构如下所示:

同样也是一颗B+Tree,data域保存数据记录的地址。因此，MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相关数据记录。

MyISAM的索引方式也叫做”非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree做为索引结构，但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。在上面我们知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这颗树的叶子节点data域保存了完整的数据记录。这个索引的Key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

上图是InnoDB主索引(同时也是数据文件)的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键(MyISAM可以没有)，如果没有显示指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节(Byte)，类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，下图定义在Col3上的一个辅助索引:

聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

了解这些之后，我们可以知道，InnoDB的存储引擎不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。并且，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身就是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

索引使用策略及优化

MySQL的优化主要分为结构优化(Scheme optimization) 和查询优化(Query optimization)。现在讨论的高性能索引策略主要属于结构化优化范畴。

最左前缀原理与相关优化

高效使用索引的首要条件是知道什么样的查询会使用到索引。这个问题和B+Tree中的”最左前缀原理”有关。

这里先说明一下联合索引的概念。在上文中，我们都是假设索引只引用了单个的列，实际上，MySQL中的索引可以以一定顺序引用多个列，这种索引叫做联合索引，一般的，一个联合索引是一个有序元组<a1,a2,…,an>,其中各个元素均为数据表的一列。另外,单列索引可以看成联合索引元素数为1的特例。

在这里，我们创建如下表

create table titles(
	emp_no INT,
	title varchar(25),
	from_date DATE,
	to_date DATE,
	primary key(emp_no,title,from_date)
)

insert into titles values (1001, 'Senior Engineer', '1996-09-22', '2016-05-09');

insert into titles values (1002, 'Senior Engineer', '1996-09-22', '2016-05-09');

insert into titles values (1003, 'Chen Yanlong', '2016-05-07', '2016-05-09');

1.全列匹配

当按照索引中所有列进行精确匹配(这里精确匹配指 “=” 或 “IN” 匹配)时，索引可以被用到。

EXPLAIN SELECT * FROM titles WHERE emp_no='1001' AND title='Senior Engineer' AND from_date='1996-09-22'

+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref               | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
|  1 | SIMPLE      | titles | const | PRIMARY       | PRIMARY | 34      | const,const,const |    1 |       |
+----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+

这里有一点要注意，理论上索引对顺序是敏感的，但由于MySQL的查询优化器会自动调整where子句的条件顺序以使用合适的索引，例如我们将where中的条件顺序颠倒：

EXPLAIN SELECT * FROM titles WHERE title='Senior Engineer' AND from_date='1996-09-22' AND emp_no='1001'

效果是一样的。

2.最左前缀匹配

当查询条件精确匹配索引的左边连续一个或几个列时，如或<emp_no,title>,索引可以被用到，但是只能用到一部分，即条件所组成的最左前缀。

EXPLAIN SELECT * FROM titles WHERE emp_no='1001'

+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
| id | select_type | table  | type | possible_keys | key     | key_len | ref   | rows | Extra |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
|  1 | SIMPLE      | titles | ref  | PRIMARY       | PRIMARY | 4       | const |    1 |       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------+

3.查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。

EXPLAIN SELECT * FROM titles WHERE emp_no='1001' AND from_date='1996-09-22';

+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
| id | select_type | table  | type | possible_keys | key     | key_len | ref   | rows | Extra       |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
|  1 | SIMPLE      | titles | ref  | PRIMARY       | PRIMARY | 4       | const |    1 | Using where |
+----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+

这种索引使用情况和情况二相同，因为title未提供，所以查询只用到了索引的第一列，虽然后面的from_date也在索引中，但是由于title不存在而无法和左前缀连接，因此需要对结果进行扫描过滤from_date，如果想让from_date也使用索引而不是where过滤，可以增加一个辅助索引<emp_no,from_date>，此时上面的查询会使用这个索引。除此之外，还可以使用一种称之为”隔离列”的优化方法，将emp_no与from_date之间的”坑”填上。

4.查询条件没有指定索引第一列

EXPLAIN SELECT * FROM titles WHERE title='Senior Engineer' AND from_date='1996-09-22'

+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | ALL  | NULL          | NULL | NULL    | NULL |    3 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+

由于不是最左前缀，这样的查询显然用不到索引。

6.范围查询

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

EXPLAIN SELECT * FROM titles WHERE emp_no < '1005' 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 |    3 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
#可以看到，key_len=4,说明后面的title列没有用到索引。

另外，用了”between” 并不意味着就是范围查询。Between实际上相当于IN,即多值精确匹配。(要谨慎区分多值匹配和范围匹配)

EXPLAIN SELECT * FROM titles WHERE emp_no BETWEEN '1001' AND '1005' AND title='Senior Engineer';	

+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
|  1 | SIMPLE      | titles | range | PRIMARY       | PRIMARY | 31      | NULL |    3 | Using where |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+

7.查询条件中含有函数或表达式

如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引。

索引选择性和前缀索引

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

第一种情况是表记录比较少，例如一两千甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好。

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

Index Selectivity = Cardinality/#T

显然，选择性的取值范围为(0,1],选择性越高的索引价值越大，这是由B+Tree的性质决定的。

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

InnoDB的主键选择与插入优化

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

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

如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。而如果使用非自增主键，由于每次插入主键的值近似于随机，因此每次新记录都要被插到现有索引页的某个位置，这样会存在很多频繁的移动，分页操作。