Mysql中Btree 與 Hash 索引比較詳解

我們在mysql中常用的索引是btress但有時我們也會使用到hash索引了，下面我來給大家分析一下Btree 與 Hash 索引比較,各位朋友可參考。

mysql最常用的索引結構是btree(O(log(n)))，但是總有一些情況下我們為了更好的性能希望能使用別的類型的索引。hash就是其中一種選擇，例如我們在通過用戶名檢索用戶id的時候，他們總是一對一的關系，用到的操作符只是=而已，假如使用hash作為索引數據結構的話，時間復雜度可以降到O(1)。不幸的是，目前的mysql版本(5.6)中，hash只支持MEMORY和NDB兩種引擎，而我們最常用的INNODB和MYISAM都不支持hash類型的索引。

不管怎樣，還是要了解一下這兩種索引的區別，下面翻譯自mysql官網文檔中對這兩者的解釋。

B-Tree 索引特征

B-Tree索引可以被用在像=,>,>=,<,<=和BETWEEN這些比較操作符上。而且還可以用於LIKE操作符，只要它的查詢條件是一個不以通配符開頭的常量。像下面的語句就可以使用索引：

 代碼如下 復制代碼 SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';

 

下面這兩種情況不會使用索引：

 代碼如下 復制代碼 SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';
SELECT * FROM tbl_name WHERE key_col LIKE other_col;

 

第一條是因為它以通配符開頭，第二條是因為沒有使用常量。

假如你使用... LIKE '%string%'而且string超過三個字符，MYSQL使用Turbo Boyer-Moore algorithm算法來初始化查詢表達式，然後用這個表達式來讓查詢更迅速。

一個這樣的查詢col_name IS NULL是可以使用col_name的索引的。

任何一個沒有覆蓋所有WHERE中AND級別條件的索引是不會被使用的。也就是說，要使用一個索引，這個索引中的第一列需要在每個AND組中出現。

下面的WHERE條件會使用索引：

 代碼如下 復制代碼
 ... WHERE index_part1=1 AND index_part2=2 AND other_column=3
    /* index = 1 OR index = 2 */
... WHERE index=1 OR A=10 AND index=2
    /* 優化成 "index_part1='hello'" */
... WHERE index_part1='hello' AND index_part3=5
    /* 可以使用 index1 的索引但是不會使用 index2 和 index3 */
... WHERE index1=1 AND index2=2 OR index1=3 AND index3=3;

 

下面的WHERE條件不會使用索引：

 代碼如下 復制代碼

/* index_part1 沒有被使用到 */
... WHERE index_part2=1 AND index_part3=2

    /* 索引 index 沒有出現在每個 where 子句中 */
... WHERE index=1 OR A=10

    /* 沒有索引覆蓋所有列 */
... WHERE index_part1=1 OR index_part2=10

 

有時候mysql不會使用索引，即使這個在可用的情況下。例如當mysql預估使用索引會讀取大部分的行數據時。（在這種情況下，一次全表掃描可能比使用索引更快，因為它需要更少的檢索）。然而，假如語句中使用LIMIT來限定返回的行數，mysql則會使用索引。因為當結果行數較少的情況下使用索引的效率會更高。

Hash 索引特征
Hash類型的索引有一些區別於以上所述的特征：

它們只能用於對等比較，例如=和<=>操作符（但是快很多）。它們不能被用於像<這樣的范圍查詢條件。假如系統只需要使用像“鍵值對”的這樣的存儲結構，盡量使用hash類型索引。

優化器不能用hash索引來為ORDER BY操作符加速。（這類索引不能被用於搜索下一個次序的值）

mysql不能判斷出兩個值之間有多少條數據（這需要使用范圍查詢操作符來決定使用哪個索引）。假如你將一個MyISAM表轉為一個依靠hash索引的MEMORY表，可能會影響一些語句（的性能）。

只有完整的鍵才能被用於搜索一行數據。（假如用B-tree索引，任何一個鍵的片段都可以用於查找。我覺得可能意味著帶通配符LIKE操作符會不起作用）。

 Hash 索引效率高，但是 Hash 索引本身由於其特殊性也帶來了很多限制和弊端，主要有以下這些。

（1）Hash 索引僅僅能滿足"=","IN"和"<=>"查詢，不能使用范圍查詢。

由於 Hash 索引比較的是進行 Hash 運算之後的 Hash 值，所以它只能用於等值的過濾，不能用於基於范圍的過濾，因為經過相應的 Hash 算法處理之後的 Hash 值的大小關系，並不能保證和Hash運算前完全一樣。

（2）Hash 索引無法被用來避免數據的排序操作。

由於 Hash 索引中存放的是經過 Hash 計算之後的 Hash 值，而且Hash值的大小關系並不一定和 Hash 運算前的鍵值完全一樣，所以數據庫無法利用索引的數據來避免任何排序運算；

（3）Hash 索引不能利用部分索引鍵查詢。

對於組合索引，Hash 索引在計算 Hash 值的時候是組合索引鍵合並後再一起計算 Hash 值，而不是單獨計算 Hash 值，所以通過組合索引的前面一個或幾個索引鍵進行查詢的時候，Hash 索引也無法被利用。

（4）Hash 索引在任何時候都不能避免表掃描。

前面已經知道，Hash 索引是將索引鍵通過 Hash 運算之後，將 Hash運算結果的 Hash 值和所對應的行指針信息存放於一個 Hash 表中，由於不同索引鍵存在相同 Hash 值，所以即使取滿足某個 Hash 鍵值的數據的記錄條數，也無法從 Hash 索引中直接完成查詢，還是要通過訪問表中的實際數據進行相應的比較，並得到相應的結果。

（5）Hash 索引遇到大量Hash值相等的情況後性能並不一定就會比B-Tree索引高。

對於選擇性比較低的索引鍵，如果創建 Hash 索引，那麼將會存在大量記錄指針信息存於同一個 Hash 值相關聯。這樣要定位某一條記錄時就會非常麻煩，會浪費多次表數據的訪問，而造成整體性能低下。

後記

順便記錄一下在使用mysql過程中碰到的一些問題：

有時候使用腳本遷移數據時會碰到亂碼的問題，即使將表字符集設置成utf8也無濟於事，這個時候在執行sql之前加一句set names utf8即可。