引言：

B+樹索引：通過根節(jié)點(diǎn)到葉節(jié)點(diǎn)逐層尋找，一步一縮小尋找的范圍對象，直至找到目標(biāo)

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

一、“獨(dú)具特色”的B+樹

B+樹即Btree，它的樹形結(jié)構(gòu)如同一棵樹木，但是倒立的樹木。所以我們稱之為B+樹索引。它的尋找目標(biāo)值方式依次由根節(jié)點(diǎn)到葉節(jié)點(diǎn)。

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

[[261140]]

以上兩幅對比可以看出，B+樹索引就像一棵倒立的樹木，樹根我們稱之為根節(jié)點(diǎn)在上方，葉子我們稱之為葉節(jié)點(diǎn)在下方。根節(jié)點(diǎn)連接的左右葉節(jié)點(diǎn)是對稱的，所以稱之為平衡的多叉樹。跟與葉子之間的箭頭叫做指針，從左邊節(jié)點(diǎn)分析，可在第一層尋找數(shù)值應(yīng)該在[15,20]之間，在第二層又進(jìn)行細(xì)分，數(shù)值在[15,18]之間，以此類推找到目標(biāo)值?？梢钥闯鯞+樹索引是通過范圍來尋找目標(biāo)值的。

B+樹索引的應(yīng)用場景和不適用場景：

• 適用于數(shù)據(jù)庫，文件系統(tǒng)等場景，因?yàn)檫@些對象都是層層包含的，文件里包含其他文件，需要逐層縮小范圍來尋找。
• 支持左右查詢，利用的是B+樹葉節(jié)點(diǎn)的指針是雙向的
• 不適用于等值查詢

二、“情有獨(dú)鐘”的哈希索引

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

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

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

優(yōu)點(diǎn)：效率高，可以一次就直接找到目標(biāo)

哈希索引示意圖：

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

哈希索引的應(yīng)用場景和不適合場景：

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

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

根據(jù)上面兩種索引的示意圖可以得出以下的不同結(jié)論：

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