(B樹的基本操作)

B樹

導讀

大家好，很高興又和大家見面啦！！！   在上一篇內容中，我們深入探討了B樹的 查找操作 與 樹高特性，揭示了 B樹 如何通過多路平衡結構顯著降低樹高，從而優化大規模數據存儲場景下的查詢效率。   我們特別分析了B樹的查找思想、具體過程（包括成功與失敗的場景），並推導出B樹高度與關鍵字數量及階數的數學關係：

$$ log_m(n+1) \leq h \leq log_{\lceil \frac{m}{2} \rceil}\frac{n+1}{2}+1 $$

這一公式確保了B樹在動態數據環境下仍能保持高效檢索能力。   然而，高效的查找僅是 B樹 價值的 冰山一角 。B樹 的真正強大之處在於其動態平衡能力——當插入或刪除關鍵字時，B樹 能通過分裂、合併等操作自動調整結構，維持穩定的樹高與性能。   無論是數據庫索引還是文件系統，B樹 都需要頻繁處理數據的增刪操作。那麼，B樹 如何在不破壞平衡的前提下實現這些操作？其背後的分裂與合併機制又是如何運作的？   今天，讓我們直接進入 B樹 的核心動態操作環節，探索其插入與刪除的完整流程與底層邏輯。

一、插入

在説明其具體的插入過程之前，我們需要先認識一下 B樹 中的一些概念，

1.1 基本概念

目前存在着兩種體系，這裏我們以一棵 3階B樹 為例，分別説明這兩種體系；

1.1.1 體系一：嚴蔚敏版教材

flowchart TB
	subgraph A[內部結點]
		direction TB
		a[n, p0, key1, p1, key2, p2]
		b[n, p0, key1, p1, key2, p2]
		c[n, p0, key1, p1, key2, p2]
		d[n, p0, key1, p1, key2, p2]
		a--->b
		a--->c
		a--->d
			subgraph C[終端結點]
		direction TB
			e[n, p0, key1, p1, key2, p2]
			f[n, p0, key1, p1, key2, p2]
			g[n, p0, key1, p1, key2, p2]
			h[n, p0, key1, p1, key2, p2]
		end
		b--->e
		c--->f
		c--->g
		d--->h
	end

	subgraph B[外部結點]
		direction TB
		e1[NULL]
		e2[NULL]
		e3[NULL]
		e4[NULL]
	end
	e--->e1
	f--->e2
	g--->e3
	h--->e4

這裏是將 B樹 分為了 內部結點 與 外部結點 兩大部分，而內部結點又將其細分出了 終端結點：

  • 內部結點：樹中存儲着關鍵字，且實際存在的結點
  • 外部結點：也稱為 葉子結點/空葉結點 ，結點本身不存儲任何關鍵字，僅代表查找失敗時的情況，一般為空指針
  • 終端結點：空葉結點 的直接父結點，同時也是樹中 內部結點 的最底層結點；

1.1.2 體系二：通用體系

flowchart TB
	subgraph A[內部結點]
		direction TB
		a[n, p0, key1, p1, key2, p2]
		b[n, p0, key1, p1, key2, p2]
		c[n, p0, key1, p1, key2, p2]
		d[n, p0, key1, p1, key2, p2]
		a--->b
		a--->c
		a--->d
	end
	subgraph C[終端結點/葉子結點]
		direction TB
			e[n, p0, key1, p1, key2, p2]
			f[n, p0, key1, p1, key2, p2]
			g[n, p0, key1, p1, key2, p2]
			h[n, p0, key1, p1, key2, p2]
	end
	b--->e
	c--->f
	c--->g
	d--->h

在該體系中，通用將 B樹 分為：內部結點 與 葉子結點 兩部分，只不過此時的 終端結點 等同於 葉子結點 ，它是存儲數據的最後一層結點，也是查找路徑的終點，下方連接着查找失敗時的外部結點；而 內部結點 是指所有的 非終端結點；

1.1.3 二者的區別

不管是 體系一 還是 體系二 ，均是採用的 內部結點 + 葉子結點 來構建一棵 B樹，這二者的區別就是 終端結點 的歸屬：

  • 在 體系一 中，終端結點 是 內部結點 的 最底層結點， 也是 葉子結點 的 直接父結點；
  • 在 體系二 中，終端結點 是 葉子結點，也是查找路徑的終點 ，其下方連接着查找失敗時的 外部結點；

體系二 （內部結點/終端結點二分法）在絕大多數現代數據庫、文件系統等領域的資料和工程實踐中，是絕對的主流和標準；   但是我們目前所使用的是基於 嚴蔚敏版的《數據結構》教材 所編寫的《數據結構》教材，因此這裏我們以 體系一 為準。

1.2 插入過程

在 BST 中執行插入操作時，我們是將待插入的關鍵字作為一個新的結點插入到樹中：

  • 在插入前，我們會通過查找操作，確定該結點的插入位置：
    • 查找失敗，則該失敗位置為新結點的插入位置
    • 查找成功，則不需執行插入操作
  • 當查找失敗時，該結點會作為新的葉結點插入到樹中
  • 當查找成功時，説明該樹中已經存在該關鍵字，因此無需執行插入操作

而 B樹 的插入操作相比與 BST ，其具體過程要複雜的多。其主要原因是因為 m階B樹中的結點最多可以存儲 $m - 1$ 個關鍵字 ，因此 B樹 的插入操作不再是將關鍵字作為新的結點插入到樹中，而是直接在樹的結點中插入新的關鍵字；   與 BST 的插入操作相同的是，新結點的插入一定是發送在 終端結點 中；但是在 B樹 中查找到插入的位置後，並不能簡單地將新關鍵字添加到 終端結點 中，這是因為當該結點中已經存在 $m - 1$ 個關鍵字時，此時的插入操作就會導致整棵樹不再滿足 m階B樹 的要求。   因此 B樹 的具體過程如下所示：

  • 定位：通過 查找 算法找到 新關鍵字 的插入的 終端結點（該結點一定是查找失敗時的葉結點的直接父結點）；
  • 插入：每個非根結點的關鍵字個數均在 $[\lceil \frac{m}{2} \rceil - 1, m - 1]$ 這個範圍內，因此，在插入的過程中會存在兩種情況：
    • 在結點中插入新的關鍵字後，該結點關鍵字的總數 $n$ 滿足 $n < m$ ，此時直接進行插入；
    • 在結點中插入新的關鍵字後，該結點關鍵字的總數 $n$ 滿足 $n == m$，此時需要通過 分裂 操作使結點中的關鍵字數量再一次滿足 $[\lceil \frac{m}{2} \rceil - 1, m - 1]$；

可以看到，B樹 的插入操作中會涉及一個十分重要的操作——分裂。該操作的具體方法是：

  • 取一個新結點插入到當前結點的父結點中，作為父結點的新子樹
  • 將插入了 $key$ 後的原結點從中間位置 $\lceil \frac{m}{2} \rceil$ 處將結點中的關鍵字分為三部分：
    • 左側的全部關鍵字放入原結點中
    • 右側的全部關鍵字放入新結點中
    • $\lceil \frac{m}{2} \rceil$ 處的關鍵字插入到原結點的父結點中
  • 若向父結點中插入關鍵字時導致父結點的關鍵字個數也超過了上限，則繼續對父結點進行分裂操作；
  • 分裂的過程會從 終端結點 向上傳遞，若傳遞到了根結點，此時 B樹 的高度會增加 $1$

1.3 實例説明

下面我們以一棵 3階B樹 為例，來説明 B樹 的具體插入過程。現在我們需要在一棵 空樹 中插入 [5,7,1,3,5,6,4]，其具體過程如下所示：

  • 插入關鍵字 5

由於該 3階B樹 是一棵空樹，此時我們需要創建一個新的結點，並將該結點作為根結點插入到樹中：

flowchart TB
a[n=1, p0, 5, p1, key2, p2]

此時我們就完成了第一步插入操作；

  • 插入關鍵字 7

通過查找操作，我們確定了此時的失敗結點的直接父結點為根結點，因此我們需要將該關鍵字插入到根結點中：

flowchart TB
a[n=2, p0, 5, p1, 7, p2]

由於此時的關鍵字個數 $n = 2 < m = 3$ 因此完成插入；

  • 插入關鍵字 1

通過查找操作，我們確定此時的失敗結點的直接父結點為根結點，因此我們需要將該關鍵字插入到根結點中：

flowchart TB
a[n=3, 1, p0, 5, p1, 7, p2]

由於此時的關鍵字個數 $n = 3 == m = 3$ 因此我們需要對該結點進行分裂操作：

  1. 取一個新結點插入到樹中
flowchart TB
a[n=3, 1, p0, 5, p1, 7, p2]
b[n, p0, key1, p1, key2, p2]

由於當前結點為根結點，因此我們需要再為該結點創建一個父結點作為新的根結點：

flowchart TB
a[n, p0, key1, p1, key2, p2]
b[n=3, 1, p0, 5, p1, 7, p2]
c[n, p0, key1, p1, key2, p2]
a--->b
a--->c
  1. 以 $\lceil \frac{3}{2} \rceil = 2$ 處的關鍵字為分界線將當前結點分為三部分：
    • 左側關鍵字放入原結點中
    • 右側關鍵字放入新結點中
    • $\lceil \frac{3}{2} \rceil = 2$ 處的關鍵字放入到父結點中

這裏我們需要注意的是 $\lceil \frac{3}{2} \rceil = 2$ 處的關鍵字是[1, 5, 7] 這三個關鍵字的 位序 其對應的下標應該是 i = 1，也就是關鍵字 5，因此通過分裂操作後的新樹如下所示：

flowchart TB
a[n=1, p0, 5, p1, key2, p2]
b[n=1, p0, 1, p1, key2, p2]
c[n=1, p0, 7, p1, key2, p2]
a--->b
a--->c

此時我們就完成了第一次分裂操作，由於此時是直接對 根節點 執行的分裂操作，因此 B樹 的樹高需要增加 $1$；

  • 插入關鍵字 3

通過查找操作，我們確定此時的失敗結點的直接父結點為關鍵字 1 所在的 終端結點，因此我們需要將該關鍵字插入到該結點中：

flowchart TB
a[n=1, p0, 5, p1, key2, p2]
b[n=2, p0, 1, p1, 3, p2]
c[n=1, p0, 7, p1, key2, p2]
a--->b
a--->c

由於此時該結點的關鍵字個數 $n = 2 < m = 3$ ，因此完成插入；

  • 插入關鍵字 5

通過查找操作，我們發現 5 已經存在於根結點中，因此不執行任何操作；

  • 插入關鍵字 6

通過查找操作，我們確定此時的失敗結點的直接父結點為關鍵字 7 所在的 終端結點，因此我們需要將該關鍵字插入到該結點中：

flowchart TB
a[n=1, p0, 5, p1, key2, p2]
b[n=2, p0, 1, p1, 3, p2]
c[n=2, p0, 6, p1, 7, p2]
a--->b
a--->c

由於此時該結點的關鍵字個數 $n = 2 < m = 3$ ，因此完成插入；

  • 插入關鍵字 4

通過查找操作，我們確定此時的失敗結點的直接父結點為關鍵字 7 所在的 終端結點，因此我們需要將該關鍵字插入到該結點中：

flowchart TB
a[n=1, p0, 5, p1, key2, p2]
b[n=3, p0, 1, p1, 3, p2, 4]
c[n=2, p0, 6, p1, 7, p2]
a--->b
a--->c

由於此時的關鍵字個數 $n = 3 == m = 3$ 因此我們需要對該結點進行分裂操作：

  1. 取一個新結點插入到樹中
flowchart TB
a[n=1, p0, 5, p1, key2, p2]
b[n=3, p0, 1, p1, 3, p2, 4]
c[n=0, p0, key1, p1, key2, p2]
d[n=2, p0, 6, p1, 7, p2]
a--->b
a--->c
a--->d
  1. 以 $\lceil \frac{3}{2} \rceil = 2$ 處的關鍵字為分界線將當前結點分為三部分：
    • 左側關鍵字放入原結點中
    • 右側關鍵字放入新結點中
    • $\lceil \frac{3}{2} \rceil = 2$ 處的關鍵字放入到父結點中
flowchart TB
a[n=2, p0, 3, p1, 5, p2]
b[n=1, p0, 1, p1, key2, p2]
c[n=1, p0, 4, p1, key2, p2]
d[n=2, p0, 6, p1, 7, p2]
a--->b
a--->c
a--->d

此時我們完成了第一次分裂操作，接下來我們需要檢查該結點的父結點—— 根結點 中的關鍵字個數是否滿足 $1 \leq n \leq 2$；   可以看到，此時的根節點的關鍵字個數滿足要求，因此完成插入；

二、刪除

B樹 的刪除操作與插入操作類似，但是會稍微複雜一點：

  • B樹 的插入操作只需要保證當前的插入結點中關鍵字的數量：
    • 完成插入後，當前結點的關鍵字數量滿足 $n < m$ ，則直接插入即可
    • 完成插入後，當前結點的關鍵字數量滿足 $n == m$ ，則需要 分裂 操作使其恢復 B樹 的性質—— B樹 中除根結點外，各結點中關鍵字的數量在 $[\lceil \frac{m}{2} \rceil - 1, m - 1]$ 之間
  • B樹 的刪除操作不僅需要關注當前結點中的關鍵字數量，還需要關注其兄弟結點中關鍵字的數量

接下來我們就來一起看一下 B樹 中的刪除操作是如何實現的；

2.1 刪除過程

B樹 的刪除過程可以總結為以下步驟：

  • 定位：通過查找操作，找到待刪除的目標關鍵字所在的結點：
    • 若找到了該結點，則將該結點中的目標關鍵字進行刪除
    • 若未找到該結點，則表示樹中不存在目標關鍵字，因此無需執行任何操作
  • 刪除：在進行刪除操作時，需要根據目標關鍵字的具體位置來執行相應的操作：
    • 目標關鍵字 $key$ 不在 終端結點 中，則將其轉化為刪除 終端結點 中的 $key'$
    • 目標關鍵字 $key$ 在 終端結點 中，則需要根據具體的情況進行刪除操作

簡單的理解就是 B樹 中的刪除操作與插入操作一樣，一定是發生在 終端結點 中；   那我們應該如何在 終端結點 中進行刪除操作？對於不在 終端結點 中的關鍵字，我們又應該如何刪除？   接下來我們就圍繞這兩個問題繼續深入 B樹 的刪除操作；

2.2 結點的轉換

當我們通過查找發現目標關鍵字 $key$ 不在 終端結點 中時，我們需要通過其直接前驅（或直接後繼）$key'$ 來替代目標關鍵字 $key$ ，而該直接前驅（或直接後繼）$key'$ 一定是位於 終端結點 中；

  • 直接前驅：目標關鍵字 $key$ 的左側子樹中 最右下 的元素
  • 直接後繼：目標關鍵字 $key$ 的右側子樹中 最左下 的元素
flowchart TB
a[22]
b[5, 11]
c[36, 45]
a--->b
a--->c
d[1, 3]
e[6, 8, 9]
f[13, 15]
b--->d
b--->e
b--->f
g[30, 35]
h[40, 42]
i[47, 48, 50, 56]
c--->g
c--->h
c--->i

在這棵 5階B樹 中，位於 非終端結點 的關鍵字有 $5$ 個：5, 11, 22, 36, 45。這些關鍵字的直接前驅與直接後繼如下所示：

  • 關鍵字 5 的直接前驅為關鍵字 3 ，直接後繼為關鍵字 6
  • 關鍵字 11 的直接前驅為關鍵字 9 ，直接後繼為關鍵字 13
  • 關鍵字 22 的直接前驅為關鍵字 15 ，直接後繼為關鍵字 30
  • 關鍵字 36 的直接前驅為關鍵字 35 ，直接後繼為關鍵字 40
  • 關鍵字 45 的直接前驅為關鍵字 42 ，直接後繼為關鍵字 47

這裏我們以關鍵字 22 為例，其直接前驅與直接後繼所在結點我們分別以紅色和藍色進行標註：

flowchart TB
a[22]
b[5, 11]
c[36, 45]
a--->b
a--->c
d[1, 3]
e[6, 8, 9]
f[13, 15]
b--->d
b--->e
b--->f
g[30, 35]
h[40, 42]
i[47, 48, 50, 56]
c--->g
c--->h
c--->i
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
classDef B color: white, fill: blue, stroke: blue, stroke-width: 2px
class f R
class g B

可以看到，其直接前驅位於其左側子樹的最右側的 終端結點 中，其具體位置為該結點中的 最右側元素；   其直接後繼位於其右側子樹的最左側 終端結點 中，其具體位置為該結點中的 最左側元素；   明確了關鍵字 $key$ 的替代關鍵字 $key'$ 的具體位置後，下面我們就來看一下我們應該如何執行從 非終端結點 到 終端結點 的轉換操作，這裏我們還是以刪除關鍵字 22 為例：

  • 當我們通過直接前驅來完成轉換時，我們需要通過其直接前驅 15 來直接替代關鍵字 22
