1、資料結構資料結構 - 使用使用 C 語言語言 2B-tree的功能非常強大,有許多資料庫系統皆採用B-tree來儲存與刪除其資料。資料結構資料結構 - 使用使用 C 語言語言 3何謂m-waw搜尋樹(m-way search tree)?一棵m-way搜尋樹,所有節點的分支度(dgree)均小於或等於m。若T為空樹,則T亦稱為m-way搜尋樹,倘若T不是空樹,則必須具備下列的性質:n節點的型態是n, A0, (K1, A1), (K2, A2),.,(Kn, An) 其中Ai是子樹的指標 0 i n m; n為節點上的鍵值數,Ki是鍵值1 i n 及 1 n m 。資料結構資料結構 - 使用使
2、用 C 語言語言 4n節點中的鍵值是由小至大排列的,因此 Ki Ki+1,1 i n。n子樹Ai的所有鍵值均小於鍵值Ki+1但大於Ki , 0 i 1必須滿足以下的特性:n樹根至少有二個子節點(children),亦即節點內至少有一鍵值(key value)。n除了樹根外,所有節點至少有個子節點,至多有m個子節點。此表示至少應有 - 1個鍵值,至多有m-1個鍵值(表示大於m/2的最小正整數)。n所有的樹葉節點皆在同一階層。資料結構資料結構 - 使用使用 C 語言語言 16資料結構資料結構 - 使用使用 C 語言語言 17在圖11-2中(a)不屬於B-tree of order 3,因為樹葉節點
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。資料結構資料結構 - 使用使用 C 語言語言 1811.2.1 B-tree 的加入假設加入P節點,若n該節點少於m-1個鍵值。n該節點的鍵值已等於m-1,則將此節點分為二,因為一棵order為m的B-tree,最多只能有m-1個鍵值。資料結構資料結構 - 使用使用 C 語言語言 19請看下
4、例之說明(此處的B-tree為order 5)資料結構資料結構 - 使用使用 C 語言語言 20加入88於圖11-3資料結構資料結構 - 使用使用 C 語言語言 21承(1)加入98資料結構資料結構 - 使用使用 C 語言語言 22承(2)加入91資料結構資料結構 - 使用使用 C 語言語言 23承(3)加入93資料結構資料結構 - 使用使用 C 語言語言 24承(4)加入99資料結構資料結構 - 使用使用 C 語言語言 2511.2.2 B-tree的刪除B-tree的刪除與2-3 tree和2-3-4 tree的刪除基本上原理是相同的,此處也分成兩部份:n刪除的節點是樹葉節點(leaf n
5、ode),n刪除的節點為非樹葉節點(non-leaf node)。資料結構資料結構 - 使用使用 C 語言語言 26以B-tree of order 5如圖11-4來說明。資料結構資料結構 - 使用使用 C 語言語言 27如將圖11-4刪除70資料結構資料結構 - 使用使用 C 語言語言 28n如欲將圖11-4中的鍵值26刪除資料結構資料結構 - 使用使用 C 語言語言 29n若欲刪除85資料結構資料結構 - 使用使用 C 語言語言 30n有一棵B-tree of order 5如圖11-5所示資料結構資料結構 - 使用使用 C 語言語言 31先從圖11-5刪除59資料結構資料結構 - 使用使
6、用 C 語言語言 32由於合併後c節點僅存放一個鍵值,不符合B-tree的定義資料結構資料結構 - 使用使用 C 語言語言 33資料結構資料結構 - 使用使用 C 語言語言 34若刪除圖11-6的鍵值50,找到p節點為g,從中取出最小值52,並代替50。資料結構資料結構 - 使用使用 C 語言語言 35若再刪除52資料結構資料結構 - 使用使用 C 語言語言 36承上圖,若繼續刪除55資料結構資料結構 - 使用使用 C 語言語言 37由於g節點其鍵值數少於 個鍵值,且其兄弟節點h也沒有大於 個鍵值,故將g、h、與c的鍵值65合併於g節點,結果如下圖:資料結構資料結構 - 使用使用 C 語言語言 38此時c節點的鍵值數也少於 ,且其兄弟節點的鍵值數不大於 ,故將b、c與a節點合併,結果如下: