5.1 索引基础
在MySQL中，存储引擎在使用索引时，先找到索引的对应值，然后根据匹配的索引找到对应的数据行。假如要运行下面的查询:
select first_name from sakila.actor where actor_id = 5;如果我们在actor_id上建有索引，则MySQL将使用索引找到actor_id=5的行，再返回该索引所对应的数据行。
5.1.1 索引的类型
索引有很多种类型，可以为不同的场景提供更好的性能。在MySQL中，索引是在存储引擎层而不是服务器层实现的。所以并没有统一的索引标准,下面是MySQL支持的索引类型:
- B+Tree索引
传统意义上我们大多数时候谈到索引指的通常是B-Tree索引，而InnoDB使用的是一种优化后的B+Tree这种数据结构做索引。B+Tree通常意味着所有的值都是按照顺序存储的，并且每一个叶子页到根的距离相同。下面是B+Tree的抽象表示，大致反映了InnoDB索引是如何工作的:
一个3阶B+Tree.png
B+Tree索引能够加快访问数据的速度，存储引擎不需要进行全表扫描来获取数据，而逝从索引的根节点，如果是主键进行范围查找的话更快。B+Tree很适合全键值、键值范围或键前缀查找,其中键前缀的查找只适用于最左前缀的查找。现在假如我们有下表:
CREATE TABLE `Peopel` (
`last_name` varchar(50) NOT NULL,
`first_name` varchar(50) NOT NULL DEFAULT '',
`dob` date NOT NULL,
`gender` enum('M','F') NOT NULL,
KEY `key` (`last_name`,`first_name`,`dob`) #组合索引的顺序很重要
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
mysql> select * from people;
+-----------+------------+------------+--------+
| last_name | first_name | dob | gender |
+-----------+------------+------------+--------+
| Allen | Cuba | 1960-01-01 | M |
| Astalre | Angelina | 1980-03-04 | F |
| Yale | Wei | 1993-10-09 | M |
| Yu | Xiao | 1993-02-25 | F |
| Xiang | Chen | 1994-12-29 | M |
+-----------+------------+------------+--------+
- 如果不是按照索引的最左列开始查找，则无法使用索引。如下第一条SQL匹配last_name字段时候走了ref索引，而第二条跳过last_name直接匹配first_name时没有走索引，type=ALL
mysql> explain select * from people where last_name = 'Allen';
+----+-------------+--------+------+---------------+------+---------+-------+------+-----------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+------+---------+-------+------+-----------------------+
| 1 | SIMPLE | people | ref | key | key | 152 | const | 1 | Using index condition |
+----+-------------+--------+------+---------------+------+---------+-------+------+-----------------------+
1 row in set (0.01 sec)
mysql> explain select * from people where first_name = 'Cuba';
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
| 1 | SIMPLE | people | ALL | NULL | NULL | NULL | NULL | 4 | Using where |
+----+-------------+--------+------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)
- 不能跳过索引中的列。如下第一条SQL只走了一次索引last_name，第二条SQL则走了两次索引，ref栏里走了两次const
mysql> explain select * from people where last_name = 'Allen' and dob = '1960-01-01';
+----+-------------+--------+------+---------------+------+---------+-------+------+-----------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+------+---------+-------+------+-----------------------+
| 1 | SIMPLE | people | ref | key | key | 152 | const | 1 | Using index condition |
+----+-------------+--------+------+---------------+------+---------+-------+------+-----------------------+
1 row in set (0.00 sec)
mysql> explain select * from people where last_name = 'Allen' and first_name = 'Cuba';
+----+-------------+--------+------+---------------+------+---------+-------------+------+-----------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+------+---------+-------------+------+-----------------------+
| 1 | SIMPLE | people | ref | key | key | 304 | const,const | 1 | Using index condition |
+----+-------------+--------+------+---------------+------+---------+-------------+------+-----------------------+
1 row in set (0.00 sec)
- 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。如下SQL因为first_name是范围查询type=range，因此最后的dob没有走索引:
mysql> explain select * from people where last_name = 'Yale' and first_name like 'W%' and dob = '1993-10-09';
+----+-------------+--------+-------+---------------+------+---------+------+------+-----------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+------+---------+------+------+-----------------------+
| 1 | SIMPLE | people | range | key | key | 307 | NULL | 1 | Using index condition |
+----+-------------+--------+-------+---------------+------+---------+------+------+-----------------------+
- 哈希索引
哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效。对每一行数据，存储引擎都会对所有的索隐裂计算一个哈希码(hash code)。哈希索引将所有哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，查找速度也非常快，哈希索引也有它的限制:
- 不能使用索引中的值来避免读取行，因为索引中只包含哈希值和行指针。
- 哈希索引数据无法用于排序。
- 不支持索引中部分列的匹配查找，因为哈希码都是根据全部索引列计算生成的。
- 哈希索引只支持等值比较查询(=,in(),<=>)，不支持任何范围查询。
- 哈希冲突会影响查询性能和维护成本。
在MySQL中InnoDB并不显示支持Hash索引，但它有一个"自适应索引"。当InnoDB注意到某些索引值频繁使用时，会在内存中基于B-Tree再创建一个自适应索引。这是一个完全自动的内部行为，用户无法控制或配置。
下面我们可以举个例子创建自定义哈希索引，模拟InnoDB创建哈希索引:
CREATE TABLE `pseudohash` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`url` varchar(255) NOT NULL,
`url_crc` int(10) unsigned NOT NULL DEFAULT '0',
PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;
mysql> explain select * from pseudohash where url = "www.baidu.com" and url_crc = crc32("www.baidu.com");
+----+-------------+------------+------+---------------+------+---------+-------+------+------------------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+------------+------+---------------+------+---------+-------+------+------------------------------------+
| 1 | SIMPLE | pseudohash | ref | url,url_crc | url | 767 | const | 1 | Using index condition; Using where |
+----+-------------+------------+------+---------------+------+---------+-------+------+------------------------------------+
1 row in set (0.00 sec)
mysql> explain select * from pseudohash where url = "www.baidu.com";
+----+-------------+------------+------+---------------+------+---------+-------+------+-----------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+------------+------+---------------+------+---------+-------+------+-----------------------+
| 1 | SIMPLE | pseudohash | ref | url | url | 767 | const | 1 | Using index condition |
+----+-------------+------------+------+---------------+------+---------+-------+------+-----------------------+
1 row in set (0.00 sec)
这样做的好处是url_crc列的索引完成索引，选择性高体积小；而针对url列的字段要做字符串的全匹配，速度相对很慢。这样的缺点是需要维护哈希值，我们可以使用触发器实现自动维护哈希值:
REATE DEFINER=`root`@`%` TRIGGER `crc_ins` BEFORE INSERT ON `pseudohash` FOR EACH ROW BEGIN SET new.url_crc=CRC32(new.url);
END;
CREATE DEFINER=`root`@`%` TRIGGER `crc_upd` BEFORE UPDATE ON `pseudohash` FOR EACH ROW BEGIN SET new.url_crc=CRC32(new.url);
END;
5.2 索引的优点
- 索引阿达减少了服务器需要扫描的数据量。
- 帮助服务器避免排序和临时表。
- 索引可以将随机I/O变成顺序I/O。
5.3 高性能的索引策略
5.3.1 独立的列
"独立的列"是指索引列不能是表达式的一部分，也不能是函数的参数。我们在写SQL时应尽量简化，如下是不能走actor_id列的索引的。
select actor_id from sakila.actor where actor_id+1=5;
select ... where TO_DAYS(CURRENT_DATE) - TO_DAYS(date_col) <= 10;
5.3.2 前缀索引和索引选择性
索引很长的字符列，这会让索引变慢。一个策略是前面提到的哈希索引。还有一种可以通过索引字符开头的一部分，这样可以提高索引的效率，但有可能会降低索引的选择性。
索引选择性=不重复的索引值/记录总数，选择性越高可以让MySQL在查找时过滤掉更多的行，最大为1则说明值唯一，没有重复的值，此时性能最好。
另一方面前缀索引也有缺点:无法用作ORDER BY和GROUP BY，也无法做覆盖扫描。
5.3.4 选择合适的索引列顺序
正确的索引列顺序依赖于使用索引的查询，同时需要考虑排序和分组的需要。
5.3.5 聚簇索引
聚簇索引是一种数据存储方式。InnoDB的聚簇索引是在B-Tree索引另外保存了数据行，它将数据行存放在叶子页当中。如图，叶子页存放了数据，节点页只存放索引列，该图中索引列是正整数int值:
聚簇索引的数据分布.png
MySQL中，InnoDB默认将主键聚集数据建立索引，如果没有定义主键，InnoDB会选择一个唯一的非空索引代替，若还没有则InnoDB隐式地自己定义一个主键来作为聚簇索引。
聚簇数据一些优点:
- 可以把相关数据保存在一起，因此在有些时候查询某个主键相关的数据时可以直接从数据页中获取，避免了再次磁盘I/O。
- 聚簇索引将索引和数据保存在同一个B-Tree中， 如果索引包含所有满足查询需要的数据的索引成为覆盖索引(Covering Index)，也就是平时所说的不需要回表操作。使用explain时输出
的extra列显示为using index。此时查询数据更快。
InnoDB和MyISAM的数据分布对比:
MyISAM的数据分布非常简单,按照数据的插入顺序存储在磁盘上.插入顺序即行号从0开始自增，对于MyISAM来说主键索引额非主键索引的数据分布是一样的，根节点存放索引值，叶子节点根据索引值排序，然后存放指针指向行地址:
非聚簇索引.png
因为InnoDB支持聚簇索引，存储方式有些不一样，InnoDB中索引就是表，数据行直接存放在叶子节点对应索引处。聚簇索引的每一个叶子节点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及数据行。即使主键是一个列前缀索引，InnoDb也会包含完整的主键列和剩下的其他列。不同的是，聚簇索引的非主键索引(二级索引)的叶子节点存放的是主键索引，而不是数据行或者行指针:
主键索引.png
二级索引.png
使用InnoDB时应该尽可能地按住键顺序插入数据，并尽可能地使用单调增加的聚簇键的值来插入新行。不过，对于高并发场景下，在InnoDB中按住键顺序插入可能会造成明显锁竞争。
5.3.6 覆盖索引
MySQL可以使用索引来直接获取列的数据，不用读取数据行。如果一个索引的叶子节点包含(或者说覆盖)所有需要查询的字段的值，我们就不需要再回表查询，称为覆盖索引。由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，如果二级索引的列能覆盖查询的要求，则可以避免再去主键索引的二次查询。MySQL中只能使用B-Tree索引做覆盖索引。当发起一个覆盖索引时，在EXPLAIN的Extra列中会显示"Using index"的信息,如之前的people表:
mysql> explain select last_name,first_name from people;
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
| 1 | SIMPLE | people | index | NULL | key | 307 | NULL | 6 | Using index |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)
MySQL中不能对以通配符开头的like操作执行索引。
5.3.7 使用索引扫描来做排序
MySQL两种方式可以生成有序的结果:通过排序操作；或者索引顺序扫描；如果EXPLAIN中的type列值为"index"，则说明使用了索引扫描做排序。索引扫描本身很快，但如果索引的列不能覆盖查询的列，那每扫描一条索引记录都要回表查询一次对应的行，这都是随机I/O，此时按索引顺序排序比直接全表的顺序排序操作还要慢。
因此，设计索引时尽可能地既满足排序又能覆盖要查询的行。并且注意，ORDER BY子句也需要满足最左前缀要求，才能使用索引扫描排序；如果是多表关联查询，则只有当ORDER BY字段全是第一个表，才有可能使用索引排序。与查找型查询不同的是一种特殊情况，如果组合索引的第一列匹配为常量，也会走扫描索引,如下last_name="Yale"固定值时也走了索引:
mysql> explain select last_name,first_name,dob from people where last_name = "Yale" order by first_name;
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
| 1 | SIMPLE | people | ref | key | key | 152 | const | 1 | Using where; Using index |
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)
mysql> explain select last_name,first_name,dob from people order by first_name;
+----+-------------+--------+-------+---------------+------+---------+------+------+-----------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+--------+-------+---------------+------+---------+------+------+-----------------------------+
| 1 | SIMPLE | people | index | NULL | key | 307 | NULL | 6 | Using index; Using filesort |
+----+-------------+--------+-------+---------------+------+---------+------+------+-----------------------------+
5.3.11 索引和锁
索引可以让查询锁定更少的行。InnoDB只有咋访问行的时候才会对其加锁，而索引能减少InnoDB访问的行数，从而减少锁的数量。如下，actor只有一个主键索引id列，其中第一个语句因为MySQl为该查询选择的执行计划是索引范围扫描，Extra列出现了Using where，这表示MySQl服务器将存储引擎返回的行再进行Where过滤，所以额外锁定了actor_id=1的行，因为第二个语句查询的时候被挂起直到第一个语句释放commit:
mysql> set autocommit=0;
Query OK, 0 rows affected (0.00 sec)
mysql> begin;
Query OK, 0 rows affected (0.00 sec)
mysql> select actor_id from actor where actor_id <5 and actor_id <>1 for update;
+----------+
| actor_id |
+----------+
| 2 |
| 3 |
| 4 |
+----------+
3 rows in set (0.00 sec)
mysql> explain select actor_id from actor where actor_id <5 and actor_id <>1 for update;
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
| id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra |
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
| 1 | SIMPLE | actor | range | PRIMARY | PRIMARY | 2 | NULL | 3 | Using where; Using index |
+----+-------------+-------+-------+---------------+---------+---------+------+------+--------------------------+
1 row in set (0.00 sec)
mysql> commit;
Query OK, 0 rows affected (0.00 sec)
#另外开启一个新事物
mysql> begin;
Query OK, 0 rows affected (0.00 sec)
mysql> select actor_id from actor where actor_id =1 for update;
+----------+
| actor_id |
+----------+
| 1 |
+----------+
1 row in set (12.82 sec) #第一个连接commit释放锁之后才能执行查询
因此，即使使用了索引，InnoDb也可能会锁住一些不需要的数据行。
5.6 总结
在MySQL中大多数情况下会使用B-Tree索引。编写查询语句时应该尽可能选择合适的索引以避免单行查找，尽可能使用数据原生顺序，尽可能使用索引覆盖查询。
