【數據結構】考研408 | B樹探秘：從查找操作到樹高性能分析詳情 - 考研,數據結構,408,C,C++,後端開發,yyds乾貨盤點蒙奇D索隆博客

(B樹的查找與樹高)

導讀

大家好，很高興又和大家見面啦！！！在上一篇內容中我們初步認識了 多路查找樹、多路平衡查找樹 以及 B樹；在 多路平衡查找樹 這個大家族中，B樹就是其最經典的代表，因此我們不僅要認識 B樹，我們還有了解該數據結構的一系列基本操作。對於一個數據結構而言，在其基本操作：增、刪、改、查中，最核心的操作就是查找；而對於 樹形結構 而言，其查找操作與 樹的高度 掛鈎；因此在今天的內容中，我們將會詳細介紹 B樹的查找操作以及不同情況下 B樹的高度，下面就讓我們直接進入今天的內容；

一、查找

B樹的查找與 BST 很相似，只是每個結點都是多個關鍵字的有序表，在每個結點上所作的不是兩路分支決定，而是根據該結點的子樹所做的多路分支決定。

1.1 查找思想

B樹的查找思想並不複雜，具體步驟如下：

從根結點開始查找目標關鍵字或關鍵字所在範圍：
- 若當前關鍵字大於目標關鍵字，則繼續查找當前關鍵字的左側指針指向的子樹
- 若當前關鍵字小於目標關鍵字：
  - 當前關鍵字的右側還存在關鍵字，則繼續順序查找
  - 當前關鍵字的右側不存在關鍵字，則繼續查找當前關鍵字的右側指針指向的子樹
- 若當前關鍵字等於目標關鍵字，則查找成功
找到目標關鍵字所在子樹後，繼續按照上述步驟繼續查找：
- 若找到了目標關鍵字，則查找成功
- 若當前子樹為空樹，則説明查找失敗

這裏我個人的看法是，該查找過程可以視為是一棵複合的 BST 的查找過程，這裏我解釋一下什麼是複合，下面我以一棵 3階B樹 為例進行説明：

flowchart LR
	subgraph BT[3階B樹]
		direction TB
		root[n, p0, key1, p1, key2, p2]
		sub1[子樹1]
		sub2[子樹2]
		sub3[子樹3]
		root ---> sub1
		root ---> sub2
		root ---> sub3
	end
	subgraph BST1
		direction TB
		root1[key1]
		sub_1[子樹1]
		sub_2[子樹2]
		root1--->|p0|sub_1
		root1--->|p1|sub_2
	end
	subgraph BST2
		direction TB
		root2[key2]
		sub_3[子樹2]
		sub_4[子樹3]
		root2--->|p1|sub_3
		root2--->|p2|sub_4
	end
	BST1 --->|+|BST2 --->|複合成|BT

在結點中的順序查找過程可以我們可以視為 查找目標所在的 BST ：

當前關鍵字 $key_i$ 對應的是 BST 的根結點 root
當前關鍵字的左側指針 $p_{i -1}$ 對應的是 BST 的左子樹指針 lchild
當前關鍵字的右側指針 $p_i$ 對應的是 BST 的右子樹指針 rchild

當我們確定了目標所在的 BST 後，我們再根據 BST 的查找規則繼續查找 目標關鍵字：

當前關鍵字等於目標關鍵字，則查找成功
當前關鍵字小於目標關鍵字，則視情況進行查找：
- 當前關鍵字右側仍存在關鍵字，則繼續向右順序查找
- 當前關鍵字右側不存在關鍵字，則查找以當前關鍵字為根的 BST 的右子樹指針
當前關鍵字大於目標關鍵字，則查找以當前關鍵字為根的 BST 的左子樹指針

這裏可能大家會好奇，為什麼小於時，是直接查找子樹？而大於時，則需要看具體的情況？這是因為在結點內的查找我們採用的是從左到右的順序查找，而結點內的元素是按從左到右升序排列，即 $key_0 < key_1 < \cdots < key_{m - 1}$；因此當目標關鍵字 $key$ 比當前關鍵字 $key_i$ 小時，説明目標關鍵字大於當前關鍵字左側的所有關鍵字，但是小於當前關鍵字，即 $key_0 < \cdots < key_{i - 1} < \textcolor{red}{key} < key_i$；所以在這種情況下，我們只需要直接查找以 $key_i$ 為根結點的 BST 的左子樹（$p_{i - 1}$ 指向的子樹）即可；

PS: 這部分提到的 BST 指的是 m階B樹 中一棵近似的 BST ，而不是 m階B樹 中真正存在一棵 BST；這裏大家一定要清楚，不要弄混了

B樹的查找包含兩個基本操作：

在 B樹中找結點
在結點中找關鍵字

B樹常存儲在磁盤上，因此前一查找操作實在磁盤上進行，後一查找操作則是在內存中進行，即 B樹的查找操作是先在磁盤上找到目標結點後，再將結點信息讀入內存，最後在內存中通過順序查找或者折半查找找到目標關鍵字。因此，在磁盤上進行查找的次數即目標結點在B樹上的層次數，決定了 B樹的查找效率。

1.2 查找過程

下面我們以一棵 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
d--->d1[NULL]
d--->d2[NULL]
d--->d3[NULL]
b--->e
e--->e1[NULL]
e--->e2[NULL]
e--->e3[NULL]
b--->f
f--->f1[NULL]
f--->f2[NULL]
f--->f3[NULL]
g[30, 35]
h[40, 42]
i[47, 48, 50, 56]
c--->g
g--->g1[NULL]
g--->g2[NULL]
g--->g3[NULL]
c--->h
h--->h1[NULL]
h--->h2[NULL]
h--->h3[NULL]
c--->i
i--->i1[NULL]
i--->i2[NULL]
i--->i3[NULL]
i--->i4[NULL]
i--->i5[NULL]

這裏我們以查找關鍵字 10 與關鍵字 48 為例，分別説明查找失敗與查找成功兩個場景；其具體的查找過程可以分為兩步：

從磁盤中讀取當前結點到內存中

在開始對 B樹進行查找時，磁盤中會有一個指針指向樹中的各個結點，而計算機在查找該結點時，不能直接在磁盤中進行查找，而是通過將磁盤中的指針指向的當前結點讀取到內存後，再對內存中的結點進行查找操作；

在內存中查找關鍵字

當完成了第一步從磁盤讀取結點數據到內存後，正在的查找操作就會在內存中執行。由於 B樹中各結點中的數據是一個升序順序表，因此在內存中查找目標關鍵字是否存在與當前結點中時，可以採用的查找操作既可以是 順序查找 也可以是 折半查找 ；

返回查找結果

在查找的過程中，會先判斷當前讀取的結點是否為 空葉結點：

為 空葉結點 ，則查找失敗
為 非空葉結點 ，繼續執行具體的查找方案

不管是用 順序查找 還是 折半查找 ，最終都只會存在3種結果：

當前關鍵字等於目標關鍵字：$key_i == \textcolor{red}{key}$ ，查找成功
當前關鍵字小於目標關鍵字：$key_i < \textcolor{red}{key}$ ，繼續查找該關鍵字的右側指針 $p_i$ 指向的子樹
當前關鍵字大於目標關鍵字：$key_i > \textcolor{red}{key}$ ，繼續查找該關鍵字的左側指針 $p_{i - 1}$ 指向的子樹

這裏我們需要注意，內存中的查找結果一定是當前結點的最終查找結果：

完成了關鍵字的查找——查找成功或者查找失敗
確定了關鍵字的具體範圍

下面我們就以查找關鍵字 10 和關鍵字 48 為例進行説明；

1.2.1 查找失敗

當我們在查找關鍵字 10 時，其具體過程如下所示：

首先我們會從磁盤中讀取根結點到內存中：

flowchart TB
	subgraph BT[磁盤]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[內存]
		n[22]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class a R

通過內存中的 順序/折半查找 最終確定了關鍵字的範圍：$10 < 22$ ；確定了具體範圍後，會繼續從磁盤中讀取該結點中的 $p0$ 指針指向的子樹：

讀取 $p_0$ 指向的子樹根結點到內存中

flowchart TB
	subgraph BT[磁盤]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[內存]
		n[5, 11]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class b R

通過內存中的 順序/折半查找 最終確定了關鍵字的範圍：$5 < 10 < 11$ ；確定了具體範圍後，會繼續從磁盤中讀取該結點中的 $p_1$ 指針指向的子樹：

讀取 $p_1$ 指向的子樹根結點到內存中

flowchart TB
	subgraph BT[磁盤]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e
		e--->|p0|e1[NULL]
		e--->|p1|e2[NULL]
		e--->|p2|e3[NULL]
		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[內存]
		n[6, 8, 9]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class e R

通過內存中的 順序/折半查找 最終確定了關鍵字的範圍：$9 < 10$ ；確定了具體範圍後，會繼續從磁盤中讀取該結點中的 $p_2$ 指針指向的子樹：

讀取 $p_2$ 指向的子樹根結點到內存中

flowchart TB
	subgraph BT[磁盤]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e
		e--->|p0|e1[NULL]
		e--->|p1|e2[NULL]
		e--->|p2|e3[NULL]
		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[內存]
		n[NULL]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class e3 R

由於當前結點為 空葉結點 ，這就表示樹中不存在關鍵字 10 ，因此本次查找失敗；

1.2.2 查找成功

當我們在查找關鍵字 48 時，其具體過程如下所示：

首先我們會從磁盤中讀取根結點到內存中：

