Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree
B-tree B-tree的功能非常強大,有許多資料庫系統皆採用B-tree來儲存與刪除其資料。
11.1 m-way搜尋樹 何謂m-waw搜尋樹(m-way search tree)? 一棵m-way搜尋樹,所有節點的分支度(dgree)均小於或等於m。若T為空樹,則T亦稱為m-way搜尋樹,倘若T不是空樹,則必須具備下列的性質: 節點的型態是n, A0, (K1, A1), (K2, A2),...,(Kn, An) 其中Ai是子樹的指標 0 ≤ i ≤ n < m; n為節點上的鍵值數,Ki是鍵值1 ≤ i ≤ n 及 1 ≤ n < m 。
11.1 m-way搜尋樹 節點中的鍵值是由小至大排列的,因此 Ki < Ki+1,1 ≤ i< n。 子樹Ai的所有鍵值均小於鍵值Ki+1但大於Ki , 0 < i < n。 子樹An的所有鍵值均大於Kn,而且子樹A0的所有鍵值小於K1。 Ai指到的子樹,0 ≤ i ≤ n亦是m-way搜尋樹。
11.1 m-way搜尋樹 例如有一3-way的搜尋樹,其中有12個鍵值分別為12, 17, 23, 25, 28, 32, 38, 45, 48, 55, 60, 70。 表為圖11-1中每個節點之3-way的搜尋樹表示法。
11.1 m-way搜尋樹 由於3-way搜尋榼,每個節點的型態是n, A0, (K1, A1), (K2, A2),...,(Kn, An),因此a節點的格式為 2, b, (23, c), (48, d) 表示a節點有2個鍵值,在b節點中的所有鍵值均小於23,在c節點中的每個鍵值大小介於23與48之間,最後d節點的所有鍵值均大於48。
11.1 m-way搜尋樹 11.1.1 m-way搜尋樹的加入
11.1 m-way搜尋樹
11.1 m-way搜尋樹
11.1 m-way搜尋樹
11.1 m-way搜尋樹 11.1.2 m-way搜尋樹的刪除 而在刪除方法上則與二元搜尋樹極為相同,若刪除非樹葉節點上的鍵值,則以左子樹中最大的鍵值或右子樹中的最小鍵值取代之。
11.1 m-way搜尋樹 刪除3則直接刪除之:
11.1 m-way搜尋樹 刪除8: 刪除12:
11.1 m-way搜尋樹 刪除7: 刪除10:
11.2 B-tree 一棵order為m的B-tree是一m-way搜尋樹。若是空樹,也算B-tree,假若高度 > 1必須滿足以下的特性: 樹根至少有二個子節點(children),亦即節點內至少有一鍵值(key value)。 除了樹根外,所有節點至少有個子節點,至多有m個子節點。此表示至少應有 - 1個鍵值,至多有m-1個鍵值(表示大於m/2的最小正整數)。 所有的樹葉節點皆在同一階層。
11.2 B-tree
11.2 B-tree 在圖11-2中(a)不屬於B-tree of order 3,因為樹葉節點不在同一階層上,而(b)是屬於B-tree of order 3,因為所有的樹葉節點皆在同一階層。 B-tree of order 3表示除了樹葉節點外每一節點的分支度(degree)不是等於2就是等於3,因此B-tree of order 3就是著名的2-3 tree。假使m=4,則是2-3-4 tree。
11.2 B-tree 11.2.1 B-tree 的加入 假設加入P節點,若 該節點少於m-1個鍵值。 該節點的鍵值已等於m-1,則將此節點分為二,因為一棵order為m的B-tree,最多只能有m-1個鍵值。
11.2 B-tree 請看下例之說明(此處的B-tree為order 5)
11.2 B-tree 加入88於圖11-3
11.2 B-tree 承(1)加入98
11.2 B-tree 承(2)加入91
11.2 B-tree 承(3)加入93
11.2 B-tree 承(4)加入99
11.2 B-tree 11.2.2 B-tree的刪除 B-tree的刪除與2-3 tree和2-3-4 tree的刪除基本上原理是相同的,此處也分成兩部份: 刪除的節點是樹葉節點(leaf node), 刪除的節點為非樹葉節點(non-leaf node)。
11.2 B-tree 以B-tree of order 5如圖11-4來說明。
11.2 B-tree 若刪除的節點是樹葉節點 如將圖11-4刪除70
11.2 B-tree 如欲將圖11-4中的鍵值26刪除
11.2 B-tree 若欲刪除85
11.2 B-tree 有一棵B-tree of order 5如圖11-5所示
11.2 B-tree 先從圖11-5刪除59
11.2 B-tree 由於合併後c節點僅存放一個鍵值,不符合B-tree的定義
11.2 B-tree 若刪除的節點為非樹葉節點
11.2 B-tree 若刪除圖11-6的鍵值50,找到p'節點為g,從中取出最小值52,並代替50。
11.2 B-tree 若再刪除52
11.2 B-tree 承上圖,若繼續刪除55
11.2 B-tree 由於g節點其鍵值數少於 個鍵值,且其兄弟節點h也沒有大於 個鍵值,故將g、h、與c的鍵值65合併於g節點,結果如下圖:
11.2 B-tree 此時c節點的鍵值數也少於 ,且其兄弟節點的鍵值數不大於 ,故將b、c與a節點合併,結果如下: