使用hash值对长字符串进行索引

cenalulu

假设需要对某个表的字符串类型的列进行索引，并且字符串的长度较长。生成的索引体积就会比较大，同时影响插入及搜索的性能。
这种情况下可以考虑使用对字符串进行hash计算，然后对hash值进行索引。可选的hash函数有crc32(),SHA1,MD5()等等。对于数据量在几十万的数据推荐crc32（）；
下面的本机mysql上进行了以下实验：
测试数据源：
将/var/share/dict/word的文件导入到数据库中。
测试过程：
建立测试表crctest；
创建trigger before insert。使插入word同时更新crc的值。
用awk将word转换成插入语句导入msyql。
分别创建word和crc的索引。
相关数据显示：
mysql> desc crctest;
+-------+------------------+------+-----+---------+-------+
| Field | Type             | Null | Key | Default | Extra |
+-------+------------------+------+-----+---------+-------+
| word  | varchar(50)      | YES  |     | NULL    |       |
| crc   | int(10) unsigned | YES  | MUL | NULL    |       |
+-------+------------------+------+-----+---------+-------+
*************************** 1. row ***************************
       Table: crctest
  Non_unique: 1
    Key_name: crcidx
Seq_in_index: 1
Column_name: crc
   Collation: A
Cardinality: 479829
    Sub_part: NULL
      Packed: NULL
        Null: YES
  Index_type: BTREE
     Comment:
*************************** 2. row ***************************
       Table: crctest
  Non_unique: 1
    Key_name: wordidx
Seq_in_index: 1
Column_name: word
   Collation: A
Cardinality: 479829
    Sub_part: 10
      Packed: NULL
        Null: YES
  Index_type: BTREE
     Comment:
性能测试：
index大小对比
如果对crc做index，index的大小为：Index_length: 7720960
如果直接对word做index，index的大小为：Index_length: 6218752
分析：由于英文单词本身的字符长度不长，而crc值的长度普遍在8位数字左右，因此crc的index大小反而更大。如果字符串是像网站这样的较长的字符时，crc的优势会很明显。
select性能对比：随机的从word文件中选出2000多个词汇对表进行匹配，语句如下。
mysql> select * from crctest where `word` in （'word','word1'...);
2883 rows in set (0.41 sec)
mysql> select * from crctest where `crc` = crc32(crc32('word'),crc32('word1')...);
2712 rows in set (0.33 sec)
分析：对于2000多数据量的匹配可以看出此时crc就已经比char的匹配效率高出25%。如果数据量更大，优势会更明显。之所以
重复度分析：
由于crc32的值当数据量巨大的时候可能会产生重复。测试数据库中重复值发生的概率是 25/479829 =0.00521%不过当数据量不断增大时可以预计重复值会越来越多。为了防止重复值干扰查询可以使用以下select进行查询 select * from crctest where `crc` = crc32('test') and `word`='test';来进行双重限定，不过会使性能有一定的降低
结论：
使用crc32等hash函数的值，对字符串进行索引能够提升查询性能。
但是当数据量超过10w级时，会发生crc重值情况，需要在查询语句中加入双重判断避免重值，同时牺牲部分性能。
               
               
               

本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u3/90603/showart_2027218.html