MYSQLB+樹(shù)和B樹(shù)的特點(diǎn)區(qū)別

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

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

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

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

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

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

那么問(wèn)題來(lái)了，為什么用B/B+樹(shù)這種結(jié)構(gòu)來(lái)實(shí)現(xiàn)索引呢？？
答：紅黑樹(shù)等結(jié)構(gòu)也可以用來(lái)實(shí)現(xiàn)索引，但是文件系統(tǒng)及數(shù)據(jù)庫(kù)系統(tǒng)普遍使用B/B+樹(shù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)索引。mysql是基于磁盤(pán)的數(shù)據(jù)庫(kù)，索引是以索引文件的形式存在于磁盤(pán)中的，索引的查找過(guò)程就會(huì)涉及到磁盤(pán)IO(為什么涉及到磁盤(pán)IO請(qǐng)看文章后面的附加理解部分)消耗，磁盤(pán)IO的消耗相比較于內(nèi)存IO的消耗要高好幾個(gè)數(shù)量級(jí)，所以索引的組織結(jié)構(gòu)要設(shè)計(jì)得在查找關(guān)鍵字時(shí)要盡量減少磁盤(pán)IO的次數(shù)。為什么要使用B/B+樹(shù)，跟磁盤(pán)的存儲(chǔ)原理有關(guān)。
局部性原理與磁盤(pán)預(yù)讀
為了提升效率，要盡量減少磁盤(pán)IO的次數(shù)。實(shí)際過(guò)程中，磁盤(pán)并不是每次嚴(yán)格按需讀取，而是每次都會(huì)預(yù)讀。磁盤(pán)讀取完需要的數(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）由于磁盤(pán)順序讀取的效率很高(不需要尋道時(shí)間，只需很少的旋轉(zhuǎn)時(shí)間)，
因此對(duì)于具有局部性的程序來(lái)說(shuō)，預(yù)讀可以提高I/O效率.預(yù)讀的長(zhǎng)度一般為頁(yè)(page)的整倍數(shù)。
（2）MySQL(默認(rèn)使用InnoDB引擎),將記錄按照頁(yè)的方式進(jìn)行管理,每頁(yè)大小默認(rèn)為16K(這個(gè)值可以修改)。linux 默認(rèn)頁(yè)大小為4K。

B-Tree借助計(jì)算機(jī)磁盤(pán)預(yù)讀的機(jī)制，并使用如下技巧：
每次新建節(jié)點(diǎn)時(shí)，直接申請(qǐng)一個(gè)頁(yè)的空間，這樣就保證一個(gè)節(jié)點(diǎn)物理上也存儲(chǔ)在一個(gè)頁(yè)里，加之計(jì)算機(jī)存儲(chǔ)分配都是按頁(yè)對(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ù)字，通常超過(guò)100，因此h非常?。ㄍǔ２怀^(guò)3，也即索引的B+樹(shù)層次一般不超過(guò)三層，所以查找效率很高）。
而紅黑樹(shù)這種結(jié)構(gòu)，h明顯要深的多。由于邏輯上很近的節(jié)點(diǎn)（父子）物理上可能很遠(yuǎn)，無(wú)法利用局部性，所以紅黑樹(shù)的I/O漸進(jìn)復(fù)雜度也為O(h)，效率明顯比B-Tree差很多。

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

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

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

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

廣告

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