Home >Database >Mysql Tutorial >Mysql 索引的基础(下)_MySQL

Mysql 索引的基础(下)_MySQL

WBOY
WBOYOriginal
2016-05-30 17:10:20965browse

如果需要存储大量的URL并需要根据URL进行搜索查找。如果使用B-Tree 来存储URL,存储的内容就会很大,因为URL本身都很长。正常情况下会有如下查询:

 

SELECT id FROM url WHERE url="http://www.baidu.com";

 

若删除原来URL上的索引,而新增一个被索引的url_crc列,使用CRC32做hash ,就可以用下面的方式查询:

 

SELECT id FROM url WHERE url='http://www.baidu.com' AND rul_crc=CRC32('http://www.baidu.com');

 

这样做性能非常高,因为MySQL 优化器会使用这个选择性很高而体积很小的基于url_crc列的索引来完成查找。即使有多个相同的索引值,查找任然很快,只需要根据hash值做快速的整数比较就能找到索引条目,然后一一返回对应的行。另外一种方式就是对完整的URL字符串做索引,那样会非常慢。

 

这样实现的缺陷是需要维护hash值。可以手动维护,可以触发器实现。如果采用这种方式,记住,不要使用SHA1()和MD5()作为哈希函数。因为这两个函数计算出来的hash值时非常长的字符串,会浪费更大的空间,比较时也会更慢。SHA1()和MD5()是强加密函数,设计目标是最大限度的消除冲突,蛋这里并不需要这样搞的要求。简单hash函数的冲突在一个可以接受的范围,同事有能提供更好的性能。

 

如果数据表非常大,CRC32()会出现大量的hash冲突,则可以考虑自己实现一个简单的64位hash函数。这个自定义的函数要返回整数,而不是字符串。一个简单的办法可以使用MD5()函数返回值的一部分来作为自定义hash函数。这肯能比自己写一个hash算法的性能要差,不过这样实现最简单。

 

SELECT CONV(RIGHT(MD5('http://www.baidu.com'),16),16,10) AS HASH64.

 

处理hash冲突。当使用hash索引进行查询的时候,必须在WHERE子句中包含常量值:

 

SELECT id from url WHERE url=crc32('http://www.baidu.com') AND url='http://www.baidu.com';

 

一旦出现hash冲突,另一个字符串的hash值也恰好是相同的,则下面的语句是无法正确工作的:

 

SELECT id from url WHERE url=crc32('http://www.baidu.com');

 

因为所谓的‘生日悖论’ 出现hash冲突的概率的增长率可能比想象的要快的多,CRC32()返回的是32位整数,当索引有9.3W条记录时,出现冲突的概率是1%。例如,我们将'/usr/share/dic/words' 中的词倒数数据表,并进行crc32()计算,最后会有98569行。这就已经出现一次hash冲突了。要避免hash冲突问题,必须在WHERE 条件中带入hahs值和对应的列值。如果不是想查询具体的值,例如只是统计记录数(不精确的),则可以不带入列值,直接使用crc32()的hash值查询即可。还可以使用FNV64()函数作为hash函数,hash值为64位,速度非常快,且冲突比crc32()要少很多。

Statement:
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn