索引

索引是在存储引擎层实现的，而不是在服务器层实现的，所以不同存储引擎具有不同的索引类型和实现。

索引能够轻易将查询性能提升几个数量级。

对于非常小的表、大部分情况下简单的全表扫描比建立索引更高效。对于中到大型的表，索引就非常有效。但是对于特大型的表，建立和使用索引的代价将会随之增长。这种情况下，需要用到一种技术可以直接区分出需要查询的一组数据，而不是一条记录一条记录地匹配，例如可以使用分区技术。

索引分类

B+Tree 索引

B+Tree 索引是大多数 MySQL 存储引擎的默认索引类型。

因为不再需要进行全表扫描，只需要对树进行搜索即可，因此查找速度快很多。

可以指定多个列作为索引列，多个索引列共同组成键。B+Tree 索引适用于全键值、键值范围和键前缀查找，其中键前缀查找只适用于最左前缀查找。

除了用于查找，还可以用于排序和分组。

如果不是按照索引列的顺序进行查找，则无法使用索引。

为了增加索引的利用率。理想状态是查询条件中每一列都能利用索引。比如前列中是三个列的复合索引。按最左前缀原则，性能最好的查询是：

select last_name, first_name, dob from people where last_name = ‘Cuba’ and first_name = ‘allen’ and dob = ‘1960-01-01’; 

要注意条件中列的顺序，要和索引中的一致才行。因为索引的存储是按这样的列顺序排好的。如果不按顺序，引擎就会去执行全表查询。

如果查询中有某列是范围查询，则其右边所有列都无法使用索引优化查找了。如：

where last_name = ‘smith’ and first_name likt ‘J%’ and dob=’1960-01-01’; 

该查询中只会在前两个条件上使用索引。因为 like 是范围查询，按规则，后面的 dob 无法使用索引。

哈希索引

Hash 索引比较的是进行 Hash 运算之后的 Hash 值，索引的检索可以一次定位，不像B-Tree 索引需要从根节点到枝节点。

所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。

在 MySQL 中只有 Memory 引擎显式支持哈希索引。

InnoDB 引擎有一个特殊的功能叫“自适应哈希索引”，当某个索引值被使用的非常频繁时，会在 B+Tree 索引之上再创建一个哈希索引，这样就让 B+Tree 索引具有哈希索引的一些优点，比如快速的哈希查找。

限制：

哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能影响并不明显；
无法用于排序与分组；
只支持精确查找，无法用于部分查找和范围查找；
如果哈希冲突很多，查找速度会变得很慢。

空间数据索引（R-Tree）

MyISAM 存储引擎支持空间数据索引，可以用于地理数据存储。

空间数据索引会从所有维度来索引数据，可以有效地使用任意维度来进行组合查询。

必须使用 GIS 相关的函数来维护数据。

全文索引

MyISAM 存储引擎支持全文索引，用于查找文本中的关键词，而不是直接比较索引中的值。

查找条件使用 MATCH AGAINST，而不是普通的 WHERE。

索引的优点

大大减少了服务器需要扫描的数据量；
帮助服务器避免进行排序和创建临时表（B+Tree 索引是有序的，可以用来做 ORDER BY 和 GROUP BY 操作）；
将随机 I/O 变为顺序 I/O（B+Tree 索引是有序的，也就将相邻的数据都存储在一起）。

索引优化

独立的列

在进行查询时，索引列不能是表达式的一部分，也不能是函数的参数，否则无法使用索引。

例如下面的查询不能使用 actor_id 列的索引：

SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5;

前缀索引

如果有很长的字符,如 blog, text, 如果索引这个列,索引会很大,而且 MySQL 也不支持对这种列进行索引.所以需要前缀索引,对这些索引的前面几个字符进行索引

为了让这种索引效率最高,也就是查询出来的结果最真实,先要确定需要索引前面几个字符.示例:

