MySQL B-Tree索引、Hash索引和位图索引

MYSQL最常用的索引结构是BTREE，时间复杂度为O(log(n))，但是总有一些情况下我们为了更好的性能希望能使用别的类型的索引。哈希索引就是其中一种选择。

哈希索引结构的特殊性，其检索效率非常高，索引的检索可以一次定位，不像B-Tree索引需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以哈希索引的查询效率要远高于B-Tree索引。例如我们在通过用户名检索用户id的时候，他们总是一对一的关系，用到的操作符只是=而已，假如使用hash作为索引数据结构的话，时间复杂度可以降到O(1)。
需要注意的是，目前的mysql版本(5.6)中，只有MEMORY和NDB两种引擎支持哈希索引，而我们最常用的INNODB和MYISAM都不支持哈希索引。
既然哈希索引的检索效率很高，那为什么大家不都用哈希索引而还要使用B-Tree索引呢，主要是因为哈希索引自身结构的特殊性使得它存在很多的限制。

1、哈希索引的使用场景

a、哈希索引只支持等值比较查询，如：=，in()，<=>(安全比较，比较包含null的时候用)，不支持任何范围查询（必须给定具体的where条件值来计算hash值，所以不支持范围查询）。
b、哈希索引数据并不是按照索引列的值顺序存储的，所以也就无法用于排序。
c、哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引的全部列值内容来计算哈希值的。如：数据列（a,b）上建立哈希索引，如果只查询数据列a，则无法使用该索引。
d、哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行（即不能使用哈希索引来做覆盖索引扫描），不过，访问内存中的行的速度很快（因为memory引擎的数据都保存在内存里），所以大部分情况下这一点对性能的影响并不明显。
e、访问哈希索引的数据非常快，除非有很多哈希冲突，当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
f、如果哈希冲突很多的话，一些索引维护操作的代价也很高，如：如果在某个选择性很低的列上建立哈希索引（即很多重复值的列），那么当从表中删除一行时，存储引擎需要遍历对应哈希值的链表中的每一行，找到并删除对应的引用，冲突越多，代价越大。

2、B-Tree索引的使用场景

a、B-Tree索引支持范围查询，可以被用在像=，>，>=，<，<=和BETWEEN这些比较操作符上。
b、B-Tree索引而且还可以用于LIKE操作符，只要它的查询条件是一个不以通配符开头的常量。
c、由于B-Tree中节点是顺序存储的，可以对查询结果进行order by排序。
d、查询必须从索引的最左边的列开始，即索引最左列匹配原则。
e、不能跳过某一索引列。例如，建立组合索引 key(last_name, first_name, birthday)，你不能利用索引查找last name为Smith且出生于某一天的人。
f、存储引擎不能使用索引中范围条件右边的列。例如，如果你的查询语句为WHERE last_name='Smith' AND first_name LIKE 'J%' AND birthday='1976-12-23'，则该查询只会使用索引中的前两列，因为LIKE是范围查询。

3、位图索引的使用场景

位图索引是一种针对多个字段的简单查询设计一种特殊的索引，适用范围比较小，只适用于字段值固定并且值的种类很少的情况，比如性别，只有男和女，或者级别，状态等等，并且只有在同时对多个这样的字段查询时才能体现出位图的优势。
位图的基本思想就是对每一个条件都用0或者1来表示，如有5条记录，性别分别是男，女，男，男，女，那么如果使用位图索引就会建立两个位图，对应男的10110和对应女的01001,这样做有什么好处呢，就是如果同时对多个这种类型的字段进行and或or查询时，可以使用按位与和按位或来直接得到结果了。

关于自定义哈希索引：

在《高性能的Mysql》这本树中，作者举了一个自定义哈希索引的列子。假设我们在一个表中大量存储了URL，而且需要根据URL来进行查找。因为URL比较长，这个时候如果我们使用B-Tree索引，索引会非常的大。解决的办法是删除原来的URL列索引，而新增一个被索引的列，用来存放URL的哈希值，可以通过CRC32对URL进行计算，并存放在列表中，在查找的时候通过CRC32对url进行计算匹配列表中的hash值。
但是这个地方需要注意hash冲突的问题，所以在查询的时候需要添加url的匹配。例如：where url_crc=CRC32('http://www.pieruo.com/p/11564.html') and url='http://www.pieruo.com/p/11564.html'。

其它说明：

a、在Mysql中InnoDB引擎有一个特殊的功能叫做自适应哈希索引，他会在内存中基于B-Tree索引的基础上面创建一个哈希索引，这让B-Tree索引也具备了一些哈希索引的优点。
b、B-Tree索引使用语法：unique key unique_username using btree('user_name')，这里的using btree 只是显示的指定的使用的索引的方式为B-Tree，对于innodb来说默认的索引方式也是用B-Tree，因此，也可以不写。