引言：

B+樹索引：通過根節點到葉節點逐層尋找，一步一縮小尋找的范圍對象，直至找到目標

Hash索引：采用一定的哈希算法，把鍵值更換成新的哈希值，檢索時不需要像B+樹那樣依次從根節點到葉節點逐層尋找，一次性可以鎖定相應的位置，找到目標值。

一、“獨具特色”的B+樹

B+樹即Btree，它的樹形結構如同一棵樹木，但是倒立的樹木。所以我們稱之為B+樹索引。它的尋找目標值方式依次由根節點到葉節點。

即就是：B+樹左右支點都是相同數目的，所以稱之為平衡的多叉樹，如果分為兩個分叉則被稱為平衡的二叉樹，即以下邊樹木為例，以中間軀干為中點，左右對稱。由根到支點高度為1，任何節點的兩個子樹的高度為1，即由根到葉節點需要一層指向一層。各個節點之間用指針進行連接。根與葉子之間相連接的軀干被稱之為指針。

[[261140]]

以上兩幅對比可以看出，B+樹索引就像一棵倒立的樹木，樹根我們稱之為根節點在上方，葉子我們稱之為葉節點在下方。根節點連接的左右葉節點是對稱的，所以稱之為平衡的多叉樹。跟與葉子之間的箭頭叫做指針，從左邊節點分析，可在第一層尋找數值應該在[15,20]之間，在第二層又進行細分，數值在[15,18]之間，以此類推找到目標值。可以看出B+樹索引是通過范圍來尋找目標值的。

B+樹索引的應用場景和不適用場景：

• 適用于數據庫，文件系統等場景，因為這些對象都是層層包含的，文件里包含其他文件，需要逐層縮小范圍來尋找。
• 支持左右查詢，利用的是B+樹葉節點的指針是雙向的
• 不適用于等值查詢

二、“情有獨鐘”的哈希索引

哈希索引：哈希索引使用的是哈希算法，這里的算法指的是使用一定的函數，即通過尋找鍵值，來找到所尋找的對象。

哈希算法即散列函數，它就是將明文翻譯成一段固定長度的字符串密碼，且是單向的。因此采用哈希算法無論你之前明文有多長，經過算法輸出后都是固定長度的字符串密碼。代表算法有MD5,MD4…..

舉個例子：比如說我們在百度上想要搜 佩奇的圖片，當沒有任何外在的標識情況下，在巨量的圖片庫里你想要找到佩奇的圖片，你覺得是不是很困難。在這種情況下，我們可以通過哈希索引，它會將圖片庫里的圖片轉化成一串0-1的編碼。這樣你就會發現，圖片相近編碼也會變得很相近。這樣我們在百度里一輸入“佩奇”這樣的編碼，就會出來許多張佩奇的圖片。這就是所謂的哈希索引。

優點：效率高，可以一次就直接找到目標

哈希索引示意圖：

上圖說明：當我們在百度中輸入“佩奇”作為鍵值，然后所謂的Hash索引就會在圖片庫中找到標識符也為“佩奇”的編碼，然后就可以搜索出佩奇的圖片了。所以它不屬于范圍搜索。

哈希索引的應用場景和不適合場景：

• 支持等值查詢：前提條件沒有過多重復的鍵值，如果存在的話，會降低哈希索引的效率，發生哈希碰撞問題。
• 范圍查詢則不合適哈希索引
• 哈希索引不能被用來避免數據排序操作
• 哈希索引不支持最左匹配規則，因為鍵值更換成哈希值是單向的

三、各顯神通的B+與哈希

根據上面兩種索引的示意圖可以得出以下的不同結論：

• Hash索引的效率要高于B+樹索引。B+ 樹是一個平衡的多叉樹，所以從根節點到葉子節點的搜索效率是差不多的，基本不會出現波動，也可以進行順序掃描，即利用B+樹的雙向指針可以左右移動，雙反方向的查找，效率很高。 Hash 索引，根據鍵值作為“字符串”，可以一次性的檢索到位。不需要像B+樹索引一樣，由根節點到葉節點一層一層的尋找，所以，Hash 索引的檢索效率要高于B+索引。
• 等值查找Hash占優勢，一定范為內B+樹索引占優勢。由于Hash索引是通過鍵值來查找的，需要鍵值相等才能夠找到所需要的值。不能用于基于某一個范圍內的查找，而B+樹索引可以實現范圍內查找。因此在等鍵值查找出，Hash 索引優勢明顯; 在某一范圍內查找，B+樹索引優勢明顯。
• B+樹效率較均等化，Hash索引發生碰觸情況下效率大減。B+樹索引由于是(左右)平衡的多叉樹，所以在索引過程中效率畢竟均等化，不會出現幅度的大起大落。 而Hash索引，在有大量重復的鍵值情況下，效率都會很低，因為那么多相同的鍵值，都會索引，它也不能分清哪個鍵值背后的存儲對象是它所要找的目標，索引就會發生哈希碰撞問題。
• B+樹索引更適合數據庫的模糊查詢。對于像數據庫中 select * from [user] where name like’%三%’，查找名字帶三的模糊查詢，Hash 是無法完成的， 模糊查詢本質上也屬于范圍索引，故在此種情況下，應該使用B+ 樹索引。