flowchart TB
	subgraph BT[磁盤]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[內存]
		n[22]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class a R

通過內存中的 順序/折半查找 最終確定了關鍵字的範圍：$22 < 48$ ；確定了具體範圍後，會繼續從磁盤中讀取該結點中的 $p1$ 指針指向的子樹：

讀取 $p_1$ 指向的子樹根結點到內存中

flowchart TB
	subgraph BT[磁盤]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[內存]
		n[36, 45]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class c R

通過內存中的 順序/折半查找 最終確定了關鍵字的範圍：$45 < 48$ ；確定了具體範圍後，會繼續從磁盤中讀取該結點中的 $p_2$ 指針指向的子樹：

讀取 $p_2$ 指向的子樹根結點到內存中

flowchart TB
	subgraph BT[磁盤]
		direction TB
		a[22]
		b[5, 11]
		c[36, 45]
		a--->|p0|b
		a--->|p1|c
		d[1, 3]
		e[6, 8, 9]
		f[13, 15]
		b--->|p0|d

		b--->|p1|e

		b--->|p2|f

		g[30, 35]
		h[40, 42]
		i[47, 48, 50, 56]
		c--->|p0|g

		c--->|p1|h

		c--->|p2|i

	end
	subgraph Node[內存]
		n[47, 48, 50, 56]
	end
	BT--->Node
classDef R color: black, fill: red, stroke: red, stroke-width: 2px
class i R

通過內存中的 順序/折半查找 最終在該結點中找到了關鍵字 48 ，因此查找成功；

二、樹高

從查找的過程我們不難發現，B樹的整個查找過程與磁盤的存取次數息息相關；在查找中，從磁盤中讀取 B樹的結點次數，與結點所在層次相同：

關鍵字 22 所在結點位於樹的第一層，從磁盤中讀取該結點時，讀取的總次數為 $1$ 次
關鍵字 48 所在結點位於樹的第三層，從磁盤中讀取該結點時，讀取的總次數為 $3$ 次

換句話説，當我們要查找的關鍵字所在的結點層次越高，對應的 B樹的高度也就越高，相應的，查找操作中所進行的磁盤存取次數也就越多；這麼看來，對 B樹進行查找操作時，所需的磁盤存取次數與 B樹的高度成正比；因此，當一棵 B樹的高度越低時，其查找的效率也就越高。接下來，我們就來一起分析一下 B樹在不同情況下的高度。

PS: 這裏我們探討的 B樹的高度是 不包括空葉結點 的高度；當然，在某些情況下，B樹的高度指的是 包含空葉結點 的高度；因此 B樹的具體高度還是得看具體的情況；

若 $n \geq 1$ ，則對任意一棵包含 $n$ 個關鍵字、高度 $h$ 、階數 $m$ 的 B樹，在關鍵字總數一定的情況下，其高度 $h$ 與關鍵字的個數 $n$ 以及階數 $m$ 之間的關係如下：

每個結點中的關鍵字個數達到最多，此時容納相同數量關鍵字的 B樹的高度達到最小。

這是因為，對於 $m階B樹$ 而言，每個結點中均可容納 $m - 1$ 個關鍵字，因此每個結點均有 $m$ 棵子樹。當每個結點的關鍵字數量最多時，説明此時的 B樹可以視為一棵滿樹，那麼各層的關鍵字個數為：

第一層：有 $1$ 個結點，每個結點中有 $m - 1$ 個關鍵字，共有 $1 * (m - 1)$ 個關鍵字
第二層：有 $m$ 個結點，每個結點中有 $m - 1$ 個關鍵字，共有 $m * (m - 1)$ 個關鍵字
第三層：有 $m^2$ 個結點，每個結點中有 $m - 1$ 個關鍵字，共有 $m^2 * (m - 1)$ 個關鍵字
$\cdots$
第 $h$ 層：有 $m^{h - 1}$ 個結點，每個結點中有 $m - 1$ 個關鍵字，共有 $m^{h - 1} * (m - 1)$ 個關鍵字

現在我們就能算得關鍵字的總個數 $n$ 應該滿足：