select count(*) as cnt, city from my_table group by city order by cnt desc limit 10;

该语句查询访问量排前十的城市及它的访问量.假定 city 字段是很长的字符串.

然后再用语句:

select count(*) as cnt, left(city, 3) as pref from my_table group by city order by cnt desc limit 10;

group by 的内容变成了 left(city, 3) 当然,该语句查询了的结果可能和前面不一样. left 的第二个参数越长,肯定越准确.多试几次,索引选择性最高的数值.

索引选择性

索引的选择性是指不重复的索引列数和数据表的记录总数的比值

索引的选择性越高则查询效率越高.因为它可以让 MySQL 在查找时过滤掉更多的行,唯一索引的选择性是 1, 这是最好的索引选择性,性能也是最好的.

计算方式可能是:

select count(distinct city) / count(*) from my_table;

面找出最高选择性的办法:

select count(distinct left(city, 3)) / count(*) as sel3, 
	count(distinct left(city, 4)) / count(*) as sel4 ,
	count(distinct left(city, 5)) / count(*) as sel5 ,
	count(distinct left(city, 6)) / count(*) as sel6 ,
	count(distinct left(city, 7)) / count(*) as sel7 ,
	from my_table

结果:

sel3	sel4	sel5	sel6	sel7
0.0239	0.0293	0.0305	0.0309	0.0310

看出,从 sel7 开始,上升的幅度已经很少了,如果再往后增成 8, 9 一样.所以,选择 7 即可.有些时候为了效率考虑,可以选择更低的 5, 6

我们就可以创建前缀索引:

alter table my_table add key(left(city,7));

前缀索引的缺点是, MySQL 无法使用前缀索引做 order by, group by

多列索引

前面知道,hash 索引是通过列的 hash 值来存的,所以无顺序之言.而 b-tree 是按顺序来存储的.所以最左前缀原则只适用于b-tree 索引

对多列创建复合索引.为了利用索引,SQL语句的写法要注意.

数据存储的方式是按索引列最左进行排,然后再第二..三..在 order by, group by, distinct 等语句都能使用到索引.

将选择性最高的列放在索引最前列.

有时候索引顺序还是得根据实际业务需求来,需要根据查询的频率进行调整.如:

select * from payment where starff_id = 2 and user_id = 584;

按最左原则,要创建一个 (starff_id, user_id) 的索引.我们可以先跑一些查询来确定这个表中值的分布情况并确定哪个列的选择性更高:

select sum(starff_id=2), sum(user_id=584) from payment\G

结果:

sum(starff_id=2): 7992
sum(user_id=2): 30

可见,对于 user_id 这个条件,符合的值更少,所以要将 user_id 放在前面.因为这样能更快的过虑掉更多的结果,更快的找到需要的结果.

可以再计算一下两者的索引选择性, 这样更客观:

select count(distince starff_id)/count(*) as st_sel, count(distince user_id)/count(*) as us_sel, count(*) from payment\G

结果:

st_sel: 0.0001
us_sel: 0.0373
count(*): 16049

看到这个结果,我们可以坚定的将 user_id 放在最前面了

聚簇索引

聚簇索引并不是一种索引类型，而是一种数据存储方式。

术语“聚簇”表示数据行和相邻的键值紧密地存储在一起，InnoDB 的聚簇索引在同一个结构中保存了 B+Tree 索引和数据行。

因为无法把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。

图中，索引列是一个整数列。到目前为止，没有哪个存储引擎完全实现了聚簇索引，只有 InnoDB 实现了通过主键进行聚集，也就是说上图中被索引的列是主键。

如果一个表没有定义主键，InnoDB 会选择一个唯一的非空索引代替。如果没有这样的列，InnoDB 会隐式定义一个主键来作为聚簇索引。

优点

可以把相关数据保存在一起，减少 I/O 操作。例如电子邮件表可以根据用户 ID 来聚集数据，这样只需要从磁盘读取少数的数据也就能获取某个用户的全部邮件，如果没有使用聚聚簇索引，则每封邮件都可能导致一次磁盘 I/O。
数据访问更快。索引和数据都在同一个B-Tree 中。不用再通过指针去查找一次。

缺点

聚簇索引最大限度提高了 I/O 密集型应用的性能，但是如果数据全部放在内存，就没必要用聚簇索引。
插入速度严重依赖于插入顺序，按主键的顺序插入是最快的。
更新操作代价很高，因为每个被更新的行都会移动到新的位置。
当插入到某个已满的页中，存储引擎会将该页分裂成两个页面来容纳该行，页分裂会导致表占用更多的磁盘空间。
如果行比较稀疏，或者由于页分裂导致数据存储不连续时，聚簇索引可能导致全表扫描速度变慢。

覆盖索引

索引包含所有需要查询的字段的值。

优点

因为索引条目通常远小于数据行的大小，所以若只读取索引，能大大减少数据访问量。
一些存储引擎（例如 MyISAM）在内存中只缓存索引，而数据依赖于操作系统来缓存。因此，只访问索引可以不使用系统调用（通常比较费时）。
对于 InnoDB 引擎，若二级索引能够覆盖查询，则无需访问聚簇索引。

B-Tree 和 B+Tree 原理

B-Tree

定义一条数据记录为一个二元组 [key, data]，B-Tree 是满足下列条件的数据结构：

所有叶节点具有相同的深度，也就是说 B-Tree 是平衡的；
一个节点中的 key 从左到右非递减排列；
如果某个指针的左右相邻 key 分别是 key_i 和 key_i+1，且不为 null，则该指针指向节点的所有 key 大于等于 key_i 且小于等于 key_i+1。

在 B-Tree 中按 key 检索数据的算法非常直观：首先在根节点进行二分查找，如果找到则返回对应节点的 data，否则在相应区间的指针指向的节点递归进行查找。

由于插入删除新的数据记录会破坏 B-Tree 的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持 B-Tree 性质。

B+Tree

与 B-Tree 相比，B+Tree 有以下不同点：

每个节点的指针上限为 2d 而不是 2d+1；
内节点不存储 data，只存储 key，叶子节点不存储指针。

带有顺序访问指针的 B+Tree

一般在数据库系统或文件系统中使用的 B+Tree 结构都在经典 B+Tree 基础上进行了优化，在叶子节点增加了顺序访问指针，做这个优化的目的是为了提高区间访问的性能。

为什么使用 B+Tree 和 B-Tree

红黑树等平衡树也可以用来实现索引，但是文件系统及数据库系统普遍采用 B+Tree B-Tree 作为索引结构，主要有以下两个原因：

（一）更少的检索次数

红黑树和 B+Tree B-Tree 检索数据的时间复杂度等于树高 h，而树高大致为 O(h)=O(log_dN)，其中 d 为每个节点的出度。

红黑树的出度为 2，而 B+Tree 与 B-Tree 的出度一般都非常大。红黑树的树高 h 很明显比 B+Tree B-Tree 大非常多，因此检索的次数也就更多。

B+Tree 相比于 B-Tree 更适合外存索引，因为 B+Tree 内节点去掉了 data 域，因此可以拥有更大的出度，检索效率会更高。

（二）利用计算机预读特性

为了减少磁盘 I/O，磁盘往往不是严格按需读取，而是每次都会预读。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。预读过程中，磁盘进行顺序读取，顺序读取不需要进行磁盘寻道，并且只需要很短的旋转时间，因此速度会非常快。

操作系统一般将内存和磁盘分割成固态大小的块，每一块称为一页，内存与磁盘以页为单位交换数据。数据库系统将索引的一个节点的大小设置为页的大小，使得一次 I/O 就能完全载入一个节点，并且可以利用预读特性，临近的节点也能够被预先载入。

MySQL 索引

索引