在MySQL中建立自己的哈希索引（书摘备查）

在MySQL中，只有Memory存储引擎支持显式的哈希索引，但是可以按照InnoDB使用的方式模拟自己的哈希索引。这会让你得到某些哈希索引的特性，例如很大的键也只有很小的索引。 想法非常简单：在标准B-Tree索引上创建一个伪哈希索引。它和真正的哈希索引不是一回事，因为它还是使用B-Tree索引进行查找。然而，它将会使用键的哈希值进行查找，而不是键自身。你所要做的事情就是在where子句中手动地定义哈希函数。 一个不错的例子就是URL查找。URL通常会导至B-Tree索引变大，因为它们非常长。通常会按照下面的方式来查找URL表：

select id from url where url='http://www.mysql.com';

但是，如果移除url列上的索引并给表添加一个被索引的url_crc列，就可以按照下面的方式进行查询：

select id from url where url='http://www.mysql.com' and url_crc=crc32('http://www.mysql.com');

这种方式很不错，因为MysSQL查询优化器注意到url_crc列上有很小的、选择性很高的索引，并且它会使用里面的值进行索引查找。即使有几行相同的url_crc值，也很容易进行精确地对比来确定需要的行。替代方案是把完整的URL索引为字符串，它要慢得多。 这个办法的一个缺点是要维护哈希值。你可以手工进行维护，在MySQL 5.0及以上版本中，可以使用触发器来进行维护。下面的例子显示了触发器如何在插入和更新值的时候维护url_crc列。首先，创建一个表：

create table pseudohash (
    id int unsigned not null auto_increment,
    url varchar(255) not null,
    url_crc int unsigned not null default 0,
    primary key (id),
    key (url_crc)
);

接下来创建触发器：

delimiter |

create trigger pseudohash_crc_ins before insert on pseudohash
for each row begin
    set new.url_crc=crc32(new.url);
end;
|

create trigger pseudohash_crc_upd before update on pseudohash
for each row begin
    set new.url_crc=crc32(new.url);
end;
|

delimiter ;

剩下的工作就是验证触发器自动维护了哈希值：

insert into pseudohash (url) values ('http://www.mysql.com');
select * from pseudohash;

update pseudohash set url='http://www.,ysql.com/' where id=1;
select * from pseudohash;

使用这种方式，就不应该使用sha1()和md5()这些哈希函数。它们返回很长的字符串，会浪费大量的存储空间并且减慢比较速度。它们是强加密函数，被设计为不产生任何冲突。这并不是我们的目标。简单的哈希函数能在有较好性能的同时保证可接受的冲突率。 如果表有很多行并且crc32()产生了很多冲突，就要实现自己的64位哈希函数。要确保自己的函数返回整数，而不是字符串。一种实现64位哈希函数的方法是利用MD5返回的部分值：

select conv(right(md5('http://www.mysql.com/'),16),16,10) as hash64;

处理哈希碰撞 当通过哈希值搜索值的时候，必须在where子句中包含一个常量值（literal value）：

select id from url where url_crc=crc32('http://www.mysql.com') and url='http://www.mysql.com';

下面的查询不能正常工作，因为可能返回多行：

select id from url where url_crc=crc32('http://www.mysql.com');

哈希碰撞几率的增长比想象的要快。crc32()返回一个32位的整数值，因此至少需要93000个值才会出现碰撞（k*(k-1)/2n=1，其中n=2^32，则k=92682）。 为了避免碰撞问题，必须在where子句中定义两个条件。如果碰撞不是问题，不如进行统计并且不需要精确的结果，就可以通过在where子句中使用crc32()值简化查询，并得到效率提升。