索引基础
索引的类型
B-Tree索引
当人们谈论索引时，如果没有特别指明类型，那多半说的是B-Tree索引。
存储引擎以不同的方式使用B-Tree索引，性能也各有不同，各有优劣。例如，MyISAM使用前缀压缩技术使得索引更小，但InnoDB则按照数据格式进行存储。再如MyISAM索引通过数据的屋里位置引用被索引的行，而InnoDB则根据主键引用被索引的行。
B-Tree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索。
B-Tree对索引列是顺序组织存储的，所以很适合查找范围数据。
B-Tree索引适用于全键值，键值范围或键前缀查找。
- 全值匹配
全值匹配是指和索引中的所有列进行匹配。 - 匹配最左前缀
可以查找只使用索引的第一列。 - 匹配列前缀
也可以只匹配某一列的值的开头部分。 - 匹配范围值
- 精确匹配某一列并范围匹配另外一列
- 只访问索引的查询
B-Tree通常可以支持“只访问索引的查询”，即查询只需要访问索引，而无需访问数据行。
B-Tree索引的限制：
- 如果不是按照索引的最左列开始查找，则无法使用索引。
- 不能跳过索引中的列。
- 如果查找中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。
哈希索引
哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效。
在mysql中，只有memory引擎显示支持哈希索引，这也是memory引擎的默认索引类型。memory引擎是支持非唯一索引的，如果多个列的哈希值相同，索引会以链表的方式存放多嗯记录指针到同一个哈希条目中。
因为索引只需要存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。
哈希索引的限制：
- 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。
- 哈希索引数据并不是按照索引值顺序存储的，所以无法用于排序。
- 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是列的全部内容来计算哈希值。例如在数据列（A，B）上建立哈希索引，如果查询只有数据列A，则无法使用该索引。
- 哈希索引只支持等值比较，包括
=,in(),<=>（注意<>和<=>是不同的操作），也不支持任何范围查询。 - 访问哈希索引的数据非常快，除非有很多哈希冲突（不同的索引列值却有相同的哈希值）。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
- 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。冲突越大，代价越大。
创建自定义哈希索引。
在B-Tree基础上创建一个伪哈希索引，这和真正的哈希索引不是一回事，因为还是使用B-Tree进行查找，但是它使用哈希值而不是键本身进行索引查找。查询时，在where子句中手动指定使用哈希函数。
例如需要存储大量的URL，并需要根据URL进行搜索查找。如果使用B-Tree来存储URL，存储的内容就会很大，因为URL本身都很长。新增一个被索引的 url_crc列，使用CRC32做哈希，就可以使用下面的方式查询：
select id from url where url="http://www.mysql.com" and url_crc=CRC32("http://www.mysql.com");
这样做的性能会很高，因为mysql优化器会使用这个选择性很高而体积很小的基于 url_crc 列的索引来完成查找。即使有多个记录有相同的索引值，查找仍然很快，只需要根据哈希值做快速的整数比较就能找到索引条目，然后一一比较返回对应的行。
另外一种方式是对完整的url字符串做索引，那样会非常慢。
如果采用这种方式，记住不要使用sha1()和md5()作为哈希函数，因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大量空间，比较时也会更慢。
还可以使用如FNV64()函数作为哈希函数，这时移植自Percona Server的函数，可以以插件的方式在任何mysql版本中使用，哈希值为64位，速度快，冲突比CRC32要少很多。
索引的优点
- 索引大大减少了服务器需要扫描的数据量
- 索引可以帮助服务器避免排序和临时表
- 索引可以将随机I/O变为顺序I/O
高性能的索引策略
独立的列
独立的列是指索引列不能是表达式的一部分，也不能是函数的参数。
下面这个查询无法使用 actor_id 列的索引：
select actor_id from actor where actor_id + 1 = 5;
前缀索引和索引选择性
有时候需要索引很长的字符串，这回让索引变的大且慢，一个策略是前面提到过的模拟哈希索引。但有时候这样做还不够，还可以做些什么呢？
通常可以索引开始的部分字符，这样可以大大节约索引空间，从而提高索引效率。
索引的选择性是指，不重复的索引值和数据表的记录总数的比值，范围从 1/#T 到 1 之间。索引的选择性越高则查询效率越高，因为选择性高的索引可以让msyql在查找时过滤掉更多的行。
唯一索引的选择性是1，这时最好的索引选择性，性能也是最好的。
多列索引
很多人对多列索引理解不够，一个常见的错误是，为每个列创建独立的索引，或者按照错误的顺序创建多列索引。
在多个列上建立独立的单列索引，大部分情况下都不能提高mysql的查询能力。
mysql5.0和更新的版本引入了一种叫做“索引合并”的策略，一定程度上可以使用表上的多个单列索引来定位指定的行。
例如，表 file_actor 在字段 file_id 和 actor_id 各有一个单列的索引，但对于下面的查询where条件，这两个索引都不是最好的选择：
select file_id , actor_id from file_actor
where actor_id=1 or file_id=1;
在老的mysql版本中，mysql会对这个查询使用全表扫描，除非改写为两个查询 union 操作：
select file_id,actor_id from file_actor where actor_id=1
union all
select file__id,actor_id from file_actor where file_id=1;
但在mysql5.0和更新的版本中，查询能够同时使用这两个单列索引进行扫描，并将结果进行合并。
这种算法有三个变种：OR条件的联合（union），AND条件的相交（intersection），组合前两种情况的联合及相交。
下面的查询就是使用了两个索引扫描的联合，通过 EXPLAIN 中的 Extra 列可以看到这点：
explain select file_id, actor_id from file_actor where actor_id=1 or file_id=1;
**************************************** 1 row ****************************
id: 1
select_type: simple
table: film_actor
type: index_merge
possible_keys: primary,idx_fk_film_id
key: primary,idx_fk_film_id
ken_len: 2,2
ref: null
rows: 29
extra: using union(primary,idx_fk_film_id);using where
索引合并策略有时候是一种优化的结果，但实际上更多时候说明了表上的索引建的很糟糕。
- 当出现服务器对多个索引做相交操作时（通常有多个AND条件），通常意味着需要一个包含多个相关列的多列索引，而不是多个独立的单列索引。
- 当服务器需要对多个索引做联合操作时（通常有多个OR条件），通常需要耗费大量CPU和内存资源在内的算法的缓存，排序和合并操作上。特别是当其中有些索引的选择性不高，需要合并扫描返回的大量数据的时候。
- 更重要的是，优化器不会把这些计算到查询成本中，优化器只关心随机页面读取。这会使得查询的成本被低估，导致该执行计划还不如直接走全表扫描。
选择合适的索引顺序
我们遇到的最容易引起困惑的问题就是索引列的顺序。正确的顺序依赖于使用该索引的查询，并且同时需要考虑如何更好的满足排序和分组的需要。
在一个多列B-Tree索引中，索引列的顺序意味着索引首先按照最左列进行排序，其次是第二列，等等。
对于如何选择索引的顺序有一个经验法则：将选择性最高的列放到索引最前列。
当不需要考虑排序和分组时，将选择性最高的列放在前面通常是很好的。
然而，性能不只是依赖于所有索引列的选择性，也和查询条件的具体值有关，也就是和值分布有关。
聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。
InnoDB的聚簇索引实际上在同一个结构中保存了B-Tree索引和数据行。
当表有聚簇索引时，它的数据行实际上存放在索引的叶子页（leaf page）中。聚簇表示数据行和相邻的键值紧凑的存储在一起。
因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。
InnoDB将通过主键聚簇数据，如果没有定义主键，InnoDB会选择一个唯一的非空索引代替。
如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。
聚簇主键可能对性能有帮助，但也可能导致严重的性能问题。所以需要仔细的考虑聚簇索引，尤其是将表的存储引擎从InnoDB改成其他引擎的时候（反过来也一样）。
聚簇索引有一些重要的优点：
- 可以把相关数据保存在一起。例如实现电子邮件时，可以根据用户id来聚集数据，这样只需要从磁盘读取少量的数据页就能获取某个用户的全部邮件。如果没有使用聚簇索引，泽每封邮件可能导致一次磁盘I/O.
- 数据访问更快。聚簇索引将索引和数据保存在同一个B-Tree中，因此从聚簇索引中获取数据通常比非聚簇索引中查找更快。
- 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。
聚簇索引也有一些缺点：
- 聚簇数据最大限度的提高了I/O密集型应用的性能，但如果数据全部放在内存中，则访问的顺序就没那么重要了，聚簇索引也就没什么优势了。
- 插入速度严重依赖插入顺序。按照主键的顺序插入是加载数据才InnoDB表中速度最快的方式。但如果不是按照主键顺序加载数据，那么在加载完成后，最好使用 OPTIMIZE TABLE命令重新组织一下表。
- 更新聚簇索引的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置。
- 基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临“页分裂”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次页分裂操作。页分裂会导致表占用更多的磁盘空间。
- 二级索引（非聚簇索引）可能比想象的要更大，因为在二级索引的叶子节点包含了引用行的主键列。
- 二级索引访问需要两次索引查找，而不是一次。二级索引中保存的“行指针”的实质，不是指向行的物理位置的指针，而是行的主键值。这意味着通过二级索引查找行，存储引擎需要找到二级索引的叶子节点获得对应的主键值，然后再根据这个值去聚簇索引中查找到对应的行。这里做了重复的工作，两次B-Tree查找而不是一次。对于InnoDB，自适应哈希索引能够减少这样的重复工作。
InnoDB和MyISAM的数据分布
来看看InnoDB和MyISAM是如何存储下面的这个表的：
create table layout_test (
col1 int not null,
col2 int not null,
primary key(col1),
key(col2)
);
假设该表的主键取值 1-10000，按照随机顺序插入并使用 optimize table 命令做了优化，也就是说，数据在磁盘上的存储方式已经最优，但行的顺序是随机的。列 col2 的值是从 1-100之间随机赋值，所以有很多 重复的值。
-
MyISAM 的数据分布
myisam
myisam
上面两图展示了主键索引和普通索引的异同。
事实上，myisam中主键索引和其他索引在结构上没有什么不同。
主键索引就是一个名为 primary 的唯一非空索引。 -
InnoDB 数据分布
InnoDB主键索引
聚簇索引的每一个叶子节点都包含了主键值，事务id,用于事务和MVCC的回滚指针以及所有的剩余列。如果主键是一个前列索引，InnoDB也会包含完成的主键列和剩下 的其他列。
InnoDB的二级索引和聚簇索引很不同。InnoDB二级索引的叶子节点中存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”。
这样的策略减少了当出现移动行或者数据页分裂时二级索引的维护工作。
使用主键值当做指针会让二级索引占用更多的空间，但换来的好处是，InnoDB在移动行时，无需更新二级索引中的这个“指针”。
-
MyISAM和InnoDB索引区别
聚簇和非聚簇索引的对比图
在InnoDB表中按主键顺序插入行
避免随机的（不连续且值的分布范围比较大）聚簇索引，特别是对于I/O密集型的应用。
从性能的角度考虑，使用uuid来作为聚簇索引则会很糟糕：它使得聚簇索引的插入变得完全随机，这是最坏的情况，使得数据没有任何聚集特性。
[图片上传失败...(image-2a8107-1532500130839)]
因为主键的值是顺序的，所以InnoDB把每一条记录都存在上一条记录后面。当达到页的最大填充因子时（InnoDB默认的最大填充因子是页大小的15/16，留出部分空间用于以后修改），下一条记录就会写入新的页中。一旦数据按照这种顺序的方式加载，主键页就会近似于被顺序的记录填满，这也是所期望的结果（然而，二级索引可能是不一样的）。
而使用uuid聚簇索引的表插入数据，因为新行的主键值不一定比之前插入的大，所以InnoDB无法简单的总是把新行插入到索引的最后，而是需要为新的行寻找合适的位置--通常是已有数据的中间位置--并且分配空间。这会增加很多额外的工作，并且导致数据分布不够优化。
使用uuid做聚簇索引的缺点：
- 写入的目标页可能已经刷到磁盘上并从缓存中移除，或者是还没有被加载到缓存中，InnoDB在插入之前不得不先找到并从磁盘读取目标页到内存中。这将导致大量的随机I/O。
- 因为写入是乱序的，InnoDB不得不频繁的做页分裂操作，以便为新的行分配空间，页分裂将导致移动大量的数据，一次插入最少需要修改三个页而不是一个页。
- 由于频繁的页分裂，页会变得稀疏并被不规则地填充，所以最终数据会有碎片。
使用InnoDB时应该尽可能的按主键顺序插入数据，并且尽可能的使用单调的聚簇键的值来插入新行。
顺序的主键什么时候会最成更坏的结果？
对于高并发负载，在InnoDB中按主键顺序插入可能会造成明显的争用。主键的上界会成为“热点”。因为所有的插入都发生在这里，所以并发插入可能导致间隙锁竞争。
另一个热点可能是 auto_increment 锁机制，如果遇到这个问题，则可能需要考虑重新设计表或者应用，或者更改 innodb_autoinc_lock_mode 配置。如果你的服务器还不支持 innodb_autoinc_lock_mode 参数，可以升级到新版本的InnoDB，可能对这种场景会工作的更好。
覆盖索引
mysql也可以直接使用索引来获取列的数据，这样就不再需要读取数据行。如果索引的叶子节点中已经包含要查找的数据，那么还有什么必要再回表查询呢？
如果一个索引包含或者说覆盖所有需要查询的字段的值，我们就称为“覆盖索引”。
覆盖索引的好处：
- 索引条目通常远小于数据行大小，所以如果只需要读取索引，那mysql就会极大的减少数据访问量。这对缓存的负载非常重要，因为这种情况下响应时间大部分花费在数据拷贝上。覆盖索引对于I/O密集型的应用也有帮助，因为索引比数据更小，更容易全部放到内存里，这对于myisam尤其正确，因为myisam能压缩索引以变的更小。
- 因为索引是按照列值顺序存储的（至少在单个页是如此），所以对于I/O密集型的范围查询会比随机从磁盘读取每一行数据的I/O要少得多。对于某些存储引擎，例如myisam和percona xtradb，甚至可以通过 optimize 命令使得索引完全顺序排列，这让简单的范围查找能使用完全顺序的索引访问。
- 一些存储引擎如myisam在内存中只缓存索引，数据则依赖于操作系统来缓存，因此要访问数据需要一次系统调用。这可能导致严重的性能问题，尤其是那些系统调用占了数据访问中的最大开销的场景。
- 由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用，InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果耳机主键能够覆盖查询，则可以避免对主键索引的二次查找。
不是所有类型的索引都可以称为覆盖索引。覆盖索引必须要存储索引列的值，而哈希索引，空间索引和全文索引等都不存储索引列的值，所以mysql只能使用B-Tree索引做覆盖索引。
对于下面这个查询：
这里索引无法使用覆盖查询，原因：
- 没有任何索引能够覆盖这个查询。因为冲寻中表中选择了所有的列，而没有任何索引覆盖了所有的列。
- mysql不能在索引中执行like操作。这是底层存储引擎api限制的。mysql5.5和更早的版本中只允许在索引中做简单的比较操作（等于，不等于，大于）。mysql能在索引中做最左前缀的like比较，因为该操作可以转换为简单比较操作，但如果是通配符开头的like查询，存储引擎就无法做比较匹配。这种情况下，MySql服务器只能提取数据行的值而不是索引值来比较。
