B-Tree索引

适用于全键型、键值范围、键前缀查找

全值匹配

匹配最左前缀

匹配列前缀

匹配范围值

精确匹配某一列并范围匹配另外一列

只访问索引的查询

限制

不是按照索引的最左列开始查找，无法使用索引

不能跳过索引中的列（只能使用一部分）

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

哈希索引

基于哈希表实现，只有精确匹配索引所有列的查询才有效。

哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

限制：

哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行；

数据不是按照索引顺序存储的，所以无法用于排序；

不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容计算哈希值的；

只支持等值比较查询；不支持任何范围查找；

当存在很多哈希冲突时，存储引擎必须遍历链表中所有行指针，逐行进行比较，直到找到所有服务条件的行。（不同的索引列可能存在相同的哈希值）

索引的优点

1.大大减少了服务器需要扫描的数据量

2.帮助服务器避免排序和临时表

3.可以将随机I/O变为顺序I/O

高性能索引策略

1.独立的列

指索引列不能是表达式的一部分，也不能是函数的参数。

不是独立的列不能使用索引

2.前缀索引和索引选择性

选取索引开始的部分字符，可以节省索引空间，从而提升索引效率，单会降低索引选择性。

索引选择性=不重复的索引值/数据表的记录总数    （当为1时最高，例唯一索引）

BLOB、TEXT或比较长的VARCHAR类型的列，必须使用前缀索引（mysql不支持太长的索引）

选择的标准

前缀的基数应该接近于完整列的基数

例：

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

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

前缀的选择性尽量接近完整列的选择性

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

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

from city_demo;o

前缀索引的缺点

无法在order by 和group by 中使用

无法用于覆盖扫描

常见应用场景

很长的十六进制唯一ID

3.选择合适的索引顺序

经验法则：将选择性最高的列放在索引最前列。

4.聚簇索引

并不是一种单独的索引类型，而是一种数据存储方式。

InnerDB的聚簇索引实际是在同一结构中保存了B-Tree索引和数据行。

一个表只能有一个聚簇索引，因为无法同时将数据行存储在两个不同的地方。

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

优点：

可以把相关数据保存在一起，可减少查询时的磁盘I/O

数据访问更快

使用覆盖索引扫描的查询可以直接使用页节点中的主键值

缺点：

插入速度严重依赖于插入顺序

更新聚簇索引列的代价很高，因为会强制InnerDB将每个被更新的行移动到新的位置

基于聚簇索引插入新行可能导致页分裂问题，从而导致表占用更多的磁盘空间

可能会导致全表扫描变慢（行比较稀疏，或页分裂导致数据存储不连续的情况）

二级索引（非聚簇索引）可能比想象中的更大，因为二级索引的叶子节点中包含了引用行的主键列

二级索引访问需要两次索引查找，而不是一次。

最好避免随机的聚簇索引，特别是对于I/O密集型的应用。如果用UUID主键插入行不仅花费时间更长，索引占用的空间也更大。

顺序的主键什么时候会造成更坏的结果？

高并发时，InnoDB按主键顺序插入会造曾明显的争用。主键的上界会成为热点。冰法插入可能导致间隙锁竞争。另一个热点是AUTO_INCREMENT锁机制。

5.覆盖索引

定义：覆盖所有需要查询的字段的值的索引

优势：

1.索引条目通常远小于数据行大小，所以如果只需要读取索引，MySQL就会极大地减少数据访问量。

2.索引如果按顺序存储时，对于I/O密集型的范围查询会比随机从磁盘读取每一行数据的I/O少很多

3.InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询

覆盖索引不需要存储索引列的值

6.使用索引扫描来做排序

两种方式可以生成有序的结果：通过排序操作；按索引顺序扫描。

扫描索引本身很快，但如果索引不恩能够覆盖查询所需的全部列，会出现回表查询，属于随机I/O，这种情况通常比顺序的全表扫描慢，尤其是在I/O密集型的工作负载时。

只有索引列的顺序与order by 子句的顺序完全一致，并且所有列的排序方向都一样时，才能使用索引进行排序。

如果多表联合查询，只有order by子句引用的字段都是第一张表时，才能使用索引做排序。

7.压缩（前缀压缩）索引

主要针对MyISAM引擎

索引块中第一个值”perform“，第二个值”performance“，那么第二个值的前缀压缩后存储的是类似”7，ance"这样的形式。MyISAM对行指针也采用类似的前缀压缩方式。

对于CPU密集型应用，扫描需要随机查找，压缩索引会导致查询慢上几倍。但因为压缩索引一般只需要十分之一的磁盘空间，所以如果是I/O密集型应用，对某些查询带来的好处会比成本多很多。

8.冗余和重复索引

重复索引：在相同的列上按照相同的顺序创建的相同类型的索引。

冗余索引，如果创建了索引（A,B)，在创建索引（A）就是冗余索引。但是创建（B,A），（B）都不属于冗余索引。

其他不同类型的索引（如哈希，全文）也不会是B-Tree索引的冗余索引。

如果ID索引是主键，则索引（A，ID）也是冗余索引。因为InnoDB的主键列包含在二级索引中了

9.未使用的索引

利用Percona Server 或 MariaDB中先打开userstates服务器变量，然后让服务器运行一段时间，再通过查询INFORMATION_SCHEMA.INDEX_STATISTICS就可以查到每个索引的使用频率。

还可以使用Percona Toolkit中的pt-indax-usage，该工具可以读取查询日志，并且对日志的每条查询进行explain操作，然后打印出关于索引和查询的报告。

10.索引和锁

索引可以让查询呢锁定更少的行。

锁定超过需要的行会增加锁争用并减少并发性。

InnoDB只有在访问行的时候才会对其加锁，而索引能减少InnoDB访问行数，从而减少锁的数量。但只有当InnoDB在存储引擎层能够过滤掉所有不需要的行时才有效。如果索引无法过滤掉无效的行，那么在InnoDB检索到数据并返回给服务器层以后，MySql服务器才能应用where子句。这时已经无法避免行锁定了，已经锁住的行要到适当的时候才能释放。MYSQL5.1以后的版本，InnoDB可以在服务器端过滤掉行后就释放锁。但之前的版本只有到事务提交之后才能释放锁。

InnoDB在二级索引上使用共享（读）锁，但访问主键索引需要排他（写）锁。这消除了使用覆盖索引的可能性，并且使得select for update 比 lock in share mode或非锁定查询要慢很多。

索引案例学习

1.支持多种过滤条件

联合索引把范围查找的放在最后面

2.避免多个范围查找

最好是将范围查询转化成等值比较

3.优化排序

文件排序对小数据集是很快的

偏移量增大后，查询速度会明显变慢。可以通过反范式化、预先计算、缓存解决。还可以通过限制用户翻页数量限制。还可以通过延迟关联进行优化。（先使用覆盖索引查出主键，再通过主键查出需要的行）

如何判断索引是否合理？

判断响应时间

找出消耗最长时间或给服务器带来最大压力的查询，检查schema、sql、索引结构，判断是否有查询扫描了太多行，是否做了很多额外的排序或者使用了临时表，是否使用了随机I/O访问数据，或者是有太多回表查询哪些不再索引中的列的操作。

选择索引和编写利用索引查询的三个原则：

1.单行访问很慢；

2.按顺序访问范围数据很快；

3.索引覆盖查询很快。

mysql中大多数情况会使用B-Tree索引。其他类型索引大多只适用于特殊的目的。