MySQL索引
索引具有哪些基本实现方式？分别适合什么查询？引擎支持什么？如何设计3*查询？
分类
B树
存储引擎以不同的方式使用B-Tree索引，性能也各有不同，各有优劣。例如，MyISAM 使用前缀压缩技术使得索引更小，但InnoDB则按照原数据格式进行存储。再如 MyISAM索引通过数据的物理位置引用被索引的行，而InnoDB则根据主键引用被索引的行。
B-Tree索引适用于全键值、键值范围或键前缀查找。 其中键前缀查找只适用于根据最左前缀的查找。前述索引对如下类型的查询有效。
全值匹配 全值匹配指的是和索引中的所有列进行匹配，例如前面提到的索引可用于查找姓名 为CubaAllen、出生于1960-01-01的人。
匹配最左前缀 前面提到的索引可用于查找所有姓为Allen的人，即只使用索引的第一列。匹配列前缀 也可以只匹配某一列的值的开头部分。例如前面提到的索引可用于查找所有以J开头的姓的人。这里也只使用了索引的第一列。 - 最左查询原则 最左前缀原则是指在多列组合索引中，只有查询条件中从最左边开始的列是连续出现的情况下，才能命中索引。如果跳过了组合索引中的某一列，则该列及其后续的列索引将无法生效。
匹配范围值 例如前面提到的索引可用于查找姓在Allen和Barrymore之间的人。这里也只使用了索引的第一列。
精确匹配某一列并范围匹配另外一列 前面提到的索引也可用于查找所有姓为Allen,并且名字是字母K开头(比如Kim、 Karl等)的人。即第一列last_name全匹配，第二列first_name范围匹配。
只访问索引的查询 B-Tree通常可以支持“只访问索引的查询”,即查询只需要访问索引，而无须访问，数据行。
B-Tree索引从最左边的限制开始检查，不能跳过某一列，中间如果有范围查询，则无法使用到后面的索引
聚簇索引
将数据存在b树索引叶子节点中，一般只能按照一个列聚集，插入数据在这个列最好是一直递增的
覆盖索引
如果一个索引包含(或者说覆盖)所有需要查询的字段的值，称之为“覆盖索引”。
哈希
基于哈希表实现，支持精准匹配索引所有列的查询，速度较快。 - 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。 - 哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。 - 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列(A,B)上建立哈希索引，如果查询只有数据列A, 则无法使用该索引。 - 哈希索引只支持等值比较查询，包括=、IN()、<=>(注意◇和<=>是不同的操作)。 也不支持任何范围查询，例如WHERE price >100。 - 访问哈希索引的数据非常快，除非有很多哈希冲突(不同的索引列值却有相同的哈希值)。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。 - 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。例如，如果在某个选择性很低(哈希冲突很多)的列上建立哈希索引，那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应行的引用，冲突越多， 代价越大。
通过在where子句中显式使用哈希函数，我们可以在只支持b树索引的索引中也使用哈希索引的特性，这一方法的限制是需要维护哈希值，且注意不要使用产生长整数的哈希函数，并要记得在where子句中比对常量值，免得由于哈希冲突而查询失败
其他
- 空间索引
- 全文索引
- 分形树索引
案例学习
三星原则
Lahdenmaki和Leach在书中介绍了如何评价一个索引是否适合某个查询的“三星系统” (three-star system):索引将相关的记录放到一起则获得一星；如果索引中的数据顺序和查找中的排列顺序一致则获得二星；如果索引中的列包含了查询中需要的全部列则获得 “三星”
常用经验
- 表达式中，列条件独立出来
- 只索引部分前缀
- 选择性高的放前面
- 表很小时不用索引