面試官問(wèn)你B樹(shù)和B+樹(shù)，就把這篇文章丟給他-創(chuàng)新互聯(lián)

原文鏈接：面試官問(wèn)你B樹(shù)和B+樹(shù)，就把這篇文章丟給他

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

1 B樹(shù)

在介紹B+樹(shù)之前， 先簡(jiǎn)單的介紹一下B樹(shù)，這兩種數(shù)據(jù)結(jié)構(gòu)既有相似之處，也有他們的區(qū)別，最后，我們也會(huì)對(duì)比一下這兩種數(shù)據(jù)結(jié)構(gòu)的區(qū)別。

1.1 B樹(shù)概念

B樹(shù)也稱(chēng)B-樹(shù),它是一顆多路平衡查找樹(shù)。二叉樹(shù)我想大家都不陌生，其實(shí)，B樹(shù)和后面講到的B+樹(shù)也是從最簡(jiǎn)單的二叉樹(shù)變換而來(lái)的，并沒(méi)有什么神秘的地方，下面我們來(lái)看看B樹(shù)的定義。

• 每個(gè)節(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字（可以存有的鍵值對(duì)）。

• 根節(jié)點(diǎn)最少可以只有1個(gè)關(guān)鍵字。

• 非根節(jié)點(diǎn)至少有m/2個(gè)關(guān)鍵字。

• 每個(gè)節(jié)點(diǎn)中的關(guān)鍵字都按照從小到大的順序排列，每個(gè)關(guān)鍵字的左子樹(shù)中的所有關(guān)鍵字都小于它，而右子樹(shù)中的所有關(guān)鍵字都大于它。

• 所有葉子節(jié)點(diǎn)都位于同一層，或者說(shuō)根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)的長(zhǎng)度都相同。
• 每個(gè)節(jié)點(diǎn)都存有索引和數(shù)據(jù)，也就是對(duì)應(yīng)的key和value。

所以，根節(jié)點(diǎn)的關(guān)鍵字數(shù)量范圍：1 <= k <= m-1，非根節(jié)點(diǎn)的關(guān)鍵字數(shù)量范圍：m/2 <= k <= m-1。

另外，我們需要注意一個(gè)概念，描述一顆B樹(shù)時(shí)需要指定它的階數(shù)，階數(shù)表示了一個(gè)節(jié)點(diǎn)最多有多少個(gè)孩子節(jié)點(diǎn)，一般用字母m表示階數(shù)。

我們?cè)倥e個(gè)例子來(lái)說(shuō)明一下上面的概念，比如這里有一個(gè)5階的B樹(shù)，根節(jié)點(diǎn)數(shù)量范圍：1 <= k <= 4，非根節(jié)點(diǎn)數(shù)量范圍：2 <= k <= 4。

下面，我們通過(guò)一個(gè)插入的例子，講解一下B樹(shù)的插入過(guò)程，接著，再講解一下刪除關(guān)鍵字的過(guò)程。

1.2 B樹(shù)插入

插入的時(shí)候，我們需要記住一個(gè)規(guī)則：判斷當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)是否小于等于m-1，如果滿(mǎn)足，直接插入即可，如果不滿(mǎn)足，將節(jié)點(diǎn)的中間的key將這個(gè)節(jié)點(diǎn)分為左右兩部分，中間的節(jié)點(diǎn)放到父節(jié)點(diǎn)中即可。

例子：在5階B樹(shù)中，結(jié)點(diǎn)最多有4個(gè)key,最少有2個(gè)key（注意：下面的節(jié)點(diǎn)統(tǒng)一用一個(gè)節(jié)點(diǎn)表示key和value）。

• 插入18，70，50,40

• 插入22

插入22時(shí)，發(fā)現(xiàn)這個(gè)節(jié)點(diǎn)的關(guān)鍵字已經(jīng)大于4了，所以需要進(jìn)行分裂，分裂的規(guī)則在上面已經(jīng)講了，分裂之后，如下。

• 接著插入23，25，39

分裂，得到下面的。

更過(guò)的插入的過(guò)程就不多介紹了，相信有這個(gè)例子你已經(jīng)知道怎么進(jìn)行插入操作了。

1.3 B樹(shù)的刪除操作

B樹(shù)的刪除操作相對(duì)于插入操作是相對(duì)復(fù)雜一些的，但是，你知道記住幾種情況，一樣可以很輕松的掌握的。

• 現(xiàn)在有一個(gè)初始狀態(tài)是下面這樣的B樹(shù)，然后進(jìn)行刪除操作。

• 刪除15，這種情況是刪除葉子節(jié)點(diǎn)的元素，如果刪除之后，節(jié)點(diǎn)數(shù)還是大于m/2，這種情況只要直接刪除即可。

• 接著，我們把22刪除，這種情況的規(guī)則：22是非葉子節(jié)點(diǎn)，對(duì)于非葉子節(jié)點(diǎn)的刪除，我們需要用后繼key（元素）覆蓋要?jiǎng)h除的key，然后在后繼key所在的子支中刪除該后繼key。對(duì)于刪除22，需要將后繼元素24移到被刪除的22所在的節(jié)點(diǎn)。

此時(shí)發(fā)現(xiàn)26所在的節(jié)點(diǎn)只有一個(gè)元素，小于2個(gè)（m/2），這個(gè)節(jié)點(diǎn)不符合要求，這時(shí)候的規(guī)則（向兄弟節(jié)點(diǎn)借元素）：如果刪除葉子節(jié)點(diǎn)，如果刪除元素后元素個(gè)數(shù)少于（m/2），并且它的兄弟節(jié)點(diǎn)的元素大于（m/2），也就是說(shuō)兄弟節(jié)點(diǎn)的元素比最少值m/2還多，將先將父節(jié)點(diǎn)的元素移到該節(jié)點(diǎn)，然后將兄弟節(jié)點(diǎn)的元素再移動(dòng)到父節(jié)點(diǎn)。這樣就滿(mǎn)足要求了。

我們看看操作過(guò)程就更加明白了。

• 接著刪除28，刪除葉子節(jié)點(diǎn)，刪除后不滿(mǎn)足要求，所以，我們需要考慮向兄弟節(jié)點(diǎn)借元素，但是，兄弟節(jié)點(diǎn)也沒(méi)有多的節(jié)點(diǎn)（2個(gè)），借不了，怎么辦呢？如果遇到這種情況，首先，還是將先將父節(jié)點(diǎn)的元素移到該節(jié)點(diǎn)，然后，將當(dāng)前節(jié)點(diǎn)及它的兄弟節(jié)點(diǎn)中的key合并，形成一個(gè)新的節(jié)點(diǎn)。

移動(dòng)之后，跟兄弟節(jié)點(diǎn)合并。

刪除就只有上面的幾種情況，根據(jù)不同的情況進(jìn)行刪除即可。

上面的這些介紹，相信對(duì)于B樹(shù)已經(jīng)有一定的了解了，接下來(lái)的一部分，我們接著講解B+樹(shù)，我相信加上B+樹(shù)的對(duì)比，就更加清晰明了了。

2 B+樹(shù)

2.1 B+樹(shù)概述

B+樹(shù)其實(shí)和B樹(shù)是非常相似的，我們首先看看相同點(diǎn)。

• 根節(jié)點(diǎn)至少一個(gè)元素
• 非根節(jié)點(diǎn)元素范圍：m/2 <= k <= m-1

不同點(diǎn)。

• B+樹(shù)有兩種類(lèi)型的節(jié)點(diǎn)：內(nèi)部結(jié)點(diǎn)（也稱(chēng)索引結(jié)點(diǎn)）和葉子結(jié)點(diǎn)。內(nèi)部節(jié)點(diǎn)就是非葉子節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)不存儲(chǔ)數(shù)據(jù)，只存儲(chǔ)索引，數(shù)據(jù)都存儲(chǔ)在葉子節(jié)點(diǎn)。
• 內(nèi)部結(jié)點(diǎn)中的key都按照從小到大的順序排列，對(duì)于內(nèi)部結(jié)點(diǎn)中的一個(gè)key，左樹(shù)中的所有key都小于它，右子樹(shù)中的key都大于等于它。葉子結(jié)點(diǎn)中的記錄也按照key的大小排列。
• 每個(gè)葉子結(jié)點(diǎn)都存有相鄰葉子結(jié)點(diǎn)的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。
• 父節(jié)點(diǎn)存有右孩子的第一個(gè)元素的索引。

下面我們看一個(gè)B+樹(shù)的例子，感受感受它吧！

2.2 插入操作

對(duì)于插入操作很簡(jiǎn)單，只需要記住一個(gè)技巧即可：當(dāng)節(jié)點(diǎn)元素?cái)?shù)量大于m-1的時(shí)候，按中間元素分裂成左右兩部分，中間元素分裂到父節(jié)點(diǎn)當(dāng)做索引存儲(chǔ)，但是，本身中間元素還是分裂右邊這一部分的。

下面以一顆5階B+樹(shù)的插入過(guò)程為例，5階B+樹(shù)的節(jié)點(diǎn)最少2個(gè)元素，最多4個(gè)元素。

• 插入5，10，15，20

• 插入25，此時(shí)元素?cái)?shù)量大于4個(gè)了，分裂

• 接著插入26，30，繼續(xù)分裂

有了這幾個(gè)例子，相信插入操作沒(méi)什么問(wèn)題了，下面接著看看刪除操作。

2.3 刪除操作

對(duì)于刪除操作是比B樹(shù)簡(jiǎn)單一些的，因?yàn)?strong>葉子節(jié)點(diǎn)有指針的存在，向兄弟節(jié)點(diǎn)借元素時(shí)，不需要通過(guò)父節(jié)點(diǎn)了，而是可以直接通過(guò)兄弟節(jié)移動(dòng)即可（前提是兄弟節(jié)點(diǎn)的元素大于m/2），然后更新父節(jié)點(diǎn)的索引；如果兄弟節(jié)點(diǎn)的元素不大于m/2（兄弟節(jié)點(diǎn)也沒(méi)有多余的元素），則將當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)合并，并且刪除父節(jié)點(diǎn)中的key，下面我們看看具體的實(shí)例。

• 初始狀態(tài)

• 刪除10，刪除后，不滿(mǎn)足要求，發(fā)現(xiàn)左邊兄弟節(jié)點(diǎn)有多余的元素，所以去借元素，最后，修改父節(jié)點(diǎn)索引

• 刪除元素5，發(fā)現(xiàn)不滿(mǎn)足要求，并且發(fā)現(xiàn)左右兄弟節(jié)點(diǎn)都沒(méi)有多余的元素，所以，可以選擇和兄弟節(jié)點(diǎn)合并，最后修改父節(jié)點(diǎn)索引

• 發(fā)現(xiàn)父節(jié)點(diǎn)索引也不滿(mǎn)足條件，所以，需要做跟上面一步一樣的操作

這樣，B+樹(shù)的刪除操作也就完成了，是不是看完之后，覺(jué)得非常簡(jiǎn)單！

3 B樹(shù)和B+樹(shù)總結(jié)

B+樹(shù)相對(duì)于B樹(shù)有一些自己的優(yōu)勢(shì)，可以歸結(jié)為下面幾點(diǎn)。

• 單一節(jié)點(diǎn)存儲(chǔ)的元素更多，使得查詢(xún)的IO次數(shù)更少，所以也就使得它更適合做為數(shù)據(jù)庫(kù)MySQL的底層數(shù)據(jù)結(jié)構(gòu)了。
• 所有的查詢(xún)都要查找到葉子節(jié)點(diǎn)，查詢(xún)性能是穩(wěn)定的，而B(niǎo)樹(shù)，每個(gè)節(jié)點(diǎn)都可以查找到數(shù)據(jù)，所以不穩(wěn)定。
• 所有的葉子節(jié)點(diǎn)形成了一個(gè)有序鏈表，更加便于查找。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線(xiàn)，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。

新聞名稱(chēng)：面試官問(wèn)你B樹(shù)和B+樹(shù)，就把這篇文章丟給他-創(chuàng)新互聯(lián)
本文網(wǎng)址：http://www.muchs.cn/article20/pcico.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、品牌網(wǎng)站制作、網(wǎng)站改版、自適應(yīng)網(wǎng)站、動(dòng)態(tài)網(wǎng)站、企業(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)