flowchart TB
	subgraph tree[轉換前]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->b
		a--->c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->d
		b--->e
		b--->f
		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->g
		c--->h
		c--->i
	end
		subgraph tree1[轉換後]
		direction TB
		A[15]
		B[5, 11]
		C[36, 45]
		A--->B
		A--->C
		D[1, 3]
		E[6, 8, 9]
		F[13, 15]
		B--->D
		B--->E
		B--->F
		G[30, 35]
		H[40, 42]
		I[47, 48, 50, 56]
		C--->G
		C--->H
		C--->I
	end
	tree ---> tree1
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
classDef B color: white, fill: blue, stroke: blue, stroke-width: 2px
class a R
class f B
class A R
class F B
  • 當我們通過直接後繼來完成轉換時，我們需要通過其直接前驅 30 來直接替代關鍵字 22
flowchart TB
	subgraph tree[轉換前]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->b
		a--->c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->d
		b--->e
		b--->f
		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->g
		c--->h
		c--->i
	end
		subgraph tree1[轉換後]
		direction TB
		A[30]
		B[5, 11]
		C[36, 45]
		A--->B
		A--->C
		D[1, 3]
		E[6, 8, 9]
		F[13, 15]
		B--->D
		B--->E
		B--->F
		G[30, 35]
		H[40, 42]
		I[47, 48, 50, 56]
		C--->G
		C--->H
		C--->I
	end
	tree ---> tree1
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
classDef B color: white, fill: blue, stroke: blue, stroke-width: 2px
class a R
class g B
class A R
class G B

從上圖中我們不難發現，不管是使用直接前驅，還是直接後繼，實際上我們只需要將對應的值存儲到目標結點中來替代原關鍵字 $key$ 即可；   若無法理解 替代 這一過程，那我們也可以理解為，先刪除原關鍵字 $key$ 再插入其直接前驅或者直接後繼 $key'$ 到該結點中；   由於執行的是一次刪除 + 一次插入，因此整個 替代 過程不會破壞 B樹 的性質；  

2.3 終端結點的刪除

當我們對 B樹 執行刪除操作時，不管目標關鍵字 $key$ 是否位於 終端結點 中，最終都會在 終端結點 中完成刪除操作；   由於刪除操作會直接減少對應結點中的一個關鍵字，這就有可能導致結點中的關鍵字個數少於 $\lceil \frac{m}{2} \rceil - 1$ ，這時就破壞了 B樹 的性質，因此為了保證刪除操作後不破壞 B樹 的性質，這時我們就需要通過 借 或 合併 操作來維持 B樹 的性質；

2.3.1 刪除的三種情況

在 B樹 中，對 終端結點 進行刪除操作時，會存在 $3$ 種情況：

  • 直接刪除關鍵字：當被刪除的關鍵字所在的結點中的關鍵字個數滿足 $n \geq \lceil \frac{m}{2} \rceil$ 時，這就表明即使刪除了一個關鍵字，該結點中的關鍵字總數仍滿足 $[\lceil \frac{m}{2} \rceil - 1, m - 1]$，因此我們可以直接在該結點中刪除目標關鍵字 $key$

  • 兄弟夠借：當被刪除的關鍵字所在的結點中的關鍵字個數恰好為 $\lceil \frac{m}{2} \rceil - 1$ 時，這就表明當前結點刪除一個關鍵字後，就不再滿足 B樹 的性質，若此時與該結點相鄰的兄弟結點中的關鍵字個數滿足 $n \geq \lceil \frac{m}{2} \rceil$，這時我們就可以向該兄弟結點 借 一個關鍵字，以確保在執行刪除操作後，仍保持 B樹 的性質；

  • 兄弟不夠借：當被刪除的關鍵字所在結點中的關鍵字個數恰好為 $\lceil \frac{m}{2} \rceil - 1$ ，且與該結點相鄰的兄弟結點中的關鍵字個數均為 $\lceil \frac{m}{2} \rceil -1$ ，這就表明，當該結點刪除一個關鍵字後，會破壞 B樹 的性質，並且我們向其兄弟結點 借 了一個關鍵字後仍會破壞 B樹 的性質，在這種情況下，我們需要通過 合併 操作來保證 B樹 的性質不會被破壞

那麼我們應該如何 借 ？當不夠 借 時，我們又應該如何 合併 呢？下面我們繼續來深入探討；

2.3.2 借

所謂的 借 實際上是將兄弟結點中的關鍵字 $key1$ 刪除後插入到父結點中，並將父結點中的關鍵字 $key2$ 刪除後，插入到當前結點中。下面我們就以一棵 5階B樹 的刪除操作來説明整個借的過程：

flowchart TB
a[n = 2, key1, key2]
b[n = 2, key3, key4]
c[n = 3, key5, key6, key7]
a--->b
a--->c

在上述這棵 5階B樹 中，根據 B樹 的性質，除了根結點外，其餘結點中的結點數在 $[2, 4]$ 這個範圍中，當我們要刪除 $key4$ 時，其具體過程如下所示：

  • 直接刪除 $key4$
flowchart TB
a[n = 2, key1, key2]
b[n = 1, key3]
c[n = 3, key5, key6, key7]
a--->b
a--->c
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class b R

此時結點中只存在一個關鍵字，而與其相鄰的右兄弟結點中有 $3$ 個關鍵字，滿足 $3 > 2$ ，因此我們可以從右兄弟中借其最左側的關鍵字 $key5$；

  • 向右兄弟 借 一個關鍵字，其具體過程分為兩步：
    • 從右兄弟中刪除關鍵字 $key5$，並將其插入到父結點中
    • 從父結點中刪除最左側的關鍵字 $key1$ ，並將其插入到當前結點中
flowchart TB
	subgraph root1[第一步: 刪除 key5,並將其插入到父結點中]
		direction TB
		a[n = 3, key1, key2, key5]
		b[n = 1, key3]
		c[n = 2, key6, key7]
		a--->b
		a--->c -.->|將關鍵字key5 插入到父結點|a
	end
	subgraph root2[第二步: 刪除 key1,並將其插入到當前結點中]
		direction TB
		A[n = 2, key2, key5]
		B[n = 2, key3,  key1]
		C[n = 2, key6, key7]
		A--->B
		A--->C
		A-.->|將關鍵字key1插入到當前結點中|B
	end
	root1 ---> root2
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class b R
class B R

也就是説，雖然 借 操作是從相鄰的兄弟結點中 借 一個關鍵字，但是實際上我們是執行了兩次 借 操作：

  • 從父結點中 借 一個關鍵字插入到當前結點中
  • 從相鄰結點中 借 的關鍵字填補到父結點中

而這個 借 的關鍵字也是有要求的：

  • 從左兄弟 借 ，則需要 借 左兄弟中最右側的關鍵字
  • 從右兄弟 借 ，則需要 借 右兄弟中最左側的關鍵字

這裏就以上圖中的關鍵字為例：

  • 在刪除$key4$ 之前，各關鍵字的大小為：$key3 < key4 < key1 < key2 < key5 < key6 < key7$
  • 在刪除 $key4$ 後，關鍵字的大小順序為：$key3 < key1 < key2 < key5 < key6 < key7$

而這些關鍵字對應的結點為：

$$ \underbrace{key3}{當前結點} < \underbrace{key1 < key2}{根結點} < \underbrace{key5 < key6 < key7}_{右兄弟結點} \ $$

當我們向右兄弟 借 一個結點並將其插入到根結點中時，我們只能夠找根結點中最大關鍵字 $key2$ 的直接後繼，也就是 $key5$ ，因此完成第一次 借 後，各關鍵字的位置做出瞭如下調整：

$$ \underbrace{key3}{當前結點} < \underbrace{key1 < key2}{根結點} < \underbrace{\textcolor{red}{key5} < key6 < key7}{右兄弟結點} \\ \ \underbrace{key3}{當前結點} < \underbrace{key1 < key2 < \textcolor{red}{key 5}}{根結點} < \underbrace{key6 < key7}{右兄弟結點} $$

同理，當我們要從根結點中 借 一個關鍵字插入到當前結點中，我們也只能找 $key3$ 的直接後繼 $key1$，因此完成第二次 借 後，各關鍵字的位置做出瞭如下調整：

$$ \underbrace{key3}{當前結點} < \underbrace{\textcolor{red}{key1} < key2 < key 5}{根結點} < \underbrace{key6 < key7}{右兄弟結點} \\ \ \underbrace{key3 < \textcolor{red}{key1}}{當前結點} < \underbrace{key2 < key 5}{根結點} < \underbrace{key6 < key7}{右兄弟結點} \ $$

現在大家應該能夠理解為什麼我們是借的 $key5$ 與 $key1$ 了。若大家在後續的實戰中，還是不太明白如何 借 ，那可以像我這樣將相關結點中的關鍵字按照大小順序進行排序，並對排序後的各關鍵字進行結點劃分，這樣就能一清二楚了；   若各位不想這麼麻煩，這裏我們也給大家做一個 借 的規則總結：

  • 向右兄弟 借 ：
    • 先 借 右兄弟中的最小關鍵字，並將其插入到父結點中
    • 再 借 父結點中的最小關鍵字，並將其插入到當前結點中
  • 向左兄弟 借：
    • 先 借 左兄弟中的最大關鍵字，並將其插入到父結點中
    • 再 借 父結點中的最大關鍵字，並將其插入到當前結點中

因此我們可以將 借 的總結為六個字：左借大，右借小；

2.3.3 合併

當相鄰的左右兄弟均不夠借時，我們就需要通過 合併 來保證 B樹 的性質。   合併 顧名思義，就是將兩個結點 合併 成一個新的結點，但是，該合併過程並不是直接合並兩個結點，而是在不改變各關鍵字的先後順序的前提下，將當前結點、兄弟結點以及根結點中的關鍵字進行合併，組成新的結點，之後再對結點進行處理，使其繼續保持 B樹 的性質；   下面我們就以一棵 5階B樹 為例，説明 合併 的具體過程；

flowchart TB
	a[22]
	b[5, 11]
	c[36, 45]
	a--->b
	a--->c
	d[1, 3]
	e[6, 8, 9]
	f[13, 15]
	b--->d
	b--->e
	b--->f
	g[30, 35]
	h[40, 42]
	i[47, 48, 50, 56]
	c--->g
	c--->h
	c--->i

在這棵 5階B樹 中，除根節點外，其餘結點中的關鍵字數量需要保證在 $[2, 4]$ 這個範圍內；   假設我們需要刪除關鍵字 35 。從圖中我們不難發現，關鍵字 35 所在的結點以及與其相鄰的兩個兄弟結點中關鍵字的數量均為 $2$ ；   也就是説，當我們刪除 35 這個關鍵字後，當前結點中的關鍵字數量就已經不滿足 B樹 的要求，並且我們也無法從兄弟結點中 借；   在這種情況下，我們就需要通過 合併 操作來保證刪除後的 B樹 仍滿足 B樹 的性質。其具體過程如下：

  • 刪除關鍵字 35
flowchart TB
	a[22]
	b[5, 11]
	c[36, 45]
	a--->b
	a--->c
	d[1, 3]
	e[6, 8, 9]
	f[13, 15]
	b--->d
	b--->e
	b--->f
	g[30]
	h[40, 42]
	i[47, 48, 50, 56]
	c--->g
	c--->h
	c--->i
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class g R

此時的樹已經不再滿足 B樹 的性質，因此我們需要選擇當前結點與其兄弟結點進行 合併；

  • 合併 兄弟結點

合併 操作中的合併對象一定是 相同父結點的兄弟結點 ，因此，對於當前結點而言，與其相鄰的且父結點相同的兄弟結點只有一個右兄弟結點，因此我們進行合併的對象一定是 右兄弟；   在合併的過程中，我們需要將當前結點、右兄弟結點，以及這兩個結點中間的位於父結點中的關鍵字 36 進行合併，形成一個新的結點：

flowchart TB
	a[22]
	b[5, 11]
	c[45]
	a--->b
	a--->c
	d[1, 3]
	e[6, 8, 9]
	f[13, 15]
	b--->d
	b--->e
	b--->f
	g[30, 36, 40, 42]
	i[47, 48, 50, 56]
	c--->g
	c--->i
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class g R

可以看到，合併後得到的新結點滿足 B樹 的性質：$n \leq m - 1$ ，因此該結點無需做出任何調整，合併完成；   但是我們會發現，此時該結點的父結點中的關鍵字個數不再滿足 B樹 的性質，因此我們需要將 合併 操作向上傳遞，也就是對當前結點的父結點進行合併操作：

flowchart TB
	a[22]
	b[5, 11]
	c[45]
	a--->b
	a--->c
	d[1, 3]
	e[6, 8, 9]
	f[13, 15]
	b--->d
	b--->e
	b--->f
	g[30, 36, 40, 42]
	i[47, 48, 50, 56]
	c--->g
	c--->i
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class c R

從圖中我們可以看到，45 所在的結點的具有相同父結點的兄弟結點只有該結點的左兄弟結點，因此我們需要將當前結點、左兄弟結點，以及位於父結點的兩個結點中間的關鍵字進行合併，組成新的結點：

flowchart TB
	a[NULL]
	b[5, 11, 22, 45]
	a--->b
	d[1, 3]
	e[6, 8, 9]
	f[13, 15]
	b--->d
	b--->e
	b--->f
	g[30, 36, 40, 42]
	i[47, 48, 50, 56]
	b--->g
	b--->i
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class b R

在此次的 合併 操作完成後，我們發現新結點的父結點中不存在任何關鍵字，此時我們只需要將其刪除，使新結點成為新的根結點即可：

flowchart TB
	b[5, 11, 22, 45]
	d[1, 3]
	e[6, 8, 9]
	f[13, 15]
	b--->d
	b--->e
	b--->f
	g[30, 36, 40, 42]
	i[47, 48, 50, 56]
	b--->g
	b--->i
classDef R color: white, fill: red, stroke: red, stroke-width: 2px
class b R

在完成本次的處理後，此時該棵 5路查找樹 再一次恢復了 B樹 的性質，並且樹的高度由原來的 $h = 3$ 降至 $h = 2$；

三、插入與刪除小結

在 m階B樹 中，不管是 插入 還是 刪除 均有以下共同點：

  • 最終的操作均是在 終端結點 上執行
  • 完成 終端結點 的操作後，還需要繼續向上傳遞，直至樹中的所有結點中的關鍵字個數均滿足 $[\lceil \frac{m}{2} \rceil - 1, m - 1]$

不過這兩種操作還是會存在不同之處：

  • 樹高的變化不同：
    • 插入 操作可能會導致樹高 $+ 1$
    • 刪除 操作可能會導致樹高 $- 1$
  • 保持平衡的操作不同：
    • 插入 操作通過 分裂 保持 B樹 的 絕對平衡
    • 刪除 操作通過 借 和 合併 保持 B樹 的 絕對平衡

在 插入 操作中，分裂 是將一個結點分裂為兩個結點，並且可能會產生新的根結點；   在 刪除 操作中，借 的規則是 左借大，右借小 ，合併 則是將兩個結點以及位於父結點中的兩個結點中間的關鍵字 合併 成一個新的結點，並且可能會直接刪除原先的根結點；

結語

通過本文的詳細探討，我們系統性地掌握了B樹兩大核心動態操作——插入與刪除的完整機制。讓我們回顧一下其中的關鍵知識點：   🔄 核心操作流程回顧   B樹 的插入與刪除操作均遵循嚴格的平衡維護原則。

  • 插入操作始於 終端結點 的精準定位，通過 結點分裂 機制（以$\lceil \frac{m}{2} \rceil$ 為分界點將關鍵字分為三部分）維持B樹的平衡特性。當分裂向上傳播至根節點時，會導致樹高增加。
  • 而刪除操作則通過關鍵字替換（將非終端結點的刪除轉化為終端結點處理）、借位操作（遵循“左借大，右借小”原則）以及 結點合併 三種策略應對不同情況，確保刪除後仍滿足 B樹 的嚴格定義。

⚖️ 平衡機制對比分析   插入與刪除操作在維持B樹平衡方面展現出不同的特性：

  • 插入操作通過主動分裂來預防節點溢出，是向上生長的過程；
  • 而刪除操作則通過借位與合併來修復下溢，是向下調整的過程。

這種差異直接體現在樹高變化上：

  • 插入可能導致樹高增加
  • 刪除則可能導致樹高降低

值得注意的是，所有操作最終都在 終端結點 完成，並通過向上傳遞的鏈式反應確保整棵樹的平衡性。   💡 實際應用價值   B樹通過這些精心設計的操作機制，在外存數據管理（如數據庫索引和文件系統）中展現出巨大優勢。   其低樹高特性顯著減少了磁盤I/O次數，而動態平衡能力則確保了數據操作的高效穩定。   理解這些底層機制，對於設計高性能存儲系統和進行數據庫優化具有重要指導意義。   📚 知識體系整合   本文與前期討論的B樹查找操作和樹高特性形成了完整知識體系。   從靜態查找到動態維護，我們已全面掌握了B樹這一重要數據結構的核心原理，為後續學習B+樹等衍生結構奠定了堅實基礎。   互動與分享

  • 點贊👍 - 您的認可是我持續創作的最大動力

  • 收藏⭐ - 方便隨時回顧這些重要的基礎概念

  • 轉發↗️ - 分享給更多可能需要的朋友

  • 評論💬 - 歡迎留下您的寶貴意見或想討論的話題

感謝您的耐心閲讀！我們下一篇再見！