MySQL系列(13)： 索引 之 Hash索引 与 B-Tree索引

　　了解 B-tree 和 Hash 数据结构，有助于预测不同的查询在不同的存储引擎上使用这些数据结构的执行情况。特别是对于允许选择 B-tree 和 Hash 索引的内存存储引擎(MEMORY)。

　　InnoDB 存储引擎默认使用的是 B-tree 数据结构的索引。官方文档：B-tree 索引 与 Hash 索引比较

B-tree索引

1. B树索引支持对列使用**=，>，> =，<，<=或BETWEEN运算符的表达式。 如果LIKE的参数是不以通配符开头的常量字符串，则该类型索引也支持LIKE**比较。

   以下使用了索引的 SELECT 语句：

   //只需要考虑'Patrick' <= key_col < 'Patricl'
   SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%';
   //只需要考虑'Pat' <= key_col < 'Pau'
   SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

   无法使用索引的 SELECT 语句：

   //以 % 通配符开头
   SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';
   //like 不是常量
   SELECT * FROM tbl_name WHERE key_col LIKE other_col;

2. 对于使用 ...like '%string%'且字符串超过三个字符串的语句，MySQL使用 Turbo Boyer-Moore 算法初始化字符串的模式，然后使用此模式更快地执行搜索。

3. 如果对索引列进行 NULL 值判断，col_name IS NULL 语句也能使用索引。

4. 如是没有覆盖 WHERE 子句中多个 AND 条件组的任何索引，不会被优化查询；为了能够使用索引，必须在每个 AND 组中使用索引或前缀索引。

5. 有时即使索引可用， MySQL 也不会使用索引。优化器评估使用索引将需要访问表更大比例的行(即表扫描比使用索引更快)。此情况下，如果查询中使用了 LIMIT 只检索了某些行，MySQL 无论如何都会使用索引，因为可以更快地找到结果中要返回的少数行。

Hash 索引

Hash 索引是采用一定哈希算法，把键值换算成新的哈希值，检索时不需要类似B+树那样从根节点到叶子节点逐级查找，最后才能访问到页节点这样多次的 IO 访问, 只需一次哈希算法即可立刻定位到相应的位置，速度非常快。

1. HASH 索引仅用于等值比较(如：=，<=>)，不能用于范围查找。依赖单值(HASH值)查找的的系统称为 键值存储。

   Hash 索引比较的是进行 Hash 运算之后的 Hash 值，所以它只能用于等值查询，并且效率远高于 B-tree 索引， 但不能用于基于范围的过滤，因为经过 Hash 算法处理之后的 Hash 值的大小关系并不能保证和 Hash 运算前完全一样(原先有序的键值，变成不可连续)，也不适用于排序操作。

2. MySQL 优化器无法使用 Hash 索引来加快排序的操作。此类型索引不能用于按顺序搜索下一个条目。

3. MySQL 无法确定两个值之间大约有多少行(范围优化器使用这一行来决定使用哪个索引)。

4. HASH 索引只能使用全键搜索行，不能使用部分键查询。(B-tree 索引，可以使用键的最左前缀匹配来查找行)。

5. Hash 索引可能存在 Hash值相等的情况，若存在大量 Hash 值相等，则性能并不一定就会比 B-Tree 索引高。

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

参考：
[1] MySQL的InnoDB索引原理详解
[2] MySQL B+树索引和哈希索引的区别
[3] Hash索引与B-Tree索引 介绍及区别