$$ \begin{align*} n &\leq (m - 1) * (1 + m + m^2 + \cdots + m^{h - 1} \ n &\leq (m - 1) * \frac{m ^h - 1}{m - 1} \ n &\leq m ^ h - 1 \ \log_m (n + 1) &\leq h \end{align*} $$

每個結點中的關鍵字個數達到最少，此時容納同樣多關鍵字的 B樹的高度達到最大。

這是因為，根據 B樹的性質，每一層的結點個數以及關鍵字總數分別為：

第一層：有 $1$ 個結點，且結點中至少有 $1$ 個關鍵字，其關鍵字總數為 $1$
第二層：有 $2$ 個結點，且結點中至少有 $\lceil \frac{m}{2} \rceil - 1$ 個關鍵字，其關鍵字總數為 $2 * (\lceil \frac{m}{2} \rceil - 1)$
第三層：有 $2 * (\lceil \frac{m}{2} \rceil)$ 個結點，且結點中至少有 $\lceil \frac{m}{2} \rceil - 1$ 個關鍵字，其關鍵字總數為 $2 * (\lceil \frac{m}{2} \rceil) * (\lceil \frac{m}{2} \rceil - 1)$
第四層：有 $2 * (\lceil \frac{m}{2} \rceil)^2$ 個結點，且結點中至少有 $\lceil \frac{m}{2} \rceil - 1$ 個關鍵字，其關鍵字總數為 $2 * (\lceil \frac{m}{2} \rceil)^2 * (\lceil \frac{m}{2} \rceil - 1)$
$\cdots$
第 $h$ 層：有 $2 * (\lceil \frac{m}{2} \rceil)^{h - 2}$ 個結點，且結點中至少有 $\lceil \frac{m}{2} \rceil - 1$ 個關鍵字，其關鍵字總數為 $2 * (\lceil \frac{m}{2} \rceil)^{h - 2} * (\lceil \frac{m}{2} \rceil - 1)$

現在我們就能算得關鍵字的總個數應該滿足：

$$ \begin{align*} n &\geq 1 + (1 + \lceil \frac{m}{2} \rceil + \lceil \frac{m}{2} \rceil^{2} + \cdots + \lceil \frac{m}{2} \rceil^{h - 2}) * 2 * (\lceil \frac{m}{2} \rceil - 1) \ n &\geq 1 + \frac{\lceil \frac{m}{2} \rceil^{h - 1} - 1}{\lceil \frac{m}{2} \rceil - 1} * 2 * (\lceil \frac{m}{2} \rceil - 1) \ n &\geq 2 * \lceil \frac{m}{2} \rceil ^ {h - 1} - 1 \ n + 1 &\geq 2 * \lceil \frac{m}{2} \rceil ^ {h - 1} \ \frac{n + 1}{2} &\geq \lceil \frac{m}{2} \rceil ^ {h - 1} \ \log_{\lceil \frac{m}{2} \rceil} \frac{n + 1}{2} &\geq h - 1 \ \log_{\lceil \frac{m}{2} \rceil} \frac{n + 1}{2} + 1 &\geq h \end{align*} $$

此時我們就得到了一棵關鍵字個數為 $n$ 的 $m階B樹$ 的高度 $h$ 的具體範圍：

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

結語

通過本文的探討，我們系統性地剖析了 B樹查找操作 的核心機制與性能特點。 B樹作為一種高效的 多路平衡查找樹，其設計精髓在於通過多路分支和節點平衡，顯著降低樹高，從而優化大規模數據存儲場景下的查詢效率。 📌 核心知識點回顧

查找操作的本質

B樹的查找是一個在 磁盤I/O 與 內存計算 之間交替的過程：

首先在磁盤上通過路徑導航定位目標節點（次數等於節點所在層次）
再將節點讀入內存進行關鍵字比較。
每個節點內的關鍵字有序排列，通過 順序或二分查找 確定目標關鍵字或目標關鍵字所在子樹：
- 若在某節點找到目標關鍵字則立即返回成功；
- 若到達葉子節點仍未找到則返回失敗。

樹高與性能的數學關係

B樹通過多路平衡設計確保樹高被嚴格限制在對數範圍內。對於包含 $n$ 個關鍵字的 m階B樹，其高度 $h$ 滿足：

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

這一性質保證了即使數據量極大，查找時的磁盤I/O次數仍可控制在極低水平。 3. 節點內查找的決策邏輯

節點內的查找可視為一個 動態的順序比較過程。查找從節點的第一個關鍵字開始，將目標關鍵字與節點內的關鍵字依次進行有序比較，每次比較會立即導向一個明確的決策：

若等於當前關鍵字則成功返回；
若小於當前關鍵字則轉入左側子樹；
若大於當前關鍵字則繼續與下一個關鍵字比較。

此過程逐步縮小搜索範圍，直至定位目標或確定路徑。 🌟 下篇預告 在掌握了B樹高效的查找邏輯後，我們將在下一篇文章中深入解析 B樹的插入與刪除操作，探討其如何通過節點分裂、合併與關鍵字旋轉等機制動態維持平衡結構。 互動與分享

點贊👍 - 您的認可是我持續創作的最大動力
收藏⭐ - 方便隨時回顧這些重要的基礎概念
轉發↗️ - 分享給更多可能需要的朋友
評論💬 - 歡迎留下您的寶貴意見或想討論的話題

感謝您的耐心閲讀！關注博主，不錯過更多技術乾貨。我們下一篇再見！

蒙奇D索隆博客

蒙奇D索隆博客

博客 / 詳情