?

簡(jiǎn)介：本文主要介紹了B樹(shù)和B 樹(shù)的插入、刪除操作。寫這篇博客的目的是發(fā)現(xiàn)沒(méi)有相關(guān)博客以舉例的方式詳細(xì)介紹B 樹(shù)的相關(guān)操作，由于自身對(duì)某些細(xì)節(jié)也感到很迷惑，通過(guò)查閱相關(guān)資料，對(duì)B 樹(shù)的操作有所頓悟，寫下這篇博客以做記錄。由于是自身對(duì)B 樹(shù)的理解，肯定有考慮不周的情況，或者理解錯(cuò)誤的地方，請(qǐng)留言指出。

?

1. B樹(shù)

1. B樹(shù)的定義

B樹(shù)也稱B-樹(shù),它是一顆多路平衡查找樹(shù)。我們描述一顆B樹(shù)時(shí)需要指定它的階數(shù)，階數(shù)表示了一個(gè)結(jié)點(diǎn)最多有多少個(gè)孩子結(jié)點(diǎn)，一般用字母m表示階數(shù)。當(dāng)m取2時(shí)，就是我們常見(jiàn)的二叉搜索樹(shù)。

一顆m階的B樹(shù)定義如下：

1）每個(gè)結(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字。

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

3）非根結(jié)點(diǎn)至少有Math.ceil(m/2)-1個(gè)關(guān)鍵字。

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

5）所有葉子結(jié)點(diǎn)都位于同一層，或者說(shuō)根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的長(zhǎng)度都相同。

上圖是一顆階數(shù)為4的B樹(shù)。在實(shí)際應(yīng)用中的B樹(shù)的階數(shù)m都非常大（通常大于100），所以即使存儲(chǔ)大量的數(shù)據(jù)，B樹(shù)的高度仍然比較小。每個(gè)結(jié)點(diǎn)中存儲(chǔ)了關(guān)鍵字（key）和關(guān)鍵字對(duì)應(yīng)的數(shù)據(jù)（data），以及孩子結(jié)點(diǎn)的指針。我們將一個(gè)key和其對(duì)應(yīng)的data稱為一個(gè)記錄。但為了方便描述，除非特別說(shuō)明，后續(xù)文中就用key來(lái)代替（key, value）鍵值對(duì)這個(gè)整體。在數(shù)據(jù)庫(kù)中我們將B樹(shù)（和B 樹(shù)）作為索引結(jié)構(gòu)，可以加快查詢速速，此時(shí)B樹(shù)中的key就表示鍵，而data表示了這個(gè)鍵對(duì)應(yīng)的條目在硬盤上的邏輯地址。

?

1.2 B樹(shù)的插入操作

插入操作是指插入一條記錄，即（key, value）的鍵值對(duì)。如果B樹(shù)中已存在需要插入的鍵值對(duì)，則用需要插入的value替換舊的value。若B樹(shù)不存在這個(gè)key,則一定是在葉子結(jié)點(diǎn)中進(jìn)行插入操作。

1）根據(jù)要插入的key的值，找到葉子結(jié)點(diǎn)并插入。

2）判斷當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)是否小于等于m-1，若滿足則結(jié)束，否則進(jìn)行第3步。

3）以結(jié)點(diǎn)中間的key為中心分裂成左右兩部分，然后將這個(gè)中間的key插入到父結(jié)點(diǎn)中，這個(gè)key的左子樹(shù)指向分裂后的左半部分，這個(gè)key的右子支指向分裂后的右半部分，然后將當(dāng)前結(jié)點(diǎn)指向父結(jié)點(diǎn)，繼續(xù)進(jìn)行第3步。

下面以5階B樹(shù)為例，介紹B樹(shù)的插入操作，在5階B樹(shù)中，結(jié)點(diǎn)最多有4個(gè)key,最少有2個(gè)key

a）在空樹(shù)中插入39

此時(shí)根結(jié)點(diǎn)就一個(gè)key，此時(shí)根結(jié)點(diǎn)也是葉子結(jié)點(diǎn)

b）繼續(xù)插入22，97和41

根結(jié)點(diǎn)此時(shí)有4個(gè)key

c）繼續(xù)插入53

插入后超過(guò)了最大允許的關(guān)鍵字個(gè)數(shù)4，所以以key值為41為中心進(jìn)行分裂，結(jié)果如下圖所示，分裂后當(dāng)前結(jié)點(diǎn)指針指向父結(jié)點(diǎn)，滿足B樹(shù)條件，插入操作結(jié)束。當(dāng)階數(shù)m為偶數(shù)時(shí)，需要分裂時(shí)就不存在排序恰好在中間的key，那么我們選擇中間位置的前一個(gè)key或中間位置的后一個(gè)key為中心進(jìn)行分裂即可。

d）依次插入13，21，40，同樣會(huì)造成分裂，結(jié)果如下圖所示。

e）依次插入30，27, 33 ；36，35，34 ；24，29，結(jié)果如下圖所示。

f）插入key值為26的記錄，插入后的結(jié)果如下圖所示。

當(dāng)前結(jié)點(diǎn)需要以27為中心分裂，并向父結(jié)點(diǎn)進(jìn)位27，然后當(dāng)前結(jié)點(diǎn)指向父結(jié)點(diǎn)，結(jié)果如下圖所示。

進(jìn)位后導(dǎo)致當(dāng)前結(jié)點(diǎn)（即根結(jié)點(diǎn)）也需要分裂，分裂的結(jié)果如下圖所示。

分裂后當(dāng)前結(jié)點(diǎn)指向新的根，此時(shí)無(wú)需調(diào)整。

g）最后再依次插入key為17,28,29,31,32的記錄，結(jié)果如下圖所示。

在實(shí)現(xiàn)B樹(shù)的代碼中，為了使代碼編寫更加容易，我們可以將結(jié)點(diǎn)中存儲(chǔ)記錄的數(shù)組長(zhǎng)度定義為m而非m-1，這樣方便底層的結(jié)點(diǎn)由于分裂向上層插入一個(gè)記錄時(shí)，上層有多余的位置存儲(chǔ)這個(gè)記錄。同時(shí)，每個(gè)結(jié)點(diǎn)還可以存儲(chǔ)它的父結(jié)點(diǎn)的引用，這樣就不必編寫遞歸程序。

一般來(lái)說(shuō)，對(duì)于確定的m和確定類型的記錄，結(jié)點(diǎn)大小是固定的，無(wú)論它實(shí)際存儲(chǔ)了多少個(gè)記錄。但是分配固定結(jié)點(diǎn)大小的方法會(huì)存在浪費(fèi)的情況，比如key為28,29所在的結(jié)點(diǎn)，還有2個(gè)key的位置沒(méi)有使用，但是已經(jīng)不可能繼續(xù)在插入任何值了，因?yàn)檫@個(gè)結(jié)點(diǎn)的前序key是27,后繼key是30,所有整數(shù)值都用完了。所以如果記錄先按key的大小排好序，再插入到B樹(shù)中，結(jié)點(diǎn)的使用率就會(huì)很低，最差情況下使用率僅為50%。

?

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

刪除操作是指，根據(jù)key刪除記錄，如果B樹(shù)中的記錄中不存對(duì)應(yīng)key的記錄，則刪除失敗。

1）如果當(dāng)前需要?jiǎng)h除的key位于非葉子結(jié)點(diǎn)上，則用后繼key（這里的后繼key均指后繼記錄的意思）覆蓋要?jiǎng)h除的key，然后在后繼key所在的子支中刪除該后繼key。此時(shí)后繼key一定位于葉子結(jié)點(diǎn)上，這個(gè)過(guò)程和二叉搜索樹(shù)刪除結(jié)點(diǎn)的方式類似。刪除這個(gè)記錄后執(zhí)行第2步

2）該結(jié)點(diǎn)key個(gè)數(shù)大于等于Math.ceil(m/2)-1，結(jié)束刪除操作，否則執(zhí)行第3步。

3）如果兄弟結(jié)點(diǎn)key個(gè)數(shù)大于Math.ceil(m/2)-1，則父結(jié)點(diǎn)中的key下移到該結(jié)點(diǎn)，兄弟結(jié)點(diǎn)中的一個(gè)key上移，刪除操作結(jié)束。

否則，將父結(jié)點(diǎn)中的key下移與當(dāng)前結(jié)點(diǎn)及它的兄弟結(jié)點(diǎn)中的key合并，形成一個(gè)新的結(jié)點(diǎn)。原父結(jié)點(diǎn)中的key的兩個(gè)孩子指針就變成了一個(gè)孩子指針，指向這個(gè)新結(jié)點(diǎn)。然后當(dāng)前結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)，重復(fù)上第2步。

有些結(jié)點(diǎn)它可能即有左兄弟，又有右兄弟，那么我們?nèi)我膺x擇一個(gè)兄弟結(jié)點(diǎn)進(jìn)行操作即可。

下面以5階B樹(shù)為例，介紹B樹(shù)的刪除操作，5階B樹(shù)中，結(jié)點(diǎn)最多有4個(gè)key,最少有2個(gè)key

a）原始狀態(tài)

b）在上面的B樹(shù)中刪除21，刪除后結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)仍然大于等2，所以刪除結(jié)束。

c）在上述情況下接著刪除27。從上圖可知27位于非葉子結(jié)點(diǎn)中，所以用27的后繼替換它。從圖中可以看出，27的后繼為28，我們用28替換27，然后在28（原27）的右孩子結(jié)點(diǎn)中刪除28。刪除后的結(jié)果如下圖所示。

刪除后發(fā)現(xiàn)，當(dāng)前葉子結(jié)點(diǎn)的記錄的個(gè)數(shù)小于2，而它的兄弟結(jié)點(diǎn)中有3個(gè)記錄（當(dāng)前結(jié)點(diǎn)還有一個(gè)右兄弟，選擇右兄弟就會(huì)出現(xiàn)合并結(jié)點(diǎn)的情況，不論選哪一個(gè)都行，只是最后B樹(shù)的形態(tài)會(huì)不一樣而已），我們可以從兄弟結(jié)點(diǎn)中借取一個(gè)key。所以父結(jié)點(diǎn)中的28下移，兄弟結(jié)點(diǎn)中的26上移,刪除結(jié)束。結(jié)果如下圖所示。

d）在上述情況下接著32，結(jié)果如下圖。

當(dāng)刪除后，當(dāng)前結(jié)點(diǎn)中只key，而兄弟結(jié)點(diǎn)中也僅有2個(gè)key。所以只能讓父結(jié)點(diǎn)中的30下移和這個(gè)兩個(gè)孩子結(jié)點(diǎn)中的key合并，成為一個(gè)新的結(jié)點(diǎn)，當(dāng)前結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)。結(jié)果如下圖所示。

當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)滿足條件，故刪除結(jié)束。

e）上述情況下，我們接著刪除key為40的記錄，刪除后結(jié)果如下圖所示。

同理，當(dāng)前結(jié)點(diǎn)的記錄數(shù)小于2，兄弟結(jié)點(diǎn)中沒(méi)有多余key，所以父結(jié)點(diǎn)中的key下移，和兄弟（這里我們選擇左兄弟，選擇右兄弟也可以）結(jié)點(diǎn)合并，合并后的指向當(dāng)前結(jié)點(diǎn)的指針就指向了父結(jié)點(diǎn)。

同理，對(duì)于當(dāng)前結(jié)點(diǎn)而言只能繼續(xù)合并了，最后結(jié)果如下所示。

合并后結(jié)點(diǎn)當(dāng)前結(jié)點(diǎn)滿足條件，刪除結(jié)束。

?

2.B 樹(shù)

2.1 B 樹(shù)的定義

各種資料上B 樹(shù)的定義各有不同，一種定義方式是關(guān)鍵字個(gè)數(shù)和孩子結(jié)點(diǎn)個(gè)數(shù)相同。這里我們采取維基百科上所定義的方式，即關(guān)鍵字個(gè)數(shù)比孩子結(jié)點(diǎn)個(gè)數(shù)小1，這種方式是和B樹(shù)基本等價(jià)的。上圖就是一顆階數(shù)為4的B 樹(shù)。

除此之外B 樹(shù)還有以下的要求。

1）B 樹(shù)包含2種類型的結(jié)點(diǎn)：內(nèi)部結(jié)點(diǎn)（也稱索引結(jié)點(diǎn)）和葉子結(jié)點(diǎn)。根結(jié)點(diǎn)本身即可以是內(nèi)部結(jié)點(diǎn)，也可以是葉子結(jié)點(diǎn)。根結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)最少可以只有1個(gè)。

2）B 樹(shù)與B樹(shù)最大的不同是內(nèi)部結(jié)點(diǎn)不保存數(shù)據(jù)，只用于索引，所有數(shù)據(jù)（或者說(shuō)記錄）都保存在葉子結(jié)點(diǎn)中。

3） m階B 樹(shù)表示了內(nèi)部結(jié)點(diǎn)最多有m-1個(gè)關(guān)鍵字（或者說(shuō)內(nèi)部結(jié)點(diǎn)最多有m個(gè)子樹(shù)），階數(shù)m同時(shí)限制了葉子結(jié)點(diǎn)最多存儲(chǔ)m-1個(gè)記錄。

4）內(nèi)部結(jié)點(diǎn)中的key都按照從小到大的順序排列，對(duì)于內(nèi)部結(jié)點(diǎn)中的一個(gè)key，左樹(shù)中的所有key都小于它，右子樹(shù)中的key都大于等于它。葉子結(jié)點(diǎn)中的記錄也按照key的大小排列。

5）每個(gè)葉子結(jié)點(diǎn)都存有相鄰葉子結(jié)點(diǎn)的指針，葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大順序鏈接。

?

2.2 B 樹(shù)的插入操作

1）若為空樹(shù)，創(chuàng)建一個(gè)葉子結(jié)點(diǎn)，然后將記錄插入其中，此時(shí)這個(gè)葉子結(jié)點(diǎn)也是根結(jié)點(diǎn)，插入操作結(jié)束。

2）針對(duì)葉子類型結(jié)點(diǎn)：根據(jù)key值找到葉子結(jié)點(diǎn)，向這個(gè)葉子結(jié)點(diǎn)插入記錄。插入后，若當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)小于等于m-1，則插入結(jié)束。否則將這個(gè)葉子結(jié)點(diǎn)分裂成左右兩個(gè)葉子結(jié)點(diǎn)，左葉子結(jié)點(diǎn)包含前m/2個(gè)記錄，右結(jié)點(diǎn)包含剩下的記錄，將第m/2 1個(gè)記錄的key進(jìn)位到父結(jié)點(diǎn)中（父結(jié)點(diǎn)一定是索引類型結(jié)點(diǎn)），進(jìn)位到父結(jié)點(diǎn)的key左孩子指針向左結(jié)點(diǎn),右孩子指針向右結(jié)點(diǎn)。將當(dāng)前結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)，然后執(zhí)行第3步。

3）針對(duì)索引類型結(jié)點(diǎn)：若當(dāng)前結(jié)點(diǎn)key的個(gè)數(shù)小于等于m-1，則插入結(jié)束。否則，將這個(gè)索引類型結(jié)點(diǎn)分裂成兩個(gè)索引結(jié)點(diǎn)，左索引結(jié)點(diǎn)包含前(m-1)/2個(gè)key，右結(jié)點(diǎn)包含m-(m-1)/2個(gè)key，將第m/2個(gè)key進(jìn)位到父結(jié)點(diǎn)中，進(jìn)位到父結(jié)點(diǎn)的key左孩子指向左結(jié)點(diǎn), 進(jìn)位到父結(jié)點(diǎn)的key右孩子指向右結(jié)點(diǎn)。將當(dāng)前結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)，然后重復(fù)第3步。

下面是一顆5階B樹(shù)的插入過(guò)程，5階B數(shù)的結(jié)點(diǎn)最少2個(gè)key，最多4個(gè)key。

a）空樹(shù)中插入5

b）依次插入8，10，15

c）插入16

插入16后超過(guò)了關(guān)鍵字的個(gè)數(shù)限制，所以要進(jìn)行分裂。在葉子結(jié)點(diǎn)分裂時(shí)，分裂出來(lái)的左結(jié)點(diǎn)2個(gè)記錄，右邊3個(gè)記錄，中間key成為索引結(jié)點(diǎn)中的key，分裂后當(dāng)前結(jié)點(diǎn)指向了父結(jié)點(diǎn)（根結(jié)點(diǎn)）。結(jié)果如下圖所示。

當(dāng)然我們還有另一種分裂方式，給左結(jié)點(diǎn)3個(gè)記錄，右結(jié)點(diǎn)2個(gè)記錄，此時(shí)索引結(jié)點(diǎn)中的key就變?yōu)?5。

d）插入17

e）插入18，插入后如下圖所示

當(dāng)前結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于5，進(jìn)行分裂。分裂成兩個(gè)結(jié)點(diǎn)，左結(jié)點(diǎn)2個(gè)記錄，右結(jié)點(diǎn)3個(gè)記錄，關(guān)鍵字16進(jìn)位到父結(jié)點(diǎn)（索引類型）中，將當(dāng)前結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)。

當(dāng)前結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)滿足條件，插入結(jié)束。

f）插入若干數(shù)據(jù)后

g）在上圖中插入7，結(jié)果如下圖所示

當(dāng)前結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)超過(guò)4，需要分裂。左結(jié)點(diǎn)2個(gè)記錄，右結(jié)點(diǎn)3個(gè)記錄。分裂后關(guān)鍵字7進(jìn)入到父結(jié)點(diǎn)中，將當(dāng)前結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)，結(jié)果如下圖所示。

當(dāng)前結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)超過(guò)4，需要繼續(xù)分裂。左結(jié)點(diǎn)2個(gè)關(guān)鍵字，右結(jié)點(diǎn)2個(gè)關(guān)鍵字，關(guān)鍵字16進(jìn)入到父結(jié)點(diǎn)中，將當(dāng)前結(jié)點(diǎn)指向父結(jié)點(diǎn)，結(jié)果如下圖所示。

當(dāng)前結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)滿足條件，插入結(jié)束。

?

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

如果葉子結(jié)點(diǎn)中沒(méi)有相應(yīng)的key，則刪除失敗。否則執(zhí)行下面的步驟

1）刪除葉子結(jié)點(diǎn)中對(duì)應(yīng)的key。刪除后若結(jié)點(diǎn)的key的個(gè)數(shù)大于等于Math.ceil(m-1)/2 – 1，刪除操作結(jié)束,否則執(zhí)行第2步。

2）若兄弟結(jié)點(diǎn)key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟結(jié)點(diǎn)借一個(gè)記錄，同時(shí)用借到的key替換父結(jié)（指當(dāng)前結(jié)點(diǎn)和兄弟結(jié)點(diǎn)共同的父結(jié)點(diǎn)）點(diǎn)中的key，刪除結(jié)束。否則執(zhí)行第3步。

3）若兄弟結(jié)點(diǎn)中沒(méi)有富余的key,則當(dāng)前結(jié)點(diǎn)和兄弟結(jié)點(diǎn)合并成一個(gè)新的葉子結(jié)點(diǎn)，并刪除父結(jié)點(diǎn)中的key（父結(jié)點(diǎn)中的這個(gè)key兩邊的孩子指針就變成了一個(gè)指針，正好指向這個(gè)新的葉子結(jié)點(diǎn)），將當(dāng)前結(jié)點(diǎn)指向父結(jié)點(diǎn)（必為索引結(jié)點(diǎn)），執(zhí)行第4步（第4步以后的操作和B樹(shù)就完全一樣了，主要是為了更新索引結(jié)點(diǎn)）。

4）若索引結(jié)點(diǎn)的key的個(gè)數(shù)大于等于Math.ceil(m-1)/2 – 1，則刪除操作結(jié)束。否則執(zhí)行第5步

5）若兄弟結(jié)點(diǎn)有富余，父結(jié)點(diǎn)key下移，兄弟結(jié)點(diǎn)key上移，刪除結(jié)束。否則執(zhí)行第6步

6）當(dāng)前結(jié)點(diǎn)和兄弟結(jié)點(diǎn)及父結(jié)點(diǎn)下移key合并成一個(gè)新的結(jié)點(diǎn)。將當(dāng)前結(jié)點(diǎn)指向父結(jié)點(diǎn)，重復(fù)第4步。

注意，通過(guò)B 樹(shù)的刪除操作后，索引結(jié)點(diǎn)中存在的key，不一定在葉子結(jié)點(diǎn)中存在對(duì)應(yīng)的記錄。

下面是一顆5階B樹(shù)的刪除過(guò)程，5階B數(shù)的結(jié)點(diǎn)最少2個(gè)key，最多4個(gè)key。

a）初始狀態(tài)

b）刪除22,刪除后結(jié)果如下圖

刪除后葉子結(jié)點(diǎn)中key的個(gè)數(shù)大于等于2，刪除結(jié)束

c）刪除15，刪除后的結(jié)果如下圖所示

刪除后當(dāng)前結(jié)點(diǎn)只有一個(gè)key,不滿足條件，而兄弟結(jié)點(diǎn)有三個(gè)key，可以從兄弟結(jié)點(diǎn)借一個(gè)關(guān)鍵字為9的記錄,同時(shí)更新將父結(jié)點(diǎn)中的關(guān)鍵字由10也變?yōu)?，刪除結(jié)束。

d）刪除7，刪除后的結(jié)果如下圖所示

當(dāng)前結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)小于2，（左）兄弟結(jié)點(diǎn)中的也沒(méi)有富余的關(guān)鍵字（當(dāng)前結(jié)點(diǎn)還有個(gè)右兄弟，不過(guò)選擇任意一個(gè)進(jìn)行分析就可以了，這里我們選擇了左邊的），所以當(dāng)前結(jié)點(diǎn)和兄弟結(jié)點(diǎn)合并，并刪除父結(jié)點(diǎn)中的key，當(dāng)前結(jié)點(diǎn)指向父結(jié)點(diǎn)。

此時(shí)當(dāng)前結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)小于2，兄弟結(jié)點(diǎn)的關(guān)鍵字也沒(méi)有富余，所以父結(jié)點(diǎn)中的關(guān)鍵字下移，和兩個(gè)孩子結(jié)點(diǎn)合并，結(jié)果如下圖所示。

?

3.參考內(nèi)容

[1]?B 樹(shù)介紹

[2]?從MySQL Bug#67718淺談B 樹(shù)索引的分裂優(yōu)化

[3]?B 樹(shù)的幾點(diǎn)總結(jié)