一個節點儲存多個分隔鍵
二叉搜尋樹每個節點只儲存一個鍵。B 樹則在一個節點中放多個已排序鍵,相鄰鍵之間及兩端各有一個子樹區間,因此一次讀取節點就能在多棵子樹之間選擇。當讀取整個鍵區塊,比多次獨立儲存存取便宜時,這種安排尤其有用。
分支多本身不保證樹矮。B 樹同時要求最低填充量,並使全部葉節點深度相同。插入新鍵時,既要騰出空間,也要保留全部條件。本節使用由上而下插入:進入已滿子節點之前先分裂它,使每次遞歸開始時都有可用空間。
抽象物件是具全序的互異鍵集合。contains(x) 測試成員關係,insert(x) 在 未存在時加入它。本節的重複插入不只保持集合不變,也保持樹結構不變。若鍵要附帶值,或容許多重集合,便須另訂規則。
相等判定及 LOWER_BOUND 的比較,必須與同一全序一致。下方 CPU 模型把一次鍵比較或鍵/指標搬動計為常數工作。
固定最小度的約定
定義 8.1.1
(最小度為 t 的 B 樹)
固定整數 。每棵完成操作後的樹符合以下不變量:
- 含 個鍵的節點,鍵嚴格遞增。它要麼沒有子節點,稱為葉;要麼恰有 個子節點。
- 每個非根節點有 至 個鍵。非空根有 1 至 個鍵。空樹只有一個不含鍵的葉根節點。
- 每棵子樹全部鍵,都落在節點相鄰鍵所指定的區間。若鍵為 ,子節點 0 只含小於 的鍵; 的子節點 只含嚴格介乎 的鍵;子節點 只含大於 的鍵。
- 全部葉深度相同,深度計由根到葉的邊數。
含 個鍵的節點稱為已滿。非根內部節點至少有 個子節點,至多 個。 時,節點可含一、二或三個鍵,常稱為 2–3–4 樹。
不同教材對 B 樹「階數」的用法未必相同,本節一律明訂最小度 。2–3 樹只容許每個節點一或兩個鍵,與這裏 的容量約定不同。
分隔鍵本身也是已儲存集合成員,包括內部節點的鍵,不是必須另外在葉保留一份的副本。B+ 樹的記錄放置約定不同,不能把它的葉副本規則直接搬入本節算法。
每步只搜尋一個區間
LOWER_BOUND(keys,x) 傳回第一個不小於 x 的鍵索引;若全部鍵較小,則傳回陣列長度。鍵與子節點都用從零開始的索引。
CONTAINS(node, x):
i = LOWER_BOUND(node.keys, x)
if i < number of node.keys and node.keys[i] == x:
return true
if node is a leaf:
return false
return CONTAINS(node.children[i], x)
證明透視
為何不用搜尋其他子樹
若節點內有鍵等於 ,便已找到集合成員,即使此節點是內部節點也一樣。否則 lower bound 找出 唯一可能所在的區間。由範圍不變量,其他每棵子樹只含嚴格位於該區間以外的鍵。
只進入該子節點,便保留「若 已儲存且尚未找到,它就在此子樹」的陳述。到葉仍不相等,即證明不存在。每次遞歸在有限樹中下降一層,故搜尋終止。
父節點有空間時,分裂已滿子節點
假設父 少於 個鍵,其索引 子節點 已滿,鍵為 。把中位鍵 升至父的索引 。 保留 ,新右兄弟 接收 。兩個子節點現在各有 個鍵。
若 是內部節點,舊的 個子節點也須分開: 保留索引 , 接收 。搬動的是整棵子樹,其內部結構不變。若 原本是葉,分裂後兩者仍是葉。
SPLIT_CHILD(P, i): // P has room; child i is full
Y = P.children[i]
median = Y.keys[t-1]
Z = a new node with the same leaf status as Y
Z.keys = a copy of Y.keys[t .. 2t-2]
if Y is not a leaf:
Z.children = Y.children[t .. 2t-1]
Y.children = Y.children[0 .. t-1]
Y.keys = Y.keys[0 .. t-2]
insert median into P.keys at index i
insert Z into P.children at index i+1
陣列切片表示建立所列的新陣列;改左節點時,不能意外擦掉右節點仍需要的數據。P.children[i] 仍指左節點 。中位鍵從被分裂的 移除,只在 儲存一次,左右兩個結果子節點都不保留它。
引理 8.1.2
(分裂已滿子節點)
設在最小度為 的 B 樹中,節點 至多有 個鍵,其子節點 已滿。執行 SPLIT_CHILD(P, i) 後:儲存的鍵集合不變; 與新兄弟 各有 個鍵; 多一個鍵、多一個子節點;次序與區間條件全部成立; 之下每個葉的深度不變。
證明
(分裂保留集合、區間與平衡深度)
的鍵分成左鍵、中位鍵及右鍵,因此每個舊鍵仍恰好出現一次。兩個子節點各有 個鍵,符合範圍。父鍵數增加一,但原本有空間,故不超過 。父子節點數也增加一,保留「子節點數等於鍵數加一」。
每個左鍵小於中位鍵,每個右鍵大於中位鍵。內部節點的首 個舊子區間屬左,餘下 個屬右。原子樹整體已位於 的適當相鄰鍵之間,插入其中位鍵後,父的其他區間仍有效。
兩個替代節點位於舊子節點的同一層,其後代子樹搬動時高度不變,因此每個葉保留原深度。分裂改變分支及鍵的位置,卻保持所表示集合與平衡葉層。
概念視角結構
分裂重新分組,但不改變鍵的次序
把一棵子樹依次列出:子樹 、鍵 、子樹 、鍵 ,如此類推,每個子樹以同樣方式展開。由區間不變量可知,這樣讀出的恰是全部鍵的遞增序列。分裂不改變這個序列:原本在 兩半之間的中位鍵,現在位於父節點中 與 之間。改變的只是序列如何分組成節點。
常見錯誤
(把中位鍵留在被分裂的節點)
把中位鍵寫入父節點,卻沒有從 移除,該鍵便被存了兩次。取 、,若 仍留在 ,左節點為 ,右節點為 ,父節點鍵為 。子節點 0 只應含嚴格小於其分隔鍵的鍵,現在卻含有 ;而且 有 個鍵,並非 個。中位鍵是升上去:離開 ,在 中只儲存一次。把分隔鍵複製進葉是 B+ 樹的約定,不適用於這裏。
包括根在內,都先分裂再下降
先搜尋新鍵;此成員搜尋不修改任何樹節點,確保重複插入在任何結構修改之前就結束並保持樹不變。因此下方輔助程序有兩個前提:新鍵不在整棵樹中;接受調用的節點未滿。
INSERT(x):
if CONTAINS(root, x):
return false
if root is full:
oldRoot = root
root = a new internal node with no keys and child [oldRoot]
SPLIT_CHILD(root, 0)
INSERT_NONFULL(root, x)
return true
INSERT_NONFULL(node, x):
i = LOWER_BOUND(node.keys, x)
if node is a leaf:
insert x into node.keys at index i
return
if node.children[i] is full:
SPLIT_CHILD(node, i)
if x > node.keys[i]:
i = i + 1
INSERT_NONFULL(node.children[i], x)
分裂後,與剛升起的中位鍵比較,決定去左還是右。相等不可能發生,因為插入前 不存在,而分裂不產生新鍵。
常見錯誤
(沿用分裂前選定的子節點下降)
取 ,父節點 ,已滿的中間子節點 ,插入 。分裂前 LOWER_BOUND 給出 。分裂把 升起,父節點變為 ,索引 1、2 的子節點為 與 。若程式碼仍用 ,就會把 放入 ,得到 ,位於分隔鍵 之下。之後搜尋 時,與 比較會走向子節點 2,即 ,結果錯誤地回報不存在。分裂後須拿 與升起的中位鍵比較, 較大便把 加一。
暫時沒有鍵的新根,是緊接分裂之前的工作記錄。分裂後它有一鍵兩子,符合完成樹不變量。只有根分裂會增加高度:全部舊葉同時加深一層。
反例模式
分裂已滿父節點的子節點
有人會以為,不論父節點如何,已滿的子節點都可以分裂。取 ,已滿的父節點 及其已滿的子節點 。分裂會升起 ,父節點便成為 ,有四個鍵,但 。引理要求父節點有空位。下降時先分裂已滿的子節點才進入,保證所進入的每個節點都未滿;沒有父節點的根,則在一個新根之下分裂。
定理 8.1.3
(由上而下插入是正確的)
設最小度為 的 B 樹表示有限集合 , 為一個鍵。若 ,INSERT(x) 回傳 false 且不改變任何東西;否則回傳 true,所得之樹是表示 的最小度 B 樹。
證明
(沿下降路徑歸納)
若 ,成員測試在修改任何節點之前就返回。否則,根分裂是上述分裂引理在「父節點沒有鍵」時的一個實例,所以之後樹仍然是 的有效表示,且根未滿。其後每次分裂同樣是引理的實例,保留集合及全部不變量,而遞歸總是進入未滿節點。每次分裂後都拿 與新的分隔鍵比較,因此所選子區間含有 。最後在葉中按 LOWER_BOUND 位置放入 ,鍵仍嚴格遞增,該葉至多有 個鍵。所以樹表示 ,並符合所有不變量。
證明透視
為何由上而下插入不會使節點溢出
輔助程序開始時,根未滿:要麼原本未滿,要麼剛換成一鍵新根。每個內部調用所選子節點,要麼本來未滿,要麼先分裂再下降。父在進入時未滿,所以能接收該次升鍵;之後父可能已滿,但此次插入只從它下降一次,不需再向它升第二個鍵。
遞歸再次進入未滿節點,最終到達至多有 個鍵的葉;加入一鍵後至多 。範圍比較把鍵放入正確區間;全部分裂保留舊集合及平衡深度。所以結果恰表示舊集合加上 ,並符合全部不變量,不需要把溢出沿遞歸向上傳。
最小度二的完整插入追蹤
例題 8.1.4
(在 t = 2 時依次插入 1 至 10)
由空葉根開始,每個節點至多放三鍵。
| 插入鍵 | 之後的根 | 葉插入前的結構事件 |
|---|---|---|
| 1 | [1] | 無 |
| 2 | [1,2] | 無 |
| 3 | [1,2,3] | 無 |
| 4 | [2] | 分裂已滿根,升起 2 |
| 5 | [2] | 無 |
| 6 | [2,4] | 分裂右子節點,升起 4 |
| 7 | [2,4] | 無 |
| 8 | [2,4,6] | 分裂最右子節點,升起 6 |
| 9 | [4] | 分裂已滿根,升起 4,再把 9 插成 [7,8,9] |
| 10 | [4] | 分裂孫節點 [7,8,9],升起 8,再把 10 插成 [9,10] |
插入 4 後:
[2]
/ \
[1] [3,4]
插入 8 後:
[2,4,6]
/ | | \
[1] [3] [5] [7,8]
插入 10 後:
[4]
/ \
[2] [6,8]
/ \ / | \
[1] [3] [5] [7] [9,10]
第九次插入時,舊根已滿,儘管目標葉仍有空間,所選算法仍先分裂根。它保持 B 樹不變量,卻不保證在同一集合的所有表示中高度最小。
下面的互動圖逐次原子分裂地重播這段插入紀錄及其他紀錄,並以 B 樹的不變量檢查每個顯示的快照。
例題 8.1.5
(重複鍵與已滿的根(t = 2))
設根是已滿的葉 。調用 INSERT(2) 時,先執行 CONTAINS,在索引 1 找到 並回傳 true,所以 INSERT 回傳 false,已滿的根原封不動,完全沒有分裂。
調用 INSERT(4) 時, 不存在。根已滿,於是建立帶有子節點 的新空根並分裂:中位鍵 升起,留下子節點 與 。在根 上執行 INSERT_NONFULL,LOWER_BOUND 給出 ;子節點 未滿,不需再分裂, 直接插入該葉。結果是根 ,葉為 與 ,與上面追蹤中的樹相同。兩次調用的差別只在成員測試:只有鍵不存在時才發生結構改變。
最低填充量給出對數高度界
定理 8.1.6
(高度與鍵數的關係)
設非空且最小度為 的 B 樹高度為 (計邊數),鍵數為 。則
證明
(逐層計算節點數)
時,根至少一鍵兩子,每個非根內部節點至少有 個子節點。因此第 層至少有 個節點,各至少有 個鍵。逐層相加,
時,同一下界只是 。由 取對數,得 。
另一極端,第 層至多有 個節點,各至多 個鍵,所以 。這些界計的是鍵數,不只是節點數;空葉根另行處理。
反例模式
不能放棄葉深度相同這一條
有人聲稱,只要每個非根節點有 至 個鍵,即使各葉深度不同,也已經有 。取 ,根 有子節點 與 ,而 有子節點 與 。每個節點都只有一個鍵,每個內部節點的子節點數都比鍵數多一,區間條件也成立。可是最長路徑有 條邊而 ,而該界要求 。把此模式向右延續,可得 個鍵、高度為 ,高度與 成線性。不變量 4 正是迫使每條由根到葉的路徑都有完整層數的條件。
例題 8.1.7
(t = 3、40 個鍵時,高度可以是多少?)
定理要求 。 時下界是 ,所以高度不可能是 3 或以上。 時上界是 ,所以高度不可能至多為 1。 時兩界為 。因此每棵最小度為 3、有 40 個鍵的 B 樹,高度恰好是 2。
邊界情況是 : 的上界 ,只有根有五個鍵、六個葉各有五個鍵才能取到。再多一個鍵,即 ,就已迫使 。
每節點線性掃描時,搜尋比較次數為 。二分搜尋可降至 ,但陣列插入及分裂仍可能搬動 個鍵或指標。直接插入算法連同成員預查,最壞 CPU 工作量為 ,所以是 。固定 時為 。成員預查與插入是兩次下降,常數倍不改變上述界。
選 時,須使滿節點的 個鍵及 個子參照可裝入一個儲存區塊。此模型下,由根到葉下降會讀 個區塊。一次分裂在該層只觸及常數個節點區塊,因此插入連寫入及預查也需 區塊存取。分裂可能寫父及左右結果子節點,共常數個區塊;即使不重用預查讀過的區塊,兩次下降仍保持相同漸近界。這不表示在一區塊內搜尋或重排全部鍵是常數 CPU 工作;表示與成本模型須一併說明。
刪除另需借鍵、合併及可能縮根,恢復最低填充量,不能把上述葉插入直接反轉當作完成。本節證明與追蹤只涵蓋搜尋及插入。
有解練習
快速檢查
(1. 分裂內部節點時也要分配子節點)
設 。父鍵為 [5,60],索引 1 的中間子節點已滿,鍵為 [10,20,30,40,50],依次有子節點 。分裂後,求父鍵、左右鍵陣列及它們各自的子節點清單。
解答 · 解答 1
升起中位鍵 30,父變為 [5,30,60]。左節點 [10,20] 配 ;新右節點 [40,50] 配 。兩者各有 鍵及 子。父原本另外兩個外側子節點不變。30 只在父儲存一次,不複製入左右子。
快速檢查
(2. 搜尋內部鍵、葉鍵與不存在的鍵)
用最終十鍵樹追蹤 2、7、11 的成員查詢,列出檢查的節點鍵陣列及各搜尋停止的理由。
解答 · 解答 2
搜尋 2:走 [4] 再走 [2],相等即證存在,不必繼續下降。搜尋 7:走 [4]、[6,8]、[7] 並找到。搜尋 11:走 [4]、[6,8]、[9,10];葉鍵全較小,沒有子節點可再搜,所以傳回假。
快速檢查
(3. 高度界不保證最低高度)
時,高度二的樹可只含六鍵嗎?雖然追蹤結果高二,集合 能否也有合法的高度一表示?
解答 · 解答 3
高度二至少需要 鍵,故六鍵不可能。十鍵集合可用根 [3,6,9],葉子節點 [1,2]、[4,5]、[7,8]、[10],在高度一符合全部填充量及範圍條件。由上而下分裂保證正確平衡,不保證該集合的最矮配置。
快速檢查
(4. 父可在下降之前變滿)
設 ,父鍵為 [10,30],中間已滿葉為 [12,18,25]。父未滿,其餘樹結構合法。用輔助程序插入未存在的 20,求新父及中間區域的葉。再解釋公開操作重複 insert(20) 會怎樣。
解答 · 解答 4
先分裂,升起 18,父變為 [10,18,30],兩葉為 [12] 及 [25]。因 ,下降右葉,插入成 [20,25]。父雖已滿仍合法,此次操作不再需向它升鍵。重複公開插入先找到 20,在任何分裂前傳回假,所以即使根已滿也不改動。