后端工程师在开发过程中经常需要和数据库打交道，而如何建立高效的索引应该是数据库技能点的关键了。本篇介绍了索引的原理和索引优化的策略，能够帮助大家在建数据表索引的时候不再迷茫。

1 - 索引

索引（在MySQL中也叫做“键(key)”）是存储引擎用于快速找到记录的一种数据结构。索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。在数据量较小且负载较低时，不恰当的索引对性能的影响可能还不明显，但当数据量逐渐增大时，性能则会急剧下降。

索引优化应该是对查询性能优化最有效的手段了。索引能够轻易地将查询性能提高几个数量级，“最优”的索引有时比一个“好的”索引性能要好两个数量级。

2 - B-Tree 索引

2.1 基本介绍

索引有很多种类型，对于MySQL来说，使用不同的存储引擎就意味着使用了不同类型的索引，因为MySQl中的索引是在存储引擎层而不是服务器层实现的。大多数 MySQL 引擎都支持 B-Tree 索引，如果没有指明索引类型，一般默认即为 B-Tree 类型。也正是因为其应用范围最广，本文就将B-Tree 索引作为例子，介绍索引的优化。
　
　B-Tree 的特点是所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。下图展示了 B-Tree 索引的抽象表示，反映了 InnoDB 索引是如何工作的。

建立在B-Tree结构上的索引（技术上来说B+Tree）

根节点存放了指向子节点的指针，存储引擎根据这些指针向下层节点页查找。如图所示，通过key值的比较进行选择路径，经过一层一层的节点页，最终找到最底下的叶子页，叶子页存放着指向数据的指针。需要特别指出的是，改图所用的结构其实是B-Tree的变种B+Tree，关于B-Tree和B+Tree的区别，大家可以参考从B树、B+树、B*树谈到R 树这篇博客。
　
　B-Tree 索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索。由于B-Tree 对索引列是顺序组织存储的，所以很适合查找范围数据。

2.2 查询特点

CREATE TABLE People (
    last_name   varchar(50) not null,
    first_name  varchar(50) not null,
    birth       datetime    not null,
    key(last_name, first_name, birthday)
);

上面一段SQL主要是建立了一张名为People的表，将last_name, first_name, birthday作为一个联合索引，下图显示了该索引是如何组织数据的存储的。

People表中索引树条目

B-Tree 索引适用于全键值、键值范围或键前缀查找。让我们用下面一段例子来解释：

// 1 - 全键值
SELECT * FROM People WHERE last_name = Allen 
AND first_name = Cuba AND birth = '1990-01-01';

// 2- 匹配最左前缀
SELECT * FROM People WHERE last_name = Allen;

// 3 - 匹配列前缀
SELECT * FROM People WHERE last_name LIKE 'A%';

// 4 - 未使用索引
SELECT * FROM People WHERE first_name = Cuba;

// 5 - 使用了部分索引
SELECT * FROM People WHERE last_name = Allen
AND birth = '1990-01-01';

// 6 - 使用了部分索引
SELECT * FROM People WHERE last_name = Allen 
AND first_name LIKE 'C%' AND birth = '1990-01-01';

2.3 B-Tree 索引的限制

• 如果不是按照索引的最左列开始查找，则无法使用索引。式（4）没有从last_name开始查找，所以该条SQL会从全局遍历查找first_name = Cuba的项，这就比从索引查找慢了许多。

• 不能跳过索引中的列。如式（5），中间跳过了first_name项的匹配，所以这段SQL先是通过last_name这条索引将数据全部筛选出，然后遍历取出birth条件项。

• 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。如式（6），这个查询只能使用last_name和first_name列的索引，因为这里LIKE是一个范围条件，查询出前两列的结果后，再遍历筛选出birth条件项。

3 - 高性能索引的策略

如何评价一个索引
索引将相关的记录放到一起则获得一星；如果索引中的数据顺序和查找中的排列顺序一致则获得二星；如果索引中的列包含了查询需要的全部列则获得“三星”

3.1 独立的列

“独立的列”是指索引列不能是表达式的一部分，也不能是函数的参数。下面是一些使用不当的案例。

// MySQL无法解析，不会使用索引
SELECT * FROM student WHERE id + 1 = 5;
// 同上
SELECT * FROM student WHERE updateTime - createTime <=  10;

3.2 前缀索引和索引选择性

有时候需要索引很长的字符列，这会让索引变得大且慢。通常可以索引开始的那部分字符，这样可以大大节约索引空间，从而提高索引效率。但这样也会降低索引的选择性。
　
　索引的的选择性是指，不重复的索引值（基数）和数据表的记录总数（#T）的比值，范围从 1/#T 到 1 之间，索引的选择性越高则查询效率越高，因为选择性高的索引可以让MySQL在查找时过滤掉更多的行。唯一索引的选择性是1，这是最好的索引选择性，性能也是最好的。

诀窍在于要选择足够长的前缀以保证较高的选择性，同时又不能太长（以便节约空间）。前缀应该足够长，以使得前缀索引的选择性接近于索引整个列。

// 创建前缀索引实例
ALTER TABLE tbl_city ADD KEY (cityName(7));

3.3 多列索引

在多个列上分别建立独立的单列索引在大多情况下并不能提高MySQL的查询性能。MySQL5.0*之后引入了一种叫“索引合并”(index merge)的策略，一定程度上可以使用表上的多个单列索引来定位指定的行。

例如表film_actor在字段film_id和actor_id上各有一个单列索引，当执行下面一条SQL：

SELECT film_id, actor_id FROM film_actor WHERE actor_id = 1 OR film_id = 1;

老的MySQL版本中，会对这个查询使用全表扫描，除非改写成如下的两个查询 UNION 的方式：

SELECT film_id, actor_id FROM film_actor WHERE actor_id = 1 
UNION ALL 
SELECT film_id, actor_id FROM film_actor WHERE  film_id = 1 OR actor_id <> 1;

MySQL5.0 后的版本中，在查询能够同时使用这两个单列索引进行扫描，并将结果进行合并。这种算法有三个变种：OR条件的联合（union），AND条件的相交（intersection），组合前两种情况的联合及相交。

不过值得注意的是，索引合并策略有时候是一种优化的结果，但实际上更多时候说明了表上的索引建的很糟糕。

• 当出现服务器对多个索引做相交操作（通常有多个AND条件），通常意味着需要一个包含所有相关列的多列索引，而不是多个独立的单列索引。

• 当服务器需要对多个索引做联合操作是（通常有多个OR条件），通常需要耗费大量的CPU和内存资源在算法的缓存、排序和合并操作上。特别是当其中有些索引的选择性不高，需要合并扫描返回大量的数据的时候。

• 更重要的是，优化器不会把这些计算到“查询成本”中，优化器只关心随机页面读取。这会使得查询的成本被“低估”，导致该执行计划还不如直接走全表扫描。

3.4 选择合适的索引列顺序

在一个多列B-Tree 索引中，索引列的顺序意味着索引首先按照最左列进行排序，其次是第二列，等等。所以，索引可以按照升序或者降序进行扫描，以满足精确符合顺序的ORDER BY、GROUP BY和DISTINCT等子句的查询需求。

在不考虑排序和分组的情况下，将选择性最高的列放在前面通常是很好的。这时候索引的作用只是用于优化 WHERE 条件的查找。然而，性能不只是依赖于所有索引列的选择性，也和查询条件的具体值有关，也就是和值得分布有关。

3.5 聚簇索引

当表有聚簇索引时，它的数据行实际上存放在索引的叶子页。术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。

3.6 覆盖索引

如果一个索引包含所有需要查询的字段的值，我们就称之为“覆盖索引”。覆盖索引是非常有用的工具，能够极大地提高性能，其好处有：

• 索引条目通常远小于数据行大小，所以如果只需要读取索引，那MySQL就会极大地减少数据访问量。
• 因为索引是按照列值顺序存储的，所以对于I/O密集型的范围查询会比随机从磁盘读取每一行数据的I/O要少得少。
• 对于MyISAM存储引擎，内存中只缓存索引，数据则依赖于操作系统来缓存，因为要访问数据需要一次系统调用
• 对于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询。

3.7 使用索引扫描来做排序

MySQL 有两种方式可以生成有序的结果：排序操作和按索引顺序扫描。如果EXPLAIN出来的type列的值为“index”，则说明MySQL 使用了索引扫描来做排序。MySQL 可以使用同一个索引既满足排序，又用于查找行。因此，如果可能，设计索引时应该尽可能地同时满足这两种任务，这样是最好的。

3.8 冗余和重复索引

MySQL 允许在相同列上创建多个索引，无论是有意的还是无意的。MySQL 需要单独维护重复的索引，并且优化器在优化查询的时候也需要逐个地进行考虑，这会影响性能。

大家好，我是彬彬酱，目前在腾讯从事Web后端开发。
菜鸟必知的 MySQL 知识专题整理了关于 MySQL 的基础知识，适合大家进行入门级学习，这个专题现包含下列文章：
菜鸟必知的 MySQL 知识（一）—— 基础知识
菜鸟必知的 MySQL 知识（二）—— 数据类型优化
菜鸟必知的 MySQL 知识（三）—— 索引优化