什么是索引
索引类似于书本目录，是数据库存储引擎维护的用于快速查找到记录的一种数据结构，它是对查询性能优化的最有效手段。
MySQL索引是在存储引擎层而不是服务器层实现的，不同存储引擎的索引工作方式也不一样，也不是所有的存储引擎都支持所有的索引；即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。
索引的优点
- 索引大大减少了服务器需要扫描的数据量。（索引快速查找特性）
- 索引可以帮助服务器避免排序和临时表。（顺序存储，索引数据可以用作order by或group by）
- 索引可以将随机I/O变成顺序I/O。（覆盖索引）
其实这也是查询优化的三个方向：减少服务器扫描的数据量；避免排序和临时表的出现；将随机I/O变为顺序I/O。
如何评价一个索引是否适合某个查询
- 一星：索引将相关的记录放到一起。（是否建立索引）
- 二星：如果索引中的数据顺序和查找中的排列顺序一致则获得。（是否满足 最左前缀原则）
- 三星：如果索引中的列包含了查询中需要的全部列。（是否是覆盖索引）
B-TREE索引
B-TREE索引是我们很常用的索引，大多数MySQL存储引擎都支持这种索引，但是不是所有存储引擎底层都是使用B-TREE来实现这种索引存储结构的，比如 InnoDB就是使用B+TREE数据结构。
存储引擎以不同的方式使用B-TREE索引，性能也各有不同，各有优劣。例如，MyISAM使用前缀压缩技术使得索引更小，但InnoDB则按照原数据格式进行存储。再如，MyISAM索引通过数据的物理位置引用被索引的行。而InnoDB则根据主键引用被索引的行。
B-TREE的叶子节点比较特别，它们的指针指向的是被索引的数据。
B-TREE对索引列是顺序组织存储的，所以非常适合查找范围数据。例如，在一个基于文本域的索引树上，按字母顺序传递连续的值进行查找是非常合适的，所以像“找出所有以I到K开头的名字”，这样的查找效率会非常高。并且由于索引树中的节点是有序的，所以对索引中涉及到的字段排序需求，索引也非常有帮助。
当遇到复合索引的情况，B-TREE进行排序的依据是CREATE TABLE语句中定义索引时列的顺序，先按照第一个索引字段进行排序，相同的情况下 再依次使用后面的字段进行排序。
缺点：
- B-TREE 必须遵循“最左前缀原则”。
- 如果查询中有某列的范围查询，则其右边所有列都无法使用索引优化查找。参见实例:MySQL 多列索引优化小记
假设有如下表：
CREATE TABLE people(
last_name varchar(50) not null ,
first_name varchar(50) not null ,
dob date not null ,
gender enum('m','f') not null ,
key(last_name , first_name , dob)
);
其索引包含表中每一行的last_name、first_name和dob列。其结构大致如下：
哈希索引
哈希索引是基于哈希表实现的，针对每行数据，存储引擎都会对所有的索引列计算出一个hash值；哈希索引将所有的hash值存储在索引中，同时在hash表中保存指向每个数据行的指针。因此，只有精确匹配索引所有列的查询才有效。
在MySQL中，只有Memory引擎显示支持哈希索引。这也是Memory引擎表的默认索引类型，Memory引擎同时也支持B-TREE索引。值得一提的是，Memory引擎是支持非唯一哈希索引的，如果多个列的哈希值相同，索引会以链表的方式存存放多个记录指针到同一个哈希条目中。
1.优点：hash索引本身只存储对应的hash值和行指针，所以索引非常紧凑，索引本身非常小，查找数据块。
2.缺点:
- 哈希索引值包含哈希值和行指针，不包含真实索引列值，所以不能使用索引中的值来避免再次读取行(就是没有“覆盖索引”一说了)。不过，因为记录了行指针，访问内存中的行的数据非常快，所以大部分情况下这一点对性能的影响不是很大。
- 哈希索引数据不是按照索引值顺序存储的，所以也就无法用于排序。
- 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
- 哈希索引只支持等值比较，包括=、IN()、<=>；也不支持然和范围查询。
- 如果哈希索引冲突非常多的话，一些索引维护操作的代价也会很高。冲突越多，代价越大。
3.InnoDB自适应哈希索引
自适应哈希索引：当InnoDB注意到某些索引值被使用得非常频繁时，它会在内存中基于B-Tree索引之上再建立一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速哈希查找。
4.创建自定义哈希索引
思路：在B-Tree基础上创建一个伪哈希索引。查找时，是使用哈希值而不是键本身进行索引查找。这就需要在查询的WHERE子句中手动指定使用哈希函数。
下面是一个实例，例如需要存储大量的URL，并需要根据URL进行搜索查找。如果使用B-TREE来存储URL，存储内容就会很大，因为URL本身都很长。正常情况下会有如下查询：
mysql> SELECT id FROM url WHERE url = "http://www.mysql.com" ;
若删除原来URL列上的索引，而新增一个被索引的url_crc列，使用CRC32做哈希，就可以使用下面的方式查询：mysql> SELECT id FROM url WHERE url = "http://www.mysql.com" AND url_crc = CRC32("http://www.mysql.com");
相比对完整的URL字符串进行索引查询，这种方式只需要计算进行快速的计算和等值比较就能找到索引条目。
Hash索引举例：
1.假设有如下数据表：
CREATE TABLE testhash (
fname VARCHAR(50) NOT NULL,
lname VARCHAR(50) NOT NULL,
KEY USING HASH(fname)
) ENGINE=MEMORY;
2.表中有如下数据：
3.假设索引使用hash函数f()，如下所示：
f('Arjen') = 2323
f('Baron') = 7437
f('Peter') = 8784
f('Vadim') = 2458
则Hash索引的数据结构如下：
注意每个槽的编号是顺序的，但是数据行不是。现在，来看如下查询：
SELECT lname FROM testhash WHERE fname = 'Peter';
MySQL先计算‘Peter’的哈希值，并使用该值寻找对应的记录指针。因为f('peter')=8784，所以MySQL在索引中查找8784，可以很快找到指向第3行的指针，最后一步是比较第三行的值是否为‘Peter’，以确保就是要查找的行。
全文索引
全文索引，目前只有MyISAM引擎支持。其可以在CREATE TABLE，ALTER TABLE，CREATE INDEX使用，不过目前只有CHAR、VARCHAR、TEXT列上可以创建全文索引。值得一提的是，在数据量较大时候，现将数据放入一个没有全局索引的表中，然后再用CREATE INDEX创建FULLTEXT索引，要比先为一张表建立FULLTEXT然后再将数据写入的速度快很多。
全文索引并不是和MyISAM一起诞生的，它的出现是为了解决WHERE name LIKE "%word%"这类针对文本的模糊查询效率较低的问题。在没有全文索引之前，这样一个查询语句要进行遍历数据表操作的，可见，在数据量较大时是极其的耗时的。
个人觉得全文索引在实际应用中并不是特别多，一般情况下都是使用Lucene、Solr这种搜索引擎去代替，故这里不再进行详细介绍。
唯一索引
其实，唯一索引和BTREE索引或者HASH索引并不是同一级别的，但是这里顺带说一下唯一索引。
普通索引的唯一任务就是加快对数据的访问速度，应该只为那些最经常出现在查询条件或排序条件中的数据列创建索引。普通索引允许被索引的数据列包含重复的值，但是唯一索引不允许。
对于唯一索引，MySQL会在有新记录插入数据库表时，自动检查新纪录的这个字段值是否已经在某个记录的这个字段里出现过了。如果是，MySQL将拒绝插入那条新纪录。这样的好处：一是简化了MySQL对这个索引的管理工作，这个索引也因此而变得更有效率；二是MySQL会在有新记录插入时，自动做唯一性校验。
- 全文摘录自《高性能MySQL》
- 一篇对高性能MySQL索引部分总结的很好的网文：理解MySQL——索引与优化