建站
咨詢
售后
建站咨詢
新聞中心
引言：
創(chuàng)新互聯(lián)專注于嘉定網(wǎng)站建設(shè)服務(wù)及定制，我們擁有豐富的企業(yè)做網(wǎng)站經(jīng)驗(yàn)。 熱誠(chéng)為您提供嘉定營(yíng)銷型網(wǎng)站建設(shè)，嘉定網(wǎng)站制作、嘉定網(wǎng)頁(yè)設(shè)計(jì)、嘉定網(wǎng)站官網(wǎng)定制、微信小程序服務(wù)，打造嘉定網(wǎng)絡(luò)公司原創(chuàng)品牌,更為您提供嘉定網(wǎng)站排名全網(wǎng)營(yíng)銷落地服務(wù)。
B+樹索引：通過(guò)根節(jié)點(diǎn)到葉節(jié)點(diǎn)逐層尋找，一步一縮小尋找的范圍對(duì)象，直至找到目標(biāo)
Hash索引：采用一定的哈希算法，把鍵值更換成新的哈希值，檢索時(shí)不需要像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ù)目的，所以稱之為平衡的多叉樹，如果分為兩個(gè)分叉則被稱為平衡的二叉樹，即以下邊樹木為例，以中間軀干為中點(diǎn)，左右對(duì)稱。由根到支點(diǎn)高度為1，任何節(jié)點(diǎn)的兩個(gè)子樹的高度為1，即由根到葉節(jié)點(diǎn)需要一層指向一層。各個(gè)節(jié)點(diǎn)之間用指針進(jìn)行連接。根與葉子之間相連接的軀干被稱之為指針。
以上兩幅對(duì)比可以看出，B+樹索引就像一棵倒立的樹木，樹根我們稱之為根節(jié)點(diǎn)在上方，葉子我們稱之為葉節(jié)點(diǎn)在下方。根節(jié)點(diǎn)連接的左右葉節(jié)點(diǎn)是對(duì)稱的，所以稱之為平衡的多叉樹。跟與葉子之間的箭頭叫做指針，從左邊節(jié)點(diǎn)分析，可在第一層尋找數(shù)值應(yīng)該在[15,20]之間，在第二層又進(jìn)行細(xì)分，數(shù)值在[15,18]之間，以此類推找到目標(biāo)值?？梢钥闯鯞+樹索引是通過(guò)范圍來(lái)尋找目標(biāo)值的。
B+樹索引的應(yīng)用場(chǎng)景和不適用場(chǎng)景：
- 適用于數(shù)據(jù)庫(kù)，文件系統(tǒng)等場(chǎng)景，因?yàn)檫@些對(duì)象都是層層包含的，文件里包含其他文件，需要逐層縮小范圍來(lái)尋找。
- 支持左右查詢，利用的是B+樹葉節(jié)點(diǎn)的指針是雙向的
- 不適用于等值查詢
二、“情有獨(dú)鐘”的哈希索引
哈希索引：哈希索引使用的是哈希算法，這里的算法指的是使用一定的函數(shù)，即通過(guò)尋找鍵值，來(lái)找到所尋找的對(duì)象。
哈希算法即散列函數(shù)，它就是將明文翻譯成一段固定長(zhǎng)度的字符串密碼，且是單向的。因此采用哈希算法無(wú)論你之前明文有多長(zhǎng)，經(jīng)過(guò)算法輸出后都是固定長(zhǎng)度的字符串密碼。代表算法有MD5,MD4…..
舉個(gè)例子：比如說(shuō)我們?cè)诎俣壬舷胍?佩奇的圖片，當(dāng)沒(méi)有任何外在的標(biāo)識(shí)情況下，在巨量的圖片庫(kù)里你想要找到佩奇的圖片，你覺得是不是很困難。在這種情況下，我們可以通過(guò)哈希索引，它會(huì)將圖片庫(kù)里的圖片轉(zhuǎn)化成一串0-1的編碼。這樣你就會(huì)發(fā)現(xiàn)，圖片相近編碼也會(huì)變得很相近。這樣我們?cè)诎俣壤镆惠斎搿芭迤妗边@樣的編碼，就會(huì)出來(lái)許多張佩奇的圖片。這就是所謂的哈希索引。
優(yōu)點(diǎn)：效率高，可以一次就直接找到目標(biāo)
哈希索引示意圖：
上圖說(shuō)明：當(dāng)我們?cè)诎俣戎休斎搿芭迤妗弊鳛殒I值，然后所謂的Hash索引就會(huì)在圖片庫(kù)中找到標(biāo)識(shí)符也為“佩奇”的編碼，然后就可以搜索出佩奇的圖片了。所以它不屬于范圍搜索。
哈希索引的應(yīng)用場(chǎng)景和不適合場(chǎng)景：
- 支持等值查詢：前提條件沒(méi)有過(guò)多重復(fù)的鍵值，如果存在的話，會(huì)降低哈希索引的效率，發(fā)生哈希碰撞問(wèn)題。
- 范圍查詢則不合適哈希索引
- 哈希索引不能被用來(lái)避免數(shù)據(jù)排序操作
- 哈希索引不支持最左匹配規(guī)則，因?yàn)殒I值更換成哈希值是單向的
三、各顯神通的B+與哈希
根據(jù)上面兩種索引的示意圖可以得出以下的不同結(jié)論：
- Hash索引的效率要高于B+樹索引。B+ 樹是一個(gè)平衡的多叉樹，所以從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的搜索效率是差不多的，基本不會(huì)出現(xiàn)波動(dòng)，也可以進(jìn)行順序掃描，即利用B+樹的雙向指針可以左右移動(dòng)，雙反方向的查找，效率很高。 Hash 索引，根據(jù)鍵值作為“字符串”，可以一次性的檢索到位。不需要像B+樹索引一樣，由根節(jié)點(diǎn)到葉節(jié)點(diǎn)一層一層的尋找，所以，Hash 索引的檢索效率要高于B+索引。
- 等值查找Hash占優(yōu)勢(shì)，一定范為內(nèi)B+樹索引占優(yōu)勢(shì)。由于Hash索引是通過(guò)鍵值來(lái)查找的，需要鍵值相等才能夠找到所需要的值。不能用于基于某一個(gè)范圍內(nèi)的查找，而B+樹索引可以實(shí)現(xiàn)范圍內(nèi)查找。因此在等鍵值查找出，Hash 索引優(yōu)勢(shì)明顯; 在某一范圍內(nèi)查找，B+樹索引優(yōu)勢(shì)明顯。
- B+樹效率較均等化，Hash索引發(fā)生碰觸情況下效率大減。B+樹索引由于是(左右)平衡的多叉樹，所以在索引過(guò)程中效率畢竟均等化，不會(huì)出現(xiàn)幅度的大起大落。 而Hash索引，在有大量重復(fù)的鍵值情況下，效率都會(huì)很低，因?yàn)槟敲炊嘞嗤逆I值，都會(huì)索引，它也不能分清哪個(gè)鍵值背后的存儲(chǔ)對(duì)象是它所要找的目標(biāo)，索引就會(huì)發(fā)生哈希碰撞問(wèn)題。
- B+樹索引更適合數(shù)據(jù)庫(kù)的模糊查詢。對(duì)于像數(shù)據(jù)庫(kù)中 select * from [user] where name like’%三%’，查找名字帶三的模糊查詢，Hash 是無(wú)法完成的， 模糊查詢本質(zhì)上也屬于范圍索引，故在此種情況下，應(yīng)該使用B+ 樹索引。
本文標(biāo)題：3分鐘讓你記住B+樹索引和哈希索引的“愛恨情愁”
鏈接地址：http://www.dlmjj.cn/article/ccdiojj.html
