索引选择性

对索引列和字符串前缀长度，都参考选择性（Selectivity）这个指标来确定：选择性定义为不重复的索引值和数据总记录条数的比值，其选择性越高，那么索引的查询效率也越高，譬如对于性别这种参数，建立索引根本没有意义。

Index Selectivity = Cardinality / #T

显然选择性的取值范围为 (0, 1]，选择性越高的索引价值越大，这是由 B+Tree 的性质决定的。在实际的数据库中，我们可以通过以下语句来计算某列的选择性：

SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM titles;

区分度：count(distinct col)/count(*)。 区分度是一个介于 0 和 1 之间的小数，越接近 1 区分度越高，越适合做索引。 原因很容易理解，比如一个辞典中全是以 a 和 b 开头的单词，那么按照首字母简历一个目录(索引)，那么目录上一共就两条，每条的范围对应差不多半本辞典，那这个目录(索引)毫无用处。相反，一个班级的学生信息以学号做索引，那么区分度为 1，只要找到学号就能直接找到相对应的学生信息，这个索引就非常有效。

覆盖索引

覆盖索引指的是对于查询中使用的除去参与索引过滤扫描的所有字段将其加入到该查询所使用的索引尾部的索引。覆盖索引扫描的优点在于由于查询中所使用的所有字段都在同一索引的字段，因而在进行查询时只需要在索引中获取相关数据即可，而不需要回磁盘扫描相应的数据，从而避免了查询中最耗时的磁盘 IO 读取。对于如下查询：

select a, b, c from t where a='a' and b='b';

该查询中如果建立联合索引(a, b, c)，那么这就是使用了覆盖扫描的索引，因为对于该查询，可以使用索引的前两个字段 a 和 b 根据 where 条件进行索引片的过滤，对过滤后的索引片直接在索引中读取 a, b, c 三个字段的值即可，而无需回表扫描。以下表为例：

mysql> create table T (
ID int primary key,
k int NOT NULL DEFAULT 0,
s varchar(16) NOT NULL DEFAULT '',
index k(k))
engine=InnoDB;

insert into T values(100,1, 'aa'),(200,2,'bb'),(300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

如果直接执行 select * from T where k between 3 and 5，那么会经历以下步骤：

• 在 k 索引树上找到 k=3 的记录，取得 ID = 300；
• 再到 ID 索引树查到 ID=300 对应的 R3；
• 在 k 索引树取下一个值 k=5，取得 ID=500；
• 再回到 ID 索引树查到 ID=500 对应的 R4；
• 在 k 索引树取下一个值 k=6，不满足条件，循环结束。
• 在这个过程中，回到主键索引树搜索的过程，我们称为回表。可以看到，这个查询过程读了 k 索引树的 3 条记录，回表了两次。在这个例子中，由于查询结果所需要的数据只在主键索引上有，所以不得不回表。

SQL 语句修改为select ID from T where k between 3 and 5，这时只需要查 ID 的值，而 ID 的值已经在 k 索引树上了，因此可以直接提供查询结果，不需要回表。也就是说，在这个查询里面，索引 k 已经“覆盖了”我们的查询需求，我们称为覆盖索引。

三星索引

三星索引指的是对于一个查询，设立了三个通用的索引条件满足的条件，建立的索引对于特定的查询每满足一个条件就表示该索引得到一颗星，当该索引得到三颗星时就表示该索引对于该查询是一个三星索引。三星索引是对于特定查询的最优索引，建立三星索引的条件如下：

• 取出所有的等值谓词的列 （WHERE COL=…） 作为索引开头的列；
• 将 ORDER BY 中的列加入到索引中；
• 将查询语句中剩余的列加入到索引中，将易变得列放到最后以降低更新成本。

譬如对于如下的查询，索引 (first_name, last_name, email) 就是一个三星索引：

SELECT first_name, last_name, email FROM user WHERE first_name = 'aa' ORDER BY last_name;

三星索引的创建过程可以发现如下规律：

• 覆盖等值谓词条件，如 first_name，可以过滤大部分的索引片数据；
• 覆盖 order by 字段可以避免对结果集的排序，如 last_name;
• 覆盖其余字段可以避免回磁盘读取数据，即使用了覆盖索引扫描，如 email。