高性能的MySQL（5）建立高性能的索引一哈希索引

哈希索引（hash index）基于哈希表實作，隻有精确比對索引的所有列的查詢才有效，對于每一行資料，存儲引擎都會對所有索引列計算一個哈希碼，不同鍵值的行計算出來的哈希碼也不一樣，哈希碼儲存在哈希索引中，同時哈希表中儲存指向每個資料的指針。

1、Memory引擎支援哈希索引，也支援B-Tree索引，而且支援非唯一的哈希索引，如果多個列的哈希值相同，索引會以連結清單的方式存放多個記錄指針到同一個哈希條目，這個是和特别的。

舉例說明：

1

2

3

4

5

<code>CREATE</code> <code>TABLE</code> <code>`testhash` (</code>

<code>  </code><code>`fname` </code><code>varchar</code><code>(50) </code><code>NOT</code> <code>NULL</code><code>,</code>

<code>  </code><code>`lname` </code><code>varchar</code><code>(50) </code><code>NOT</code> <code>NULL</code><code>,</code>

<code>  </code><code>KEY</code> <code>`fname` (`fname`) USING HASH</code>

<code>) ENGINE=MEMORY </code><code>DEFAULT</code> <code>CHARSET=utf8 |</code>

<a href="http://blog.51cto.com/attachment/201310/152834692.png" target="_blank"></a>

假設索引使用f()生成哈希碼如下

f('Arjen') = 2323

f('Baron') = 7437

f('Peter') = 8784

f('Vadim') = 2458

則哈希索引資料結構如下

槽

值

2323

指向第1行指針

2458

指向第4行指針

7437

指向第2行指針

8784

指向第3行指針

注意哈希碼是有序的，但是資料行不是。

當執行查詢的時候

<code>select</code> <code>* </code><code>from</code> <code>testhash </code><code>where</code> <code>fname=</code><code>'Peter'</code><code>；</code>

先計算哈希碼，然後找到第3行指針，最後比較第3行的值是否為‘Peter’，以确定就是要找的行。

2、哈希索引的限制：

a、哈希索引隻包含哈希碼和行指針，不存儲字段值，是以無法用索引中的值來避免去讀取行。

b、哈希索引資料并不是按照索引值順序存儲的，是以也就無法用于排序。

c、哈希索引也不支援部分索引列比對查找，必須利用所有索引列，因為哈希值是通過所有索引列計算的。

d、哈希索引隻支援等值比較查詢，包括=、in()、&lt;=&gt;(安全比較)比較包含null的時候用。哈希也不支援任何範圍查詢，比方說where price &gt; 100

e、哈希索引非常快，除非有哈希沖突（不同的索引值會有相同的哈希值），這個時候引擎必須周遊連結清單中的所有行來比對。

f、哈希沖突較多的時候，比方列上相同的值比較多的時候，索引維護代價就會比較高。

InnoDB引擎有一個特殊的功能叫做“自适應哈希索引”，由引擎内部實作，也可以關閉。

3、建立自定義哈希索引

如果存儲引擎不支援哈希索引，可以在B-Tree基礎上建立一個僞哈希索引。這個和真正的哈希索引不是一回事，還是用到B-Tree進行查找，隻是利用鍵值的哈希值而不是鍵值來進行索引查找，隻需要在where中手動指定哈希函數。

如果需要存儲大量的URL，并且需要根據URL進行搜尋，如果使用B-Tree來索引URL，存儲内容會很大。比方說下面的查詢

<code>select</code> <code>* </code><code>from</code> <code>url </code><code>where</code> <code>url=</code><code>"http://www.baidu.com"</code><code>;</code>

若删除原來的URL列索引，而新增一個被索引的字段url_crc,使用crc32做哈希就可以使用下面的查詢了

<code>select * from url where url_crc=crc32(</code><code>"http://www.baidu.com"</code><code>) and url=</code><code>"http://www.baidu.com"</code><code>;</code>

這樣性能就會很高。

這樣的缺陷是需要維護哈希值。可以使用觸發器來實作維護工作。

建立一張表

6

<code>CREATE</code> <code>TABLE</code> <code>`pseudohash` (</code>

<code>  </code><code>`id` </code><code>int</code><code>(10) unsigned </code><code>NOT</code> <code>NULL</code> <code>AUTO_INCREMENT,</code>

<code>  </code><code>`url` </code><code>varchar</code><code>(255) </code><code>NOT</code> <code>NULL</code><code>,</code>

<code>  </code><code>`url_crc` </code><code>int</code><code>(10) unsigned </code><code>NOT</code> <code>NULL</code> <code>DEFAULT</code> <code>'0'</code><code>,</code>

<code>  </code><code>PRIMARY</code> <code>KEY</code> <code>(`id`)</code>

<code>) ENGINE=InnoDB </code><code>DEFAULT</code> <code>CHARSET=utf8;</code>

建立觸發器

<code>//插入</code>

<code>delimiter $$</code>

<code>create</code> <code>trigger</code> <code>pseudohash_crc_ins before </code><code>insert</code> <code>on</code> <code>pseudohash </code><code>for</code> <code>each row </code><code>begin</code> <code>set</code> <code>NEW.url_crc=crc32(NEW.url);</code><code>end</code><code>;$$</code>

<code>//更新</code>

<code>create</code> <code>trigger</code> <code>pseudohash_crc_upd before </code><code>update</code> <code>on</code> <code>pseudohash </code><code>for</code> <code>each row </code><code>begin</code> <code>set</code> <code>NEW.url_crc=crc32(NEW.url);</code><code>end</code><code>;$$</code>

<code>delimiter ;</code>

<a href="http://blog.51cto.com/attachment/201310/163436552.png" target="_blank"></a>

<a href="http://blog.51cto.com/attachment/201310/163609204.png" target="_blank"></a>

盡量避免使用太長的哈希函數，會浪費很多空間。除非出現了大量沖突，可以考慮自己實作一個簡單的64位哈希函數，一個簡單的方法是使用MD5()傳回一部分值。

<a href="http://blog.51cto.com/attachment/201310/164018965.png" target="_blank"></a>

有一點值得注意：

當使用哈希索引進行查詢的時候，必須在where中同時跟上rul的比對，一旦出現了哈希沖突，這個真正要查詢的值才會幫助比對出真正的行。

本文轉自shayang8851CTO部落格，原文連結：http://blog.51cto.com/janephp/1309800，如需轉載請自行聯系原作者