引言

這是本博客中第一篇介紹數(shù)據(jù)結(jié)構(gòu)與算法的文章，所以開頭我想多說幾句。算法是程序員「恰飯」的根本之一，這個無需多討論。而這個東西偏偏又短時間難以掌握，所以如果平時不花點工夫進(jìn)行學(xué)習(xí)，等用到了就抓瞎了。正所謂「人無遠(yuǎn)慮，必有近憂」。有人會說這些東西工作中用不到，我覺得可能還是沒有真正的意識到一些東西，導(dǎo)致工作中即使接觸到了，也不當(dāng)回事。

不過話說回來，對于我來說學(xué)習(xí)算法不是為了參加競賽，不是為了過某次面試。我學(xué)習(xí)算法想要以實用為主，同時開拓自己的思路，遇到問題時可以快速地想到更多解決方案。因此文章里（包括本篇）的一些描述和用詞，可能并不專業(yè)，而是怎么方便理解怎么來。關(guān)于這一點還請讀者了解。

本篇文章里我們介紹一下B樹?！窧樹」這個名字是這個算法的發(fā)明人給起的，維基百科上介紹發(fā)明人沒有解釋字母「 B 」代表什么，可能是發(fā)明人之一拜爾（ Bayer ）名字的首字母，也可能是當(dāng)時所在的公司 Boeing 的首字母。不過我自己理解，代表「 Block 」也挺有意義的，具體原因看完這篇文章，你就明白了。

什么是B樹

我們首先嘗試著定義一下什么是B樹。不過這種定義一般都很難理解，所以這里我們首先形象的看一下B樹一般長什么樣子，然后說明一下它的一些關(guān)鍵特性，最后再給出相對嚴(yán)謹(jǐn)?shù)亩x描述。

下面是一棵B樹示意圖（注意圖中并沒有示意出 key 所對應(yīng)的 value 數(shù)據(jù)）：

可以看到，與我們常見到的二叉樹或紅黑樹不同，B樹的每個結(jié)點中可以有多個 key。在上圖中最多有 4 個，最少 2 個（這不是巧合，因為B樹的每個結(jié)點內(nèi)部必須有至少一半的有效的 key）。key 的排序倒與二叉樹類似：某個 key 的左子樹上的所有 key 都比自己小；右子樹上的 key 都比自己大。

另外細(xì)心的你可能已經(jīng)發(fā)現(xiàn)，上面這棵B樹的所有葉子結(jié)點的高度都是一樣的。這不是巧合，而是B樹的操作規(guī)則導(dǎo)致它的所有葉子始終在同一高度上。

（不得不說的是，這個圖中結(jié)點最大關(guān)鍵字?jǐn)?shù)量并不嚴(yán)格符合B樹的定義，在《算法導(dǎo)論》中要求B樹中的最大關(guān)鍵字?jǐn)?shù)量是一個奇數(shù)，因為這樣一來有些操作就比較方便了。不過限于圖片的展示大小，我這里暫時忽略了這一點，用了 4 個關(guān)鍵字而非 5 個）

看到這里，讀者應(yīng)該對B樹有了一個大體的印象，但可能心里仍會有疑問：好像也沒什么特別的，不過是每個結(jié)點的 key 多一些，葉子始終在同一高度上；但真是要查找某個 key，感覺好像還不如平衡二叉樹方便呢（因為不光要在結(jié)點之間查找，還要在結(jié)點內(nèi)部使用二分查找法查找）；效率也不見得比紅黑樹或平衡二叉樹高。

要解釋這些疑問，要從各種樹的應(yīng)用場景說起。平衡二叉樹（或紅黑樹）的應(yīng)用雖然很多，但一般都是用來引用內(nèi)存中的數(shù)據(jù)，即這些樹的結(jié)點數(shù)據(jù)都在內(nèi)存中；而B樹一般應(yīng)用在數(shù)據(jù)庫索引或文件系統(tǒng)中，它引用的數(shù)據(jù)要大得多，多數(shù)結(jié)點數(shù)據(jù)都是存放在硬盤中的，而硬盤的訪問速度顯然比內(nèi)存慢得多。這就顯現(xiàn)出了B樹的優(yōu)勢：同樣的數(shù)據(jù)，如果使用B樹組織，訪問數(shù)據(jù)時需要讀取磁盤的次數(shù)遠(yuǎn)小于使用平衡二叉樹或紅黑樹時的訪問次數(shù)。

比如如果要訪問 key 為 45 的數(shù)據(jù)，在上面B樹的例子中只需訪問兩次磁盤（根結(jié)點始終在內(nèi)存中）；而使用平衡二叉樹最好的情況下也需要訪問 4 次磁盤。并且這種差距會隨著數(shù)據(jù)量的增加而更加明顯。

所以B樹的設(shè)計不僅僅是每個結(jié)點 key 多一些這么簡單，它有自己的應(yīng)用場景，那就是當(dāng)數(shù)據(jù)大到需要將多數(shù)結(jié)點放到磁盤中時，B樹既可以保證快速找到想要的數(shù)據(jù)，又可以保證訪問磁盤的次數(shù)最少，從而最大化訪問速度。

磁盤中有「塊」（或「頁」）的概念，「塊」是磁盤每次訪問的最小單位。也就是說，即使你只想讀一個字節(jié)，也需要先從磁盤讀上一個「塊」的數(shù)據(jù)。所以對于多數(shù)結(jié)點都存儲在磁盤上的B樹來說，一個結(jié)點正好占用一個磁盤塊（或至少一個）是最自然不過的了；而每個結(jié)點中最多有多少 key/value 數(shù)據(jù)對，則要看這些數(shù)據(jù)對的大小，并不是固定的。

所以我們可以總結(jié)B樹有以下特點：

主要應(yīng)用于數(shù)據(jù)庫索引或文件系統(tǒng)中，所組織的數(shù)據(jù)和樹結(jié)點本身多數(shù)位于磁盤上，而不是內(nèi)存中。
每個結(jié)點的大小正好等于一個（或多個）磁盤塊的大小
每個結(jié)點內(nèi)部有多個 key/value 數(shù)據(jù)對，數(shù)據(jù)對的最大數(shù)量等于單個結(jié)點所能容納的數(shù)據(jù)對的最大量；最小數(shù)量為最大數(shù)量的一半（根結(jié)點除外）
每個結(jié)點內(nèi)部的 key 都有對應(yīng)的左右子樹；所有左子樹中的 key 都小于自己；所有右子樹的 key 都大于自己。
所有葉結(jié)點的高度是一樣的

相信現(xiàn)在你已經(jīng)對B樹有了一個大致上的印象。在這一小節(jié)的最后，我們給出B樹的嚴(yán)謹(jǐn)?shù)亩x。不過我覺得一件東西如何定義的不重要，它在你心中是什么樣子才重要。

下面是《算法導(dǎo)論》一書中給出的B樹的定義（我替換了書中使用的符號，我覺我的寫法對于程序員來說更容易理解，雖然理解原書使用的符號也不難）：

一棵B樹 $T$ 是具有如下性質(zhì)的有根樹（根為 $root[T]$ ）:

每個結(jié)點 node 有以下域：
a) node.count: 當(dāng)前存儲在結(jié)點 node 中的 key 的數(shù)量
b) node.key: 存放關(guān)鍵字的數(shù)組，一共 node.count 個，以非降序存放。所以 node.key[0] <= node.key[1] <= ... <= node.key[node.count-1]
c) node.isLeaf: 一個布爾值，如果 node 是葉子的話，值為 true；否則為 false
d) node.child: 子結(jié)點數(shù)組，每個元素指向某個子結(jié)點。一共 node.count+1 個

各關(guān)鍵字 node.key[i] 對儲存在各子樹中的關(guān)鍵字范圍加以分隔：如果 $k_i$ 為存儲在以 node.child[i] 為根的子樹的關(guān)鍵字，則 $k_0$ <= node.key[0] <= $k_1$ <= node.key[1] <= ... <= node.key[node.count-1] <= $k_{node.count}$

每個葉結(jié)點具有相同的高度，即樹的高度 $h$

每一個結(jié)點能包含的關(guān)鍵字?jǐn)?shù)有一個上界和下界。這個界稱為B樹的最小度數(shù)，我們使用固定整數(shù) $t$ >= 2 來表示
a) 每個非根結(jié)點必須至少有 $t-1$ 個關(guān)鍵字，也即每個非根內(nèi)結(jié)點至少有 $t$ 個子女。如果樹是非空的，根結(jié)點至少包含一個關(guān)鍵字。
b) 每個結(jié)點可包含至多 $2t - 1$ 個關(guān)鍵字。所以一個內(nèi)結(jié)點至多可有 $2t$ 個子女（如果恰好有 $2t - 1$ 關(guān)鍵字，我們就說這個結(jié)點是「滿的」）

這就是B樹的定義。這里有幾個要點，我們再次總結(jié)重申一下：一是B樹的每個非根結(jié)點都有多個關(guān)鍵字（至少 $t-1$ ，至多 $2t-1$ ）和相應(yīng)數(shù)量的子女；二是每個葉結(jié)點的高度相同。

在我剛看《算法導(dǎo)論》時，我感覺這里樹的度數(shù) $t$ 的定義稍顯別扭：為什么要定義一個最小度數(shù) $t$ 呢？無非就是結(jié)點關(guān)鍵字?jǐn)?shù)量的上界和下界，直接定義每個結(jié)點最多有 $x$ 個、最少有 $\frac{x}{2}$ 個關(guān)鍵字，或最少有 $x$ 個、最多有 $2x$ 個關(guān)鍵字，不是也可以嗎？其實書中這樣定義的目的，是為了始終保證每個滿結(jié)點有奇數(shù)個關(guān)鍵字，這一特點在「分裂結(jié)點」時特別有用。具體在后面介紹結(jié)點分裂時，再作詳細(xì)的說明。

另外你會發(fā)現(xiàn)，當(dāng) $t = 1$ 時，每個結(jié)點最多有一個關(guān)鍵字、兩個子女。這時的B樹是最簡單的，基本上等同于二叉樹了。

在后面的介紹B樹的各種操作時，我們?nèi)詴褂眠@個定義里出現(xiàn)的一些符號，請確保到目前為止理解了這些符號的含義。

B樹的操作

下面我們來看看在B樹上如何進(jìn)行操作。對于多數(shù)數(shù)據(jù)結(jié)構(gòu)，所進(jìn)行的操作無非就是「增刪改查」?！感薷摹惯@一操作是建立在其它操作的基礎(chǔ)之上的，因此沒什么可說的。這里我們重點關(guān)注查找、插入和刪除。

在詳細(xì)介紹插入和刪除操作算法之前，我們需要記住B樹的這倆操作的關(guān)鍵動作，它們就是：

分裂
合并
挪用

前兩個關(guān)鍵動作是對于結(jié)點來說的，即「分裂結(jié)點」或「合并結(jié)點」；后一個是對關(guān)鍵字來說的，即「挪用關(guān)鍵字」。當(dāng)在插入或刪除過程中，被修改的結(jié)點不符合B樹的要求時，我們就使用這三個關(guān)鍵操作中的一個對其進(jìn)行處理，就可以使結(jié)點重新符合B樹的要求。確切的說，當(dāng)對某個結(jié)點進(jìn)行「插入」或「刪除」操作時，如果結(jié)點關(guān)鍵字的數(shù)量不再滿足要求（至少 $t-1$ ，至多 $2t-1$ ），就需要對結(jié)點進(jìn)行分裂或合并，或從別處挪用一個關(guān)鍵字過來。具體細(xì)節(jié)我們后面再說。

（我不確定這里用「關(guān)鍵動作」這一詞語是不是準(zhǔn)確，不過對于很多數(shù)據(jù)結(jié)構(gòu)的操作算法來說，都有這樣一類操作，比如紅黑樹的關(guān)鍵動作是「旋轉(zhuǎn)」。對于這種數(shù)據(jù)結(jié)構(gòu)，如果修改后不符合自身的要求，只要使用它的關(guān)鍵動作想辦法調(diào)整一下，就可以重新符合要求。我覺得這是理解這類數(shù)據(jù)結(jié)構(gòu)的操作算法的關(guān)鍵，并不需要死記硬背，希望讀者能花心思體會一下。）

下面我們就詳細(xì)說明一下針對B樹的各種操作。在這個過程中，我們采用兩個約定：

B樹的根始終在內(nèi)存中。
除根以外，其它結(jié)點都在磁盤中。

基于這兩個約定，在操作時B樹的結(jié)點時，我們需要注意：

對非根結(jié)點進(jìn)行操作之前，要先調(diào)用 DISK-READ 將結(jié)點數(shù)據(jù)讀取到內(nèi)存中
對根結(jié)點進(jìn)行操作之前無需調(diào)用 DISK-READ
所有結(jié)點被修改后，要立即調(diào)用 DISK-WRITE 將其寫回磁盤
某個結(jié)點被刪除，調(diào)用 DISK-DELETE 將其從磁盤中刪除

另外需要說明一點的是，與《算法導(dǎo)論》保持一致，我們這里對B樹進(jìn)行操作時，也只會沿著樹的根下降，不會有任何結(jié)點的回溯。

查找

對于任意類型的樹來說，查找操作是最簡單的了，B樹也是這樣。相信不需要介紹，讀者也知道該怎么查找（或稱為「遍歷」）一棵B樹。與普通樹（如二叉樹）不同的是，B樹在每個結(jié)點上不僅僅有兩個分支，而是有多個分支。準(zhǔn)確的說，如果一個結(jié)點有 n 個 key，那么在這個結(jié)點上就有 n+1 個分支，在進(jìn)行查找時，需要對這 n 個 key 進(jìn)行一個查找（如二分查找），來決定應(yīng)該走哪個分支。

下面我們是查找B樹的偽代碼：

BTREE-SEARCH(root, k) {
    // 找出使 k <= root.key[i] 成立的最小下標(biāo) i
    // 注意如果沒找到，i 的值會被設(shè)置為 root.count，
    // 恰好是最后一個子女的下標(biāo)
    i <- 0
    while i < root.count and k > root.key[i]
        i <- i + 1

    // 找到了，返回
    if i < root.count and k == root.key[i] {
        return (root, i) 
    }

    // 達(dá)到葉子結(jié)點，查找結(jié)束
    if root.isLeaf
        return NIL
    else
        // 在女子 root.child[i] 中查找 k
        DISK-READ(root.child[i])
        return BTREE-SEARCH(k, root.child[i])
}

這個偽代碼中使用了遞歸查找關(guān)鍵字 k，調(diào)用方式為 BTREE-SEARCH( $root[T]$ , k)。偽代碼比較簡單，也有詳細(xì)的注釋，這里就不多解釋了。

插入

讓我們「拍腦袋」想想，如何向B樹中插入關(guān)鍵字呢？首先我們要找到這個關(guān)鍵字應(yīng)該插入到哪個結(jié)點中；找到了這個結(jié)點，就可以把這個關(guān)鍵字插入到 node.key 數(shù)組中的合適位置了。

不過稍等，我們之前說過，B樹的每個結(jié)點最多有 $2t-1$ 個關(guān)鍵字。所以如果我們找到的這個結(jié)點的關(guān)鍵字個數(shù)小于 $2t-1$ ，那么非常棒我們直接把關(guān)鍵字插入到 node.key 中的合適位置就可以了；但如果這個結(jié)點中的關(guān)鍵字正好是 $2t-1$ 個、即這是個滿結(jié)點呢？此時是無法把這個關(guān)鍵字直接插入到這個結(jié)點中的。這時就要用到「分裂結(jié)點」這一關(guān)鍵動作了。那么什么是「分裂結(jié)點」呢？

結(jié)點的分裂

簡單來說，分裂結(jié)點就是在向某個滿結(jié)點插入新的關(guān)鍵字之前，先將這個滿結(jié)點一分為二、變?yōu)閮蓚€結(jié)點的過程。變?yōu)閮蓚€結(jié)點之后，就有空間容納新的關(guān)鍵字了。分裂之前的滿結(jié)點有 $2t-1$ 個關(guān)鍵字；分裂后兩個結(jié)點各有 $t-1$ 個關(guān)鍵字（其中前一個結(jié)點保留了原滿結(jié)點比較小的 $t-1$ 個關(guān)鍵字；而后一個結(jié)點保留了原滿結(jié)點比較大的 $t-1$ 個關(guān)鍵字）；位于中間的那個關(guān)鍵字則被提到了父結(jié)點中，作為兩個結(jié)點的分隔關(guān)鍵字。

注意剛才描述的分裂過程中，關(guān)鍵字?jǐn)?shù)量一直保持不變：分裂前的滿結(jié)點關(guān)鍵字?jǐn)?shù)量為 $2t-1$ ，分裂后關(guān)鍵字?jǐn)?shù)量為 $(t-1) + (t-1) + 1 = 2t-1$ 。另外這里也清楚的說明了《算法導(dǎo)論》中為什么要如此定義 $t$ ：滿結(jié)點的關(guān)鍵字個數(shù)為 $2t-1$ ，這肯定是個奇數(shù)，因此分裂時總能保證每個新結(jié)點都有相同的、B樹所要求的最少數(shù)量的 $t-1$ 個結(jié)點，同時也總能保證肯定有一個中間關(guān)鍵字可以被放到父結(jié)點中，用來分隔這兩個新結(jié)點。

這一分裂的過程可用如下示意圖表示：

還需說明一點的是，分裂時可以將中間關(guān)鍵字放到父結(jié)點用來分隔兩個新結(jié)點的前提條件是，父結(jié)點不是滿結(jié)點。如果是父結(jié)點也是滿結(jié)點該怎么辦呢？

這里有兩個辦法，一個是繼續(xù)向上分裂父結(jié)點，如果祖父結(jié)點也是滿的，繼續(xù)向上分裂，直到遇到一個非滿的父結(jié)點。如果一路分裂到根結(jié)點，發(fā)現(xiàn)根結(jié)點也是滿結(jié)點，那就只能分裂這個根結(jié)點，并新生成一個新結(jié)點作為根結(jié)點，而舊的根結(jié)點分裂而成的兩個結(jié)點作為新根的兩個子結(jié)點。這時樹的高度增加了 1。

另一個辦法是在從根開始下降查找將要插入的結(jié)點時，遇到滿結(jié)點就將其分裂。這樣一路找一路分裂下來，最后插入前進(jìn)行分裂時，其父結(jié)點肯定不是滿結(jié)點，因而可以正常分裂了。同第一個辦法一樣，如果根是滿結(jié)點，樹的高度也會加1。

第二個辦法相對簡單，《算法導(dǎo)論》中使用的就是這個方法，這里我們也使用這個方法。

這里順便解釋一下為什么B樹的所有葉子結(jié)點高度都相同，且等于樹的高度。從上面的兩個方法可以看出，無論哪個方法，樹的高度的增加都是由分裂根結(jié)點引起的，而不是像其它樹結(jié)構(gòu)那樣，由新加入一個葉子結(jié)點引起的。因此B樹的所有葉子總有相同的高度。

下面給出結(jié)點分裂的偽代碼：

// BTREE-SPLIT 將一個指定的結(jié)點分裂成兩個。
// parent:      將要分裂的結(jié)點（即 splitedNode）的父結(jié)點
// childIndex:  將要分裂的結(jié)點在 parent.child 中的下標(biāo)值
// splitedNode: 將要被分裂的結(jié)點
BTREE-SPLIT(parent, childIndex, splitedNode) {
    // splitKey 代表將被提取到 parent 中分隔兩個分裂結(jié)點的關(guān)鍵字
    splitKey <- splitedNode.key[t-1]

    // 首先創(chuàng)建一個新的結(jié)點，并填充新結(jié)點的各個字段
    // 這里我們把 splitedNode 中的后半部分的 key 和 child 放到 newNode 中
    newNode <- ALLOC-NODE()
    newNode.count <- t - 1
    newNode.isLeaf <- splitedNode.isLeaf
    for i <- 0 ; i < t-1 ; i++
        newNode.key[i] <- splitedNode.key[i + t]
    if not newNode.isLeaf
        for i <- 0 ; i < t ; i++
            newNode.child[i] <- splitedNode.child[i + t]

    // 修改 splitedNode，只保留前半部分的 key 和 child
    splitedNode.count <- t - 1

    // 修改 parent，將分裂后的兩個結(jié)點及新的 key 放到正確的位置
    keyIndex = childIndex
    for i <- parent.count; i > keyIndex; i--
        parent.key[i] <- parent.key[i-1]
    for i <- parent.count + 1; i > childIndex + 1; i--
        parent.child[i] <- parent.child[i-1]
    parent.key[keyIndex] <- splitKey
    parent.child[childIndex + 1] <- newNode
    parent.count <- parent.count + 1

    DISK-WRITE(parent)
    DISK-WRITE(splitedNode)
    DISK-WRITE(newNode)
}

這段偽代碼可以用如下示意圖表示：

無回溯方式插入關(guān)鍵字

知道了如何分裂一個結(jié)點，整個插入過程就簡單多了。這里我們使用的方法與《算法導(dǎo)論》中的一致，即無回溯的方式插入。

前面我們說過，分裂時有可能父結(jié)點也是滿結(jié)點，有兩個方法可以解決這個問題：一個是先遞歸向上分裂父結(jié)點，直到遇到一個非滿的父結(jié)點，這種方式需要進(jìn)行回溯；另一個是從根開始定位將要插入的結(jié)點時，每當(dāng)遇到滿結(jié)點就將其分裂，這種方式不需要進(jìn)行回溯。這兩種方法各有優(yōu)劣，第一種方法實現(xiàn)起來稍復(fù)雜，但只有在必要時才會分裂結(jié)點，可以保持結(jié)點數(shù)量最小化；第二種方法實現(xiàn)起來比較簡單，但有些滿結(jié)點可能暫時不需要分裂，也會被分裂，使結(jié)點數(shù)量有一點點增大。這里我們使用的是第二種方法。

下面我們給出插入的偽代碼：

BTREE-INSERT(T, k) {
    r <- root[T]

    if r.count == 2t-1 {
        // 如果根結(jié)點是滿的，首先分裂根結(jié)點
        newR <- ALLOC-NODE()
        newR.isLeaf <- false
        newR.count <- 0
        newR.child[0] <- r

        root[T] <- newR
        BTREE-SPLIT(newR, 0, r)

        r <- newR
        DISK-WRITE(r)
    }

    BTREE-INSERT-NONFULL(r, k)
}

// 注意 參數(shù) node 總是非滿的
BTREE-INSERT-NONFULL(node, k) {
    // 找到 k 在 node 結(jié)點中的位置
    i < - 0
    while i < node.count and k > node.key[i]
        i <- i + 1

    // k 已經(jīng)存在了，簡單起見這里直接返回。
    // 但也可能需要更新 k 所對應(yīng)的值
    if i < node.count and k == node.key[i]
        return

    if node.isLeaf {
        // 如果 node 是葉結(jié)點，則將 k 插入其中
        for j <- node.count; j > i; j <- j + 1 
            node.key[j] <- node.key[j - 1]

        node.key[i] <- k
        DISK-WRITE(node)
    } else {
        // 如果 node 是內(nèi)部結(jié)點，則將 k 插入到合適的子結(jié)點中
        child <- node.child[i]
        DISK-READ(child)

        // 如果這個合適的子結(jié)點是個滿結(jié)點，則先對其進(jìn)行分裂。
        // 分裂后新提上來的關(guān)鍵字占據(jù)了 i 所指向的位置，因此
        // 要判斷一下，如果 k 大于新提上來的關(guān)鍵字，則子結(jié)點應(yīng)
        // 使用分裂時新創(chuàng)建的結(jié)點；否則仍為原來的子結(jié)點。
        if child.count == 2t - 1 {
            BTREE-SPLIT(node, i, child)
            if k > node.key[i] {
                child <- node.child[i + 1]
            }
        }

        // 遞歸在子結(jié)點中插入 k
        BTREE-INSERT-NONFULL(child, k)
    }
}

插入的過程分成了兩個函數(shù)，BTREE-INSERT 作為最頂層的函數(shù)，用來對B樹的根進(jìn)行分裂；輸助函數(shù) BTREE-INSERT-NONFULL 執(zhí)行真正的插入動作。注意它的參數(shù) node 所代表的永遠(yuǎn)是一個非滿的結(jié)點。

刪除

現(xiàn)在我們再來看看刪除操作。B樹的刪除操作要比插入操作復(fù)雜得多，但不要緊張，只要理清了邏輯，復(fù)雜的問題也會變得很簡單。

我們依然「拍腦袋」想想要刪除一個B樹中的關(guān)鍵字，需要怎么做。首先我們要找到關(guān)鍵字所在的位置，找到以后將這個關(guān)鍵字「去掉」就好了。

這里的「去掉」是有技巧的。不同能類型的結(jié)點，「去掉」的方法也不一樣：
在葉結(jié)點中：把后續(xù)的關(guān)鍵字向前移動，覆蓋掉要刪除的那個關(guān)鍵字
在內(nèi)結(jié)點中：不能使用葉結(jié)點中移動覆蓋的方法，而要用其它關(guān)鍵字「替換」將被刪除的關(guān)鍵字

這里先簡單說一下在內(nèi)結(jié)點中刪除關(guān)鍵字時的情形。其實在內(nèi)結(jié)點中刪除關(guān)鍵字，需要用內(nèi)結(jié)點的子樹中的最值（左子樹的最大值，或右子樹的最小值）替換。替換時需要先將這個最值刪掉，然后再用這個最值替換掉要刪除的關(guān)鍵字。你可能會想到，這個最值肯定是在子樹地葉子結(jié)點中，不是嗎？如此一來，在內(nèi)結(jié)點中刪除關(guān)鍵字的問題，也轉(zhuǎn)變成在葉結(jié)點中刪除關(guān)鍵字的問題了。

所以現(xiàn)在「去掉」關(guān)鍵字的方法的關(guān)鍵只有一個：
在葉結(jié)點中：把后續(xù)的關(guān)鍵字向前移動，覆蓋掉要刪除的那個關(guān)鍵字

這一方法看似簡單，其實有一個重要問題需要解決，那就是在葉結(jié)點中刪除關(guān)鍵字時，我們要保證「去掉」一個關(guān)鍵字后，B樹仍然能保持它的性質(zhì)不變，即所有結(jié)點的關(guān)鍵字?jǐn)?shù)量仍然不小于 $t-1$ 。例如在一個只有 $t-1$ 個關(guān)鍵字的葉結(jié)點中，你不能直接刪除結(jié)點中的某個關(guān)鍵字。

如何解決這個問題呢？很自然的我們會想，只要保證在刪除前，葉結(jié)點中的關(guān)鍵字?jǐn)?shù)量大于 $t-1$ 就可以了。那么如何保證呢？這里也有兩個方法：
如果任一兄弟結(jié)點關(guān)鍵字?jǐn)?shù)量大于 $t-1$ ，就使用
方法1：從兄弟結(jié)點中「挪」一個關(guān)鍵字過來
如果所有兄弟結(jié)點的關(guān)鍵字?jǐn)?shù)量都為 $t-1$ ，就使用
方法2：將兩個兄弟結(jié)點「合并」，組成一個擁有 $2t-1$ 個關(guān)鍵字的新結(jié)點

但是新的問題又出現(xiàn)了。方法2 中「合并」兩個兄弟結(jié)點時，需要從父結(jié)點取走一個關(guān)鍵字。如果父結(jié)點也只有 $t-1$ 關(guān)鍵字該怎么辦呢？我們要保證合并前，父結(jié)點的關(guān)鍵字?jǐn)?shù)量也大于 $t-1$ ......

好像問題的解決方案開始遞歸了，不過可以看到，「挪」關(guān)鍵字和「合并結(jié)點」這兩個方法，是保證任意一個結(jié)點（內(nèi)結(jié)點和葉結(jié)點）的關(guān)鍵字?jǐn)?shù)量大于 $t-1$ 的通用方法。（文章前面提到過的「關(guān)鍵動作」，也包含了這兩種方法）。只要能保證某個結(jié)點是非最小結(jié)點，就可以從中刪除關(guān)鍵字了。

這一段描述到現(xiàn)在，已經(jīng)全部解決了刪除B樹關(guān)鍵字這一操作的幾乎所有問題。我們再整理一下這里面的關(guān)鍵問題：

如何刪除內(nèi)結(jié)點中的關(guān)鍵字
- 關(guān)鍵：刪除子樹葉結(jié)點中的關(guān)鍵字
如何刪除葉結(jié)點中的關(guān)鍵字
- 關(guān)鍵：保證葉結(jié)點和父結(jié)點（內(nèi)結(jié)點）的關(guān)鍵字?jǐn)?shù)量大于
  - 如何從兄弟結(jié)點中「挪」一個關(guān)鍵字到自己結(jié)點中
  - 如何「合并」兩個兄弟結(jié)點

只要我們從解決掉上面這棵「問題樹」，B樹的刪除問題就可以解決了。我們下面會對這里面的所有關(guān)鍵進(jìn)行詳細(xì)的說明。（如果不是十分理解上面這一段的描述也沒關(guān)系，等看完詳細(xì)介紹再回過頭來看這一段描述，應(yīng)該會有一個更加整體和深刻的印象）

從兄弟中挪用關(guān)鍵字

從兄弟中挪用關(guān)鍵字，即將某個兄弟的關(guān)鍵字減小一個，而將自己的關(guān)鍵字增加一個。以下是這一操作的示意圖（圖中展示的是從左兄弟中挪用關(guān)鍵字，從右兄弟中挪用與之類似，就不再展示了）：

從圖中可以看出，其實嚴(yán)格來說不是直接從兄弟中挪用，而是先將父結(jié)點中分隔兄弟倆的關(guān)鍵字挪到自己結(jié)點中，再將兄弟的關(guān)鍵字挪到父結(jié)點中作為新的分隔兄弟倆的關(guān)鍵字。

下面是這一操作的偽代碼：

// BTREE-EXTEND-FROM-LEFT-BROTHER 從左兄弟中挪一個關(guān)鍵字到自己結(jié)點中
// parent:     將要增加關(guān)鍵字的結(jié)點的父結(jié)點
// childIndex: 將要增加關(guān)鍵字的結(jié)點在 parent.child 中的下標(biāo)索引
// node:       將要增加關(guān)鍵字的結(jié)點
BTREE-EXTEND-FROM-LEFT-BROTHER(parent, childIndex, node) {
    leftBrotherIndex <- childIndex - 1
    leftBrother <- parent.child[leftBrotherIndex]

    // 移除左兄弟的最大的關(guān)鍵字及其右孩子
    newSplitkey, child <- BTREE-REMOVE-MAX-IN-NODE(leftBrother)

    // 將舊的分隔關(guān)鍵字及 child 加入到自己結(jié)點中
    // 然后并新的分隔關(guān)鍵字寫入 parent 中
    splitkeyIndex <- leftBrotherIndex
    BTREE-INSERT-AS-MIN-IN-NODE(node, parent.key[splitkeyIndex], child)
    parent.key[splitkeyIndex] <- newSlitKey
    DISK-WRITE(parent)
}

// BTREE-EXTEND-FROM-RIGHT-BROTHER 從右兄弟中挪一個關(guān)鍵字到自己結(jié)點中
// parent:     將要增加關(guān)鍵字的結(jié)點的父結(jié)點
// childIndex: 將要增加關(guān)鍵字的結(jié)點在 parent.child 中的下標(biāo)索引
// node:       將要增加關(guān)鍵字的結(jié)點
BTREE-EXTEND-FROM-RIGHT-BROTHER(parent, childIndex, node) {
    rightBrotherIndex <- childIndex + 1
    rightBrother <- parent.child[rightBrotherIndex]

    // 移除右兄弟的最小關(guān)鍵字及其左孩子
    newSplitkey, child <- BTREE-REMOVE-MIN-IN-NODE(rightBrother)

    // 將舊的分隔關(guān)鍵字及 child 加入到自己結(jié)點中
    // 然后并新的分隔關(guān)鍵字寫入 parent 中
    splitKeyIndex <- childIndex
    BTREE-INSERT-AS-MAX-IN-NODE(node, parent.key[splitKeyIndex], child)
    parent.key[splitKeyIndex] <- newSplitKey
    DISK-WRITE(parent)
}

這里共兩個函數(shù)，分別用來從左兄弟和右兄弟中挪用關(guān)鍵字。這兩個函數(shù)都比較簡單，就不多解釋了。其中用到了幾個輔助函數(shù)，它們的偽代碼如下：

// BTREE-INSERT-AS-MIN-IN-NODE 將 key 和 child 作為最小關(guān)鍵字
// 寫入 node 結(jié)點中
BTREE-INSERT-AS-MIN-IN-NODE(node, key, child) {
    for i <- node.count; i > 0; i <- i - 1
        node.key[i] <- node.key[i - 1]
    if not node.isLeaf
        for  i <- node.count + 1; i > 0; i <- i - 1
            node.child[i] <- node.child[i - 1]

    node.key[0] <- key 
    if not node.isLeaf
        node.child[0] <- child
    node.count <- node.count + 1

    DISK-WRITE(node)
}

// BTREE-INSERT-AS-MAX-IN-NODE 將 key 和 child 作為最大關(guān)鍵字
// 寫入 node 結(jié)點中
BTREE-INSERT-AS-MAX-IN-NODE(node, key, child) {
    node.key[node.count] <- key
    if not node.isLeaf
        node.child[node.count + 1] <- child
    node.count <- node.count + 1

    DISK-WRITE(node)
}

// BTREE-REMOVE-MAX-IN-NODE 將 node 中
// 最大的關(guān)鍵字及其右孩子移除，并返回
BTREE-REMOVE-MAX-IN-NODE(node) {
    key <- node.key[node.count - 1]
    if not node.isLeaf
        child <- node.child[node.count]
    else
        child <- NIL
    node.count <- node.count - 1
    
    DISK-WRITE(node)
    return (key, child)
}

// BTREE-REMOVE-MIN-IN-NODE 將 node 中
// 最小的關(guān)鍵字及其左孩子移除，并返回
BTREE-REMOVE-MIN-IN-NODE(node) {
    key <- node.key[0]
    if not node.isLeaf
        child <- node.child[0]
    else
        child <- NIL

    for i <- 0; i < node.count - 1; i <- i + 1
        node.key[i] <- node.key[i+1]
    if not node.isLeaf
        for i <- 0; i < node.count; i <- i + 1
            node.child[i] <- node.child[i+1]
    node.count <- node.count - 1

    DISK-WRITE(node)
    return (key, child)
}

合并結(jié)點

剛才我們介紹的從兄弟中挪用關(guān)鍵字的前提是，兄弟中有關(guān)鍵字可以挪用，即左右兩兄弟中至少有一個關(guān)鍵字?jǐn)?shù)量大于 $t-1$ 。但如果某結(jié)點左右兩兄弟的關(guān)鍵字?jǐn)?shù)量都為 $t-1$ 該怎么辦呢？那只能合并結(jié)點了。

所謂合并結(jié)點，就是將兩個關(guān)鍵字?jǐn)?shù)量為 $t-1$ 的結(jié)點合并為一個結(jié)點，加上父結(jié)點中的分隔關(guān)鍵字，新結(jié)點的關(guān)鍵字?jǐn)?shù)量正好為 $2t-1$ 。下面是這一操作的示意圖：

這里需要特別強(qiáng)調(diào)的一點是，兩個結(jié)點可以合并，除了兩個結(jié)點的關(guān)鍵字?jǐn)?shù)量都必須為 $t-1$ 外，還有一個重要的前提是父結(jié)點的關(guān)鍵字?jǐn)?shù)量大于 $t-1$ 。因為合并時將把分隔關(guān)鍵字從父結(jié)點中移除，放入新結(jié)點中，這會導(dǎo)致父結(jié)點的關(guān)鍵字?jǐn)?shù)量減 1。如果合并時父結(jié)點的關(guān)鍵字?jǐn)?shù)量為 $t-1$ ，合并后父結(jié)點就不符合B樹的要求了。

下面是合并這一過程的偽代碼如下：

// BTREE-MERGE-NODE 合并 parent 中由 splitKeyIndex 索引的
// 關(guān)鍵字作為分隔關(guān)鍵字的兩個子結(jié)點。
// parent:        將要合并的兩個結(jié)點的父結(jié)點
// splitKeyIndex: 將要合并的兩個結(jié)點的分隔關(guān)鍵字在 parent.key 中的索引
// leftNode:      將要被合并的左結(jié)點
// rightNode:     將要被合并的右結(jié)點
BTREE-MERGE-NODE(parent, splitKeyIndex, leftNode, rightNode) {
    // 簡單起見，新結(jié)點我們直接復(fù)用左孩子，
    // 這樣就不用再拷貝左孩子中的數(shù)據(jù)到 newNode 中了。
    newNode <- leftNode

    // 將父結(jié)點中的分隔關(guān)鍵字放到 newNode 中
    newNode.key[leftNode.count] <- parent.key[splitKeyIndex]

    // 將右子結(jié)點中的關(guān)鍵字和 child 拼接到 newNode 中
    // 已有的關(guān)鍵字和 child 后面
    for i <- 0; i < rightNode.count; i <- i + 1
        newNode.key[leftNode.count + 1 + i] <- rightNode.key[i]
    if not rightNode.isLeaf {
        for i <- 0; i < rightNode.count + 1; i <- i + 1 
            newNode.child[leftNode.count + 1 + i] <- rightNode.child[i]
    }

    // 設(shè)置新結(jié)點的葉子標(biāo)志和關(guān)鍵字?jǐn)?shù)量。
    // 到此新結(jié)點完全創(chuàng)建成功。
    newNode.isLeaf <- leftNode.isLeaf
    newNode.count <- leftNode.count + rightNode.count + 1

    // 現(xiàn)在 newNode 已經(jīng)初始化完畢，下面要修改父結(jié)點，
    // 一是把原來的分隔關(guān)鍵字抹掉；
    // 二是把 newNode 放入 parent 中的合適位置（即取代 leftNode 的位置）
    for i <- splitKeyIndex; i < parent.count - 1; i <- i + 1
        parent.key[i] <- parent.key[i + 1]
    for i <- splitKeyIndex + 1; i < parent.count; i <- i + 1
        parent.child[i] <- parent.child[i + 1]
    
    parent.child[splitKeyIndex] <- newNode
    parent.count <- parent.count - 1

    DISK-WRITE(newNode)
    DISK-WRITE(parent)
    // 由于 newNode 復(fù)用的 leftNode，所以這里不要刪除 leftNode
    DISK-DELETE(rightNode) 
}

這段代碼雖然稍長，但邏輯比較簡單，就不再多作解釋了。

確保結(jié)點為非最小結(jié)點

剛才我們說了，兩個結(jié)點可以合并的前提之一，是父結(jié)點的關(guān)鍵字?jǐn)?shù)量大于 $t-1$ ，即父結(jié)點不能是最小結(jié)點。但如果父結(jié)點是最小結(jié)點，又需要合并其中兩個子結(jié)點，該怎么辦呢？

其中一個辦法是先把父結(jié)點變成非最小結(jié)點，這可以通過對父結(jié)點使用前面我們已經(jīng)介紹過的挪用關(guān)鍵字或合并結(jié)點的方式實現(xiàn)；而在這個過程中如果將父結(jié)點與它的兄弟結(jié)點合并的情況，我們又需要保證父父結(jié)點為非最小結(jié)點。

可以看到，這是個方法需要回溯父結(jié)點。還記得在插入操作中，我們使用了非回溯的方式進(jìn)行插入，即在從根結(jié)點開始查找插入位置時，每遇到一個滿結(jié)點，我們就將其分裂，變成非滿結(jié)點。類似的，在刪除時我們也可以使用非回溯的方式。

使用非回溯的方式刪除關(guān)鍵字時，我們從根結(jié)點開始查找要刪除的關(guān)鍵字，每遇到一個最小結(jié)點，我們就想辦法將其變成非最小結(jié)點。這樣，當(dāng)我們想要合并某兩個兄弟結(jié)點時，它們的父結(jié)點肯定不會是最小結(jié)點，也就符合合并的要求了。

這里的關(guān)鍵是「想辦法將結(jié)點變成非最小結(jié)點」。其實使用前面我們介紹過的兩種方式：關(guān)鍵字挪用和合并，就可以讓任何一個結(jié)點變成非最小結(jié)點。由于主要方法前面已經(jīng)介紹過了，這里就不再畫示意圖了，直接看偽代碼就行了：

// BTREE-ENSURE-NON-MINNODE 確保指定的結(jié)點為非最小結(jié)點。
// 它會將代替 node 的非最小結(jié)點返回，
// 這個新的結(jié)點有可能是 node，也可能不是。
// parent:    要確保的結(jié)點的父結(jié)點
// nodeIndex: 要確保的結(jié)點在 parent.child 中的索引
// node:      要確保為非最小結(jié)點的結(jié)點
BTREE-ENSURE-NON-MINNODE(parent, nodeIndex, node) {
    if node.count > t - 1
        return node, nodeIndex
    // 根結(jié)點的關(guān)鍵字?jǐn)?shù)量可以小于 t-1，所以永遠(yuǎn)不是最小結(jié)點
    if parent == NIL 
        return node, nodeIndex

    // node 是一個最小結(jié)點，下面的操作要讓它變成一個非最小結(jié)點

    // 首先嘗試從左兄弟中挪一個關(guān)鍵字
    leftBrother <- parent.child[nodeIndex - 1]
    DISK-READ(leftBrother)
    if nodeIndex > 0 and leftBrother.count > t - 1 {
        BTREE-EXTEND-KEY-FROM-LEFT-BROTHER(parent, nodeIndex, node)
        return node, nodeIndex
    }
    
    // 嘗試從右兄弟中挪一個關(guān)鍵字
    rightBrother <- parent.child[nodeIndex + 1]
    DISK-READ(rightBrother)
    if nodeIndex < child.count and rightBrother.count > t - 1 {
        BTREE-EXTEND-KEY-FROM-RIGHT-BROTHER(parent, nodeIndex, node)
        return node, nodeIndex
    }

    // 左右兄弟都無法挪關(guān)鍵字，好合并了
    // 這里注意合并后新結(jié)點在 parent.child 中的索引
    if nodeIndex != 0 {
        // 左兄弟存在，跟左兄弟合并
        BTREE-MERGE-NODE(parent, nodeIndex - 1, leftBrother, node)
        node <- parent.child[nodeIndex - 1]
        nodeIndex <- nodeIndex - 1
    } else {
        // 沒有左兄弟，只能跟右兄弟合并
        BTREE-MERGE-NODE(parent, nodeIndex, node, rightBrother) 
        node <- parent.child[nodeIndex]
    }
    return node, nodeIndex
}

可以看到這個函數(shù)基本是將前面挪用關(guān)鍵字和合并結(jié)點兩個操作結(jié)合了起來：如果可以通過挪用關(guān)鍵字的方式保證結(jié)點為非最小結(jié)點，就優(yōu)先挪用關(guān)鍵字；否則就合并。

葉結(jié)點中刪除關(guān)鍵字

在葉結(jié)點中刪除關(guān)鍵字比較簡單，按照前面說的，只要把后續(xù)的關(guān)鍵字向前移動，覆蓋掉將要刪除的關(guān)鍵字就可以了。但前提是必須保證葉結(jié)點的不是最小結(jié)點。

刪除過程比較簡單，我們就不用示意圖了，直接看偽代碼吧：

// BTREE-DELETE-KEY-IN-LEAF 用來刪除葉子結(jié)點中的某個關(guān)鍵字。
// parent:          為葉子結(jié)點的父結(jié)點
// nodeIndex:       為葉子結(jié)點在 parent.child 中的下標(biāo)索引
// node:            為包含將要刪除關(guān)鍵字的葉子結(jié)點
// deletedKeyIndex: node.key 中將要刪除的關(guān)鍵字的下標(biāo)
// deletedKey:      為將要刪除的關(guān)鍵字的值
BTREE-DELETE-KEY-IN-LEAF(parent, nodeIndex, node, deletedKeyIndex, deletedKey) {
    // BTREE-ENSURE-NON-MINNODE 用來保證葉子結(jié)點 node 不是最小結(jié)點
    deleteFromNode, _ <- BTREE-ENSURE-NON-MINNODE(parent, nodeIndex, node)
    
    // BTREE-ENSURE-NON-MINNODE 返回的 deleteFromNode 可能
    // 并不是 node，或者是 node 但關(guān)鍵字的索引已經(jīng)發(fā)生了變化，
    // 這里要對其進(jìn)行修正。詳細(xì)說明見偽代碼后面的解釋。

    if deleteFromNode.key[deletedKeyIndex] != deletedKey
        deletedKeyIndex <- deletedKeyIndex + 1
    if deleteFromNode.key[deletedKeyIndex] != deletedKey
        deletedKeyIndex <- deleteKeyIndex - 1 + t

    // 向前移動，覆蓋掉要刪除的關(guān)鍵字
    for i <- deletedKeyIndex; i < deleteFromNode.count - 1; i <- i + 1
        deleteFromNode.key[i] <- deleteFromNode.key[i+1]

    deleteFromNode.count <- deleteFromNode.count - 1
    DISK-WRITE(deleteFromNode)
}

雖然在葉子結(jié)點中刪除關(guān)鍵字比較簡單，但我們要保證刪除之前葉子結(jié)點為非最小結(jié)點，因此我們調(diào)用了 BTREE-ENSURE-NON-MINNODE 函數(shù)。這一調(diào)用就引出了麻煩：因為這個函數(shù)可能會讓關(guān)鍵字的索引發(fā)生變化，所以我們調(diào)用后必須重新修正要刪除的關(guān)鍵字所在的索引位置。

根據(jù)上一小節(jié)的介紹， BTREE-ENSURE-NON-MINNODE 函數(shù)可能會對 node 結(jié)點作以下操作：

沒有任何操作，node 本來就是一個非最小結(jié)點
從右兄弟中挪一個關(guān)鍵字到 node 中
從左兄弟中挪一個關(guān)鍵字到 node 中
將 node 與左兄弟合并
將 node 與右兄弟合并

這五個操作中，只有第 3 和第 4 個操作會改變被刪除關(guān)鍵字的位置，使得 deleteFromNode.key[deletedKeyIndex] != deletedKey。所以我們需要對這兩種情況作修正，保證 deleteFromNode.key[deletedKeyIndex] == deletedKey 。

如果是第 3 種情況，新挪用的關(guān)鍵字會插入到 node.key[0] 的位置，而 node 中原來的關(guān)鍵字都會向右順移一位，因此只要將索引值加1，就是 deletedKey 所在的位置。所以我們使用以下代碼進(jìn)行調(diào)整：

    if deleteFromNode.key[deletedKeyIndex] != deletedKey
        deletedKeyIndex <- deletedKeyIndex + 1

我們這里只是假設(shè)是第 3 種情況，所以這個調(diào)整不一定是對的。如果調(diào)整完了還不對，那就只能是第 4 種情況。這種情況下左兄弟中的 $t-1$ 個關(guān)鍵字以及父結(jié)點中的分隔關(guān)鍵字都被插入到了 node 結(jié)點中原關(guān)鍵字的前面，所以 node 中原有的關(guān)鍵字不是向右順移了一位，而是 t 位。然而剛才處理第 3 種情況時我們已經(jīng)向右移了一位了，所以要先恢復(fù)這一次移動，再向右移 t 位。這里使用以下代碼進(jìn)行調(diào)整：

    if deleteFromNode.key[deletedKeyIndex] != deletedKey
        deletedKeyIndex <- deleteKeyIndex - 1 + t

兩次調(diào)整以后，deletedKeyIndex 中的關(guān)鍵字值肯定就是 deletedKey 了。注意如果不是第 3 或第 4 種情況，就根本不會進(jìn)入這兩個 if 分支中的任意一個。

相信這樣解釋一番以后，BTREE-DELETE-KEY-IN-LEAF 這個函數(shù)就更好理解了。其實這個函數(shù)里我們對關(guān)鍵字位置進(jìn)行調(diào)整的代碼，隱含了對 BTREE-ENSURE-NON-MINNODE 函數(shù)太多的假設(shè)，我們需要完全清楚 BTREE-ENSURE-NON-MINNODE 是怎么實現(xiàn)的，只要它有改動，我們這里的實現(xiàn)可能就要跟著改動，否則就會出錯。這種問題可不是我們寫代碼的時候想見到的。其實這里還有一種處理方法，就是在 deleteFromNode 中重新查找關(guān)鍵在所在的位置，如下偽代碼所示：

    if deleteFromNode.key[deletedKeyIndex] != deletedKey {
        deletedKeyIndex <- 0
        while deleteFromNode.key[deletedKeyIndex] != deletedKey {
            deletedKeyIndex <- deletedKeyIndex + 1
        }
    }

這樣一來，只要 BTREE-ENSURE-NON-MINNODE 能實現(xiàn)自己聲稱的功能，我們完全不關(guān)心它是如何實現(xiàn)的。缺點就是效率稍低一點（相對而言，我覺得只要不是非常頻繁的刪除，差別不會太大，并且這里還可以用二分查找增加效率）。在實際應(yīng)用中，我會更喜歡后一種實現(xiàn)。

內(nèi)結(jié)點中刪除關(guān)鍵字

下面我們來看看在內(nèi)結(jié)點中如何刪除關(guān)鍵字。由于內(nèi)結(jié)點有自己的子結(jié)點，所以直接刪除關(guān)鍵字的話，關(guān)鍵字作為子結(jié)點的分隔就會發(fā)生錯亂。因此只能用別的關(guān)鍵字替換掉想要刪除的關(guān)鍵字。那么用哪個關(guān)鍵字來替換呢？我們想一下，原來的關(guān)鍵字作為一個分隔關(guān)鍵字，它的值比左子樹中的所有值都大，比右子樹中的所有值都小。那么很自然的，左子樹中的最大值或右子樹中的最小值，都可以用來替換。

那么如何進(jìn)行替換呢？簡單來說，就是將左子樹的最大值或右子樹的最小值刪掉，然后用這個最值覆蓋掉我們想刪除的關(guān)鍵字就可以了。而左子樹的最大值或右子樹的最小值肯定都在葉結(jié)點上，將這個最值刪掉相當(dāng)于從葉結(jié)點中刪除一個關(guān)鍵字，這個我們上一小節(jié)已經(jīng)說過了。

一般而言刪除左子樹的最大值比刪除右子樹的最小值簡單一點（最大值的刪除只需將 node.count 減 1 即可，而最小值的刪除需要將 node.key[0] 后面的元素都向前移動一下），所以我們選擇使用左子樹的最大值來進(jìn)行替換。下面是在內(nèi)結(jié)點中刪除關(guān)鍵字的示意圖：

這個示意圖顯示了一種比較簡單的情況，即在左子樹中向下查找要刪除的關(guān)鍵字時，沒有發(fā)生任何挪用關(guān)鍵字或合并結(jié)點的時候，且存放左子樹最大關(guān)鍵字的葉結(jié)點也不是最小結(jié)點，可以直接刪除這個關(guān)鍵字。比較復(fù)雜的情況是，在刪除左子樹最大值時，會一直進(jìn)行結(jié)點合并，以至于刪除了左子樹的最大值以后，原本想要刪除的關(guān)鍵子已經(jīng)不在原來的結(jié)點中了，而是被合并操作合并到一個新的結(jié)點中了。

下面是在內(nèi)結(jié)點中刪除關(guān)鍵字的偽代碼：

// BTREE-DELETE-KEY-IN-INNERNODE 刪除一個內(nèi)部結(jié)點的關(guān)鍵字。
// node:            想要刪除的關(guān)鍵字所在的結(jié)點
// deletedKeyIndex: 想要刪除的關(guān)鍵字在 node.key 中的索引
// deletedKey:      想要刪除的關(guān)鍵字的值
BTREE-DELETE-KEY-IN-INNERNODE(node, deletedKeyIndex, deletedKey) {
    newKey <- BTREE-GET-MAXKEY(node.child[deletedKeyIndex])

    // 將左子樹中的最大值刪除
    // 由于調(diào)用 BTREE-DELETE-WITH-NODE 時傳入的第 3 個參數(shù)必須是
    // 非最小結(jié)點，因此我們首先調(diào)用 BTREE-ENSURE-NON-MINNODE 保證這一點
    leftChild, leftChildIndex <- 
        BTREE-ENSURE-NON-MINNODE(node, deletedKeyIndex, node.child[deletedKeyIndex])
    BTREE-DELETE-WITH-NODE(node, leftChildIndex, leftChild, newKey)

    // 刪除左子樹最大關(guān)鍵字后，原本要刪除的關(guān)鍵字的位置可能就變了，
    // 所以這里不能直接使用 deletedKeyIndex 索引要刪除的關(guān)鍵字的位置，
    // 而是要重新查找。
    node, deletedKeyIndex <- BTREE-SEARCH(node, deletedKey)
    node.key[deletedKeyIndex] <- newKey
    DISK-WRITE(node)
}

這段代碼用到了一個輔助函數(shù) BTREE-GET-MAXKEY，用來獲取子樹的最大關(guān)鍵字的值。它的偽代碼如下：

BTREE-GET-MAXKEY(root) {
    if root.isLeaf
        return root.key[root.count - 1]

    DISK-READ(root.child[root.count])
    BTREE-GET-MAXKEY(root.child[root.count])
}

非回溯刪除

上面我們討論了所有刪除過程中遇到的問題和解決方法，現(xiàn)在可以將它們匯總起來，實現(xiàn)非回溯方式刪除這一操作了。具體偽代碼如下：

// BTREE-DELETE 刪除B樹 T 中的某個關(guān)鍵字。
BTREE-DELETE(T, k) {
    BTREE-DELETE-IN-NODE(NIL, -1, root[T], k)
}

// BTREE-DELETE-WITH-NODE 刪除以 node 為代表的子樹中的關(guān)鍵字 k。
// 注意調(diào)用這個函數(shù)前，node 必須是一個非最小結(jié)點（除非它是根結(jié)點）。
BTREE-DELETE-WITH-NODE(parent, nodeIndex, node, k) {
    // 查找關(guān)鍵字的合適位置
    i <- 0
    while i < node.count and k > node.key[i]
        i <- i + 1

    // 不可能有合適的位置存儲這個關(guān)鍵字，返回
    if i >= node.count
        return

    // 找到了，刪除
    if k == node.key[i] {
        BTREE-DELETE-KEY(parent, nodeIndex, node, k, i)
        return
    }
    
    // 沒找著，但已經(jīng)到了葉子結(jié)點了，不可能有了。返回
    if node.isLeaf
        return

    // 沒找著，繼續(xù)在子結(jié)點中遞歸刪除
    // 但在繼續(xù)查找之前，要保證 node.child[i] 不是最小結(jié)點
    ENSURE-NON-MINNODE(node, i, node.child[i])
    BTREE-DELETE-WITH-NODE(node, node.child[i], k)
}

// BTREE-DELETE-KEY 刪除 node 結(jié)點中的關(guān)鍵字。
// 注意調(diào)用這個函數(shù)時，要刪除的關(guān)鍵字肯定在 node 結(jié)點中。
BTREE-DELETE-KEY(parent, nodeIndex, node, deletedKeyIndex, deletedKey) {
    if node.isLeaf
        BTREE-DELETE-KEY-IN-LEAF(parent, nodeIndex, node, deletedKeyIndex, deletedKey)
    else
        BTREE-DELETE-KEY-IN-INNERNODE(node, deletedKeyIndex, deletedKey)
}

這段偽代碼中有 3 個函數(shù)，它們基本就是把前面介紹的操作和問題解決方法串在了一起，因此這里就不再細(xì)說了。

總結(jié)

在這篇文章里，我們介紹了B樹以及它的各種操作。B樹多用于數(shù)據(jù)庫索引或文件系統(tǒng)中，在這些環(huán)境中，幾乎所有數(shù)據(jù)都存放在磁盤中，因此對數(shù)據(jù)訪問時需要盡可能地減少對磁盤的訪問次數(shù)。而B樹的特性恰好可以在非常少的訪問磁盤的情況下，進(jìn)行各種操作。

B樹的操作包含查找、插入、刪除。每種樹都有自己的「關(guān)鍵動作」，B樹也不例外。B樹的關(guān)鍵動作包含插入時的分裂結(jié)點，刪除時的合并結(jié)點、挪用關(guān)鍵字等。只要理解了這些關(guān)鍵動作，就能深刻理解B樹這種數(shù)據(jù)結(jié)構(gòu)。

限于作者水平，文章中難免有錯誤的地方，如果發(fā)現(xiàn)感謝您能不吝指正。

本文最先發(fā)表于我的博客，歡迎評論和轉(zhuǎn)載。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

B樹

B樹

引言

什么是B樹

B樹的操作

查找

插入

結(jié)點的分裂

無回溯方式插入關(guān)鍵字

刪除

從兄弟中挪用關(guān)鍵字

合并結(jié)點

確保結(jié)點為非最小結(jié)點

葉結(jié)點中刪除關(guān)鍵字

內(nèi)結(jié)點中刪除關(guān)鍵字

非回溯刪除

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

B樹

引言

什么是B樹

B樹的操作

查找

插入

結(jié)點的分裂

無回溯方式插入關(guān)鍵字

刪除

從兄弟中挪用關(guān)鍵字

合并結(jié)點

確保結(jié)點為非最小結(jié)點

葉結(jié)點中刪除關(guān)鍵字

內(nèi)結(jié)點中刪除關(guān)鍵字

非回溯刪除

總結(jié)

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av