摘要：Mysql中支持B-Tree與Hash兩種索引方法，最常用的也是默認(rèn)的B-Tree方法索引，其次就是最容易被忽略的Hash方法索引。下面將分別介紹兩種索引方法的區(qū)別...

一、 B-Tree索引

B-Tree(也稱 b+ 樹) 索引是 MySQL 數(shù)據(jù)庫中使用最為頻繁的索引類型，除了 Archive 存儲引擎之外的其他所有的存儲引擎都支持 B-Tree 索引。不僅僅在 MySQL 中是如此，實(shí)際上在其他的很多數(shù)據(jù)庫管理系統(tǒng)中B-Tree 索引也同樣是作為最主要的索引類型，這主要是因?yàn)?B-Tree 索引的存儲結(jié)構(gòu)在數(shù)據(jù)庫的數(shù)據(jù)檢 索中有非常優(yōu)異的表現(xiàn)。

一般來說， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的結(jié)構(gòu)來存儲的，也就是所有實(shí)際需要的數(shù)據(jù)都存放于 Tree 的 Leaf Node ，而且到任何一個 Leaf Node 的最短路徑的長度都是完全相同的，所以我們大家都稱之為 B-Tree 索引當(dāng)然，可能各種數(shù)據(jù)庫（或 MySQL 的各種存儲引擎）在存放自己的 B-Tree 索引的時候會對存儲結(jié)構(gòu)稍作改造。如 Innodb 存儲引擎的 B-Tree 索引實(shí)際使用的存儲結(jié)構(gòu)實(shí)際上是 B+Tree ，也就是在 B-Tree 數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上做了很小的改造，在每一個

Leaf Node 上面出了存放索引鍵的相關(guān)信息之外，還存儲了指向與該 Leaf Node 相鄰的后一個 LeafNode 的指針信息，這主要是為了加快檢索多個相鄰 Leaf Node 的效率考慮。

在 Innodb 存儲引擎中，存在兩種不同形式的索引，一種是 Cluster 形式的主鍵索引（ Primary Key ），另外一種則是和其他存儲引擎（如 MyISAM 存儲引擎）存放形式基本相同的普通 B-Tree 索引，這種索引在 Innodb 存儲引擎中被稱為 Secondary Index 。

實(shí)現(xiàn)原理：

上圖顯示了一種索引方式。左邊是數(shù)據(jù)庫中的數(shù)據(jù)表，有col1和col2兩個字段，一共有15條記錄；右邊是以col2列為索引列的B-Tree索引，每個節(jié)點(diǎn)包含索引的鍵值和對應(yīng)數(shù)據(jù)表地址的指針，這樣就可以都過B-Tree在O(logn)的時間復(fù)雜度內(nèi)獲取相應(yīng)的數(shù)據(jù)，這樣明顯地加快了檢索的速度。

B-Tree是一種平衡多叉排序樹，是一種動態(tài)查找效率很高的樹形結(jié)構(gòu)。B-Tree中所有結(jié)點(diǎn)的孩子結(jié)點(diǎn)的最大值稱為B-Tree的階，B-Tree的階通常用m表示，簡稱為m叉樹。一般來說，應(yīng)該是m>=3。一顆m階的B-Tree或是一顆空樹，或者是滿足下列條件的m叉樹：

樹中每個結(jié)點(diǎn)最多有m個孩子結(jié)點(diǎn)；

除根結(jié)點(diǎn)外，其它結(jié)點(diǎn)至少有(int)m/2+1個孩子結(jié)點(diǎn)；

若根結(jié)點(diǎn)不是葉子節(jié)點(diǎn)，則根結(jié)點(diǎn)至少有2個孩子結(jié)點(diǎn)；

結(jié)點(diǎn)的結(jié)構(gòu)：  

其中，n為結(jié)點(diǎn)中關(guān)鍵字個數(shù)，(int)m/2<=n<m；di(1<=i<=n)為該結(jié)點(diǎn)的n個關(guān)鍵字值的第i個，且di<d(i+1)；ci(0<=i<=n)為該結(jié)點(diǎn)孩子結(jié)點(diǎn)的指針，且ci所指向的節(jié)點(diǎn)的關(guān)鍵字均大于或等于di且小于d(i+1)；

所有的葉結(jié)點(diǎn)都在同一層上。

所以B-Tree索引具有最左匹配特性（即從左往右匹配原則）。

二、 Hash索引：

Hash 索引結(jié)構(gòu)的特殊性，其檢索效率非常高，索引的檢索可以一次定位，不像B-Tree 索引需要從根節(jié)點(diǎn)到枝節(jié)點(diǎn)，最后才能訪問到頁節(jié)點(diǎn)這樣多次的IO訪問，所以 Hash 索引的查詢效率要遠(yuǎn)高于 B-Tree 索引。

可能很多人又有疑問了，既然 Hash 索引的效率要比 B-Tree 高很多，為什么大家不都用 Hash 索引而還要使用 B-Tree 索引呢？任何事物都是有兩面性的，Hash 索引也一樣，雖然 Hash 索引效率高，但是 Hash 索引本身由于其特殊性也帶來了很多限制和弊端，主要有以下這些：

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

由于 Hash 索引比較的是進(jìn)行 Hash 運(yùn)算之后的 Hash 值，所以它只能用于等值的過濾，不能用于基于范圍的過濾，因?yàn)榻?jīng)過相應(yīng)的 Hash 算法處理之后的 Hash 值的大小關(guān)系，并不能保證和Hash運(yùn)算前完全一樣。

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

由于 Hash 索引中存放的是經(jīng)過 Hash 計(jì)算之后的 Hash 值，而且Hash值的大小關(guān)系并不一定和 Hash 運(yùn)算前的鍵值完全一樣，所以數(shù)據(jù)庫無法利用索引的數(shù)據(jù)來避免任何排序運(yùn)算；

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

對于組合索引，Hash 索引在計(jì)算 Hash 值的時候是組合索引鍵合并后再一起計(jì)算 Hash 值，而不是單獨(dú)計(jì)算 Hash 值，所以通過組合索引的前面一個或幾個索引鍵進(jìn)行查詢的時候，Hash 索引也無法被利用。

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

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

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

對于選擇性比較低的索引鍵，如果創(chuàng)建 Hash 索引，那么將會存在大量記錄指針信息存于同一個 Hash 值相關(guān)聯(lián)。這樣要定位某一條記錄時就會非常麻煩，會浪費(fèi)多次表數(shù)據(jù)的訪問，而造成整體性能低下。

實(shí)現(xiàn)原理：

哈希索引是基于哈希表實(shí)現(xiàn)的。只有精確匹配索引所有列的的查詢才有效。他的實(shí)現(xiàn)是存儲殷勤會對每一行數(shù)據(jù)的索引列計(jì)算哈希碼，并將哈希碼和指向該記錄的指針維護(hù)起來，對于hash相同的，采用鏈表的方式解決沖突。類似于hashmap。因?yàn)樗饕慕Y(jié)構(gòu)是十分緊湊的，所以hash索引的查詢很快。如此其實(shí)我們就很容易的理解hash索引的優(yōu)缺點(diǎn)了：

1，hash索引只包含了哈希值和行指針，索引不能避免讀取行，不能使用覆蓋索引。

2，hash索引并不是按照索引順序存儲的，無法用于排序。

3，hash索引不支持部分或者區(qū)域查找，部分列的hash結(jié)果是不同的。

在Mysql中InnoDB引擎有一個特殊的功能叫做自適應(yīng)哈希索引，他會在內(nèi)存中基于B-Tree索引的基礎(chǔ)上面創(chuàng)建一個哈希索引，這讓B-Tree索引頁具備了一些哈希索引的優(yōu)點(diǎn)。