Mysql中Btree 与 Hash 索引比较详解

mysql最常用的索引结构是btree(O(log(n)))，但是总有一些情况下我们为了更好的性能希望能使用别的类型的索引。hash就是其中一种选择，例如我们在通过用户名检索用户id的时候，他们总是一对一的关系，用到的操作符只是=而已，假如使用hash作为索引数据结构的话，时间复杂度可以降到O(1)。不幸的是，目前的mysql版本(5.6)中，hash只支持MEMORY和NDB两种引擎，而我们最常用的INNODB和MYISAM都不支持hash类型的索引。

不管怎样，还是要了解一下这两种索引的区别，下面翻译自mysql官网文档中对这两者的解释。

B-Tree 索引特征

B-Tree索引可以被用在像=,>,>=,<,<=和BETWEEN这些比较操作符上。而且还可以用于LIKE操作符，只要它的查询条件是一个不以通配符开头的常量。像下面的语句就可以使用索引：

代码如下	复制代码
SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%'; SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

下面这两种情况不会使用索引：

代码如下	复制代码
SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%'; SELECT * FROM tbl_name WHERE key_col LIKE other_col;

第一条是因为它以通配符开头，第二条是因为没有使用常量。

假如你使用... LIKE '%string%'而且string超过三个字符，MYSQL使用Turbo Boyer-Moore algorithm算法来初始化查询表达式，然后用这个表达式来让查询更迅速。

一个这样的查询col_name IS NULL是可以使用col_name的索引的。

任何一个没有覆盖所有WHERE中AND级别条件的索引是不会被使用的。也就是说，要使用一个索引，这个索引中的第一列需要在每个AND组中出现。

下面的WHERE条件会使用索引：

代码如下	复制代码
... WHERE index_part1=1 AND index_part2=2 AND other_column=3 /* index = 1 OR index = 2 / ... WHERE index=1 OR A=10 AND index=2 / 优化成 "index_part1='hello'" / ... WHERE index_part1='hello' AND index_part3=5 / 可以使用 index1 的索引但是不会使用 index2 和 index3 */ ... WHERE index1=1 AND index2=2 OR index1=3 AND index3=3;

下面的WHERE条件不会使用索引：

代码如下

复制代码

/* index_part1 没有被使用到 */
... WHERE index_part2=1 AND index_part3=2

/* 索引 index 没有出现在每个 where 子句中 */
... WHERE index=1 OR A=10

/* 没有索引覆盖所有列 */
... WHERE index_part1=1 OR index_part2=10

有时候mysql不会使用索引，即使这个在可用的情况下。例如当mysql预估使用索引会读取大部分的行数据时。（在这种情况下，一次全表扫描可能比使用索引更快，因为它需要更少的检索）。然而，假如语句中使用LIMIT来限定返回的行数，mysql则会使用索引。因为当结果行数较少的情况下使用索引的效率会更高。

Hash 索引特征
Hash类型的索引有一些区别于以上所述的特征：

它们只能用于对等比较，例如=和<=>操作符（但是快很多）。它们不能被用于像<这样的范围查询条件。假如系统只需要使用像“键值对”的这样的存储结构，尽量使用hash类型索引。

优化器不能用hash索引来为ORDER BY操作符加速。（这类索引不能被用于搜索下一个次序的值）

mysql不能判断出两个值之间有多少条数据（这需要使用范围查询操作符来决定使用哪个索引）。假如你将一个MyISAM表转为一个依靠hash索引的MEMORY表，可能会影响一些语句（的性能）。

只有完整的键才能被用于搜索一行数据。（假如用B-tree索引，任何一个键的片段都可以用于查找。我觉得可能意味着带通配符LIKE操作符会不起作用）。

Hash 索引效率高，但是 Hash 索引本身由于其特殊性也带来了很多限制和弊端，主要有以下这些。

（1）Hash 索引仅仅能满足"=","IN"和"<=>"查询，不能使用范围查询。

由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值的过滤，不能用于基于范围的过滤，因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系，并不能保证和Hash运算前完全一样。

（2）Hash 索引无法被用来避免数据的排序操作。

由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值，而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样，所以数据库无法利用索引的数据来避免任何排序运算；

（3）Hash 索引不能利用部分索引键查询。

对于组合索引，Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值，而不是单独计算 Hash 值，所以通过组合索引的前面一个或几个索引键进行查询的时候，Hash 索引也无法被利用。

（4）Hash 索引在任何时候都不能避免表扫描。

前面已经知道，Hash 索引是将索引键通过 Hash 运算之后，将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中，由于不同索引键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从 Hash 索引中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。

（5）Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。

对于选择性比较低的索引键，如果创建 Hash 索引，那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦，会浪费多次表数据的访问，而造成整体性能低下。

后记

顺便记录一下在使用mysql过程中碰到的一些问题：

有时候使用脚本迁移数据时会碰到乱码的问题，即使将表字符集设置成utf8也无济于事，这个时候在执行sql之前加一句set names utf8即可。

补充：数据库,mysql教程