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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

廣告

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