本篇內(nèi)容介紹了“MySQL B+樹和B樹的特點(diǎn)區(qū)別”的有關(guān)知識(shí)，在實(shí)際案例的操作過程中，不少人都會(huì)遇到這樣的困境，接下來就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

成都創(chuàng)新互聯(lián)-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比庫車網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式庫車網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋庫車地區(qū)。費(fèi)用合理售后完善，十余年實(shí)體公司更值得信賴。

B樹是一種多路自平衡搜索樹，它類似普通的二叉樹，但是B書允許每個(gè)節(jié)點(diǎn)有更多的子節(jié)點(diǎn)。

B樹的特點(diǎn)：
（1）所有鍵值分布在整個(gè)樹中
（2）任何關(guān)鍵字出現(xiàn)且只出現(xiàn)在一個(gè)節(jié)點(diǎn)中
（3）搜索有可能在非葉子節(jié)點(diǎn)結(jié)束
（4）在關(guān)鍵字全集內(nèi)做一次查找，性能逼近二分查找算法

B+樹是B樹的變體，也是一種多路平衡查找樹。

從圖中也可以看到，B+樹與B樹的不同在于：
（1）所有關(guān)鍵字存儲(chǔ)在葉子節(jié)點(diǎn)，非葉子節(jié)點(diǎn)不存儲(chǔ)真正的data
（2）為所有葉子節(jié)點(diǎn)增加了一個(gè)鏈指針

那么問題來了，為什么用B/B+樹這種結(jié)構(gòu)來實(shí)現(xiàn)索引呢？？
答：紅黑樹等結(jié)構(gòu)也可以用來實(shí)現(xiàn)索引，但是文件系統(tǒng)及數(shù)據(jù)庫系統(tǒng)普遍使用B/B+樹結(jié)構(gòu)來實(shí)現(xiàn)索引。mysql是基于磁盤的數(shù)據(jù)庫，索引是以索引文件的形式存在于磁盤中的，索引的查找過程就會(huì)涉及到磁盤IO(為什么涉及到磁盤IO請(qǐng)看文章后面的附加理解部分)消耗，磁盤IO的消耗相比較于內(nèi)存IO的消耗要高好幾個(gè)數(shù)量級(jí)，所以索引的組織結(jié)構(gòu)要設(shè)計(jì)得在查找關(guān)鍵字時(shí)要盡量減少磁盤IO的次數(shù)。為什么要使用B/B+樹，跟磁盤的存儲(chǔ)原理有關(guān)。
局部性原理與磁盤預(yù)讀
為了提升效率，要盡量減少磁盤IO的次數(shù)。實(shí)際過程中，磁盤并不是每次嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀。磁盤讀取完需要的數(shù)據(jù)后，會(huì)按順序再多讀一部分?jǐn)?shù)據(jù)到內(nèi)存中，這樣做的理論依據(jù)是計(jì)算機(jī)科學(xué)中注明的局部性原理：

 

當(dāng)一個(gè)數(shù)據(jù)被用到時(shí)，其附近的數(shù)據(jù)也通常會(huì)馬上被使用
程序運(yùn)行期間所需要的數(shù)據(jù)通常比較集中

（1）由于磁盤順序讀取的效率很高(不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間)，
因此對(duì)于具有局部性的程序來說，預(yù)讀可以提高I/O效率.預(yù)讀的長(zhǎng)度一般為頁(page)的整倍數(shù)。
（2）MySQL(默認(rèn)使用InnoDB引擎),將記錄按照頁的方式進(jìn)行管理,每頁大小默認(rèn)為16K(這個(gè)值可以修改)。linux 默認(rèn)頁大小為4K。

B-Tree借助計(jì)算機(jī)磁盤預(yù)讀的機(jī)制，并使用如下技巧：
每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁對(duì)齊的，就實(shí)現(xiàn)了一個(gè)結(jié)點(diǎn)只需一次I/O。
假設(shè) B-Tree 的高度為 h,B-Tree中一次檢索最多需要h-1次I/O（根節(jié)點(diǎn)常駐內(nèi)存），漸進(jìn)復(fù)雜度為O(h)=O(logdN)O(h)=O(logdN)。一般實(shí)際應(yīng)用中，出度d是非常大的數(shù)字，通常超過100，因此h非常小（通常不超過3，也即索引的B+樹層次一般不超過三層，所以查找效率很高）。
而紅黑樹這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無法利用局部性，所以紅黑樹的I/O漸進(jìn)復(fù)雜度也為O(h)，效率明顯比B-Tree差很多。

為什么mysql的索引使用B+樹而不是B樹呢？？
（1）B+樹更適合外部存儲(chǔ)(一般指磁盤存儲(chǔ)),由于內(nèi)節(jié)點(diǎn)(非葉子節(jié)點(diǎn))不存儲(chǔ)data，所以一個(gè)節(jié)點(diǎn)可以存儲(chǔ)更多的內(nèi)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)能索引的范圍更大更精確。也就是說使用B+樹單次磁盤IO的信息量相比較B樹更大，IO效率更高。
（2）mysql是關(guān)系型數(shù)據(jù)庫，經(jīng)常會(huì)按照區(qū)間來訪問某個(gè)索引列，B+樹的葉子節(jié)點(diǎn)間按順序建立了鏈指針，加強(qiáng)了區(qū)間訪問性，所以B+樹對(duì)索引列上的區(qū)間范圍查詢很友好。而B樹每個(gè)節(jié)點(diǎn)的key和data在一起，無法進(jìn)行區(qū)間查找。

“MYSQL B+樹和B樹的特點(diǎn)區(qū)別”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！

分享題目：MYSQLB+樹和B樹的特點(diǎn)區(qū)別
本文路徑：http://jinyejixie.com/article32/ppposc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、營(yíng)銷型網(wǎng)站建設(shè)、關(guān)鍵詞優(yōu)化、網(wǎng)站制作、服務(wù)器托管、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)