-B+樹索引和HASH索引有哪些不一樣【MySQL系列】

我們都了解B+樹和Hash索引的差別有助于我們預測索引在不同的存儲引擎中是怎麼執行查詢的。

我們都了解B+樹和Hash索引的差別有助于我們預測索引在不同的存儲引擎中是怎麼執行查詢的。

B+ TREE 索引特性

B數是一種在資料庫索引中流行的樹資料結構。該結構始終保持排序，進而可以快速查找精确比對。MySQL中使用的是B樹的一種變體，B+樹，這種類型的索引可用于大多數存儲引擎，例如InnoDB和 MyISAM。B+樹中的B不是代表二叉(binary)，而是代表平衡(balance)，因為 B+樹是從最早的平衡二叉樹演化而來，但是B+樹不是一個二叉樹。

B+樹可以用在=、 >、 >=、 <、 <= 、BETWEEN 等比較運算符中進行比較。也可以用在不是以通配符%開頭的LIKE語句中進行比較，因為LIKE語句如果以通配符開頭，索引可能會失效。

比如下面的SQL語句就沒有使用索引即使key_col建立了索引。

SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';

1.

如果使用LIKE ‘%string_like%’ 進行查詢時string_like字元串超過三個字元，MySQL将使用Turbo Boyer-Moore算法對string_like字元串進行初始化以達到快速查詢的目的。

Boyer-Moore算法在用于查找子字元串的算法當中，BM（Boyer-Moore）算法被認為最高效的字元串搜尋算法，它由Bob Boyer和J Strother Moore設計于1977年。一般情況下，比KMP算法快3-5倍。該算法常用于文本編輯器中的搜尋比對功能，比如大家所熟知的GNU grep指令使用的就是該算法，這也是GNU grep比BSD grep快的一個重要原因。 — 百度百科

有時候即使查詢能命中索引，MySQL也不會使用索引。當MySQL優化器發現通過索引需要掃描的行占比很大，在這種情況下，表掃描可能會快得多，因為它需要查找的行更少。

Hash 索引特性

Hash 索引是通過hash算法進行索引的建立和查詢的，hash算法是把任意長度的輸入通過hash算法變換成固定長度的輸出，該輸出就是hashcode，hash算法本質上來說是壓縮算法。當資料量大很可能進行大量hash沖突，影響性能。是以hash是以更适合精确查詢。

兩者差別

B+樹索引支援精确查詢、比較查詢、範圍查詢、模糊查詢、排序等多種查詢方式。如下：

• 進口氣動球閥

而Hash 索引更适合精确查詢，也不能進行 ORDER BY排序操作，比較查詢、範圍查詢、模糊查詢更不好處理了。

總結

B+樹索引支援的查詢方式更多，更适合作為資料庫索引的資料結構。但是如果系統需要Hash 索引這種key-value查詢的方式也可以選擇Hash 索引。