资料结构-使用C语言2B-tree课件.ppt

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節點合併，結果如下：