1、資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 2B-tree的功能非常強(qiáng)大，有許多資料庫(kù)系統(tǒng)皆採(cǎi)用B-tree來儲(chǔ)存與刪除其資料。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 3何謂m-waw搜尋樹(m-way search tree)？一棵m-way搜尋樹，所有節(jié)點(diǎn)的分支度（dgree）均小於或等於m。若T為空樹，則T亦稱為m-way搜尋樹，倘若T不是空樹，則必須具備下列的性質(zhì)：n節(jié)點(diǎn)的型態(tài)是n, A0, (K1, A1), (K2, A2),.,(Kn, An) 其中Ai是子樹的指標(biāo) 0 i n m; n為節(jié)點(diǎn)上的鍵值數(shù)，Ki是鍵值1 i n 及 1 n m 。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使

2、用 C 語(yǔ)言語(yǔ)言 4n節(jié)點(diǎn)中的鍵值是由小至大排列的，因此 Ki Ki+1，1 i n。n子樹Ai的所有鍵值均小於鍵值Ki+1但大於Ki ， 0 i 1必須滿足以下的特性：n樹根至少有二個(gè)子節(jié)點(diǎn)（children），亦即節(jié)點(diǎn)內(nèi)至少有一鍵值（key value）。n除了樹根外，所有節(jié)點(diǎn)至少有個(gè)子節(jié)點(diǎn)，至多有m個(gè)子節(jié)點(diǎn)。此表示至少應(yīng)有 - 1個(gè)鍵值，至多有m-1個(gè)鍵值（表示大於m/2的最小正整數(shù)）。n所有的樹葉節(jié)點(diǎn)皆在同一階層。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 16資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 17在圖11-2中(a)不屬於B-tree of order 3，因?yàn)闃淙~節(jié)點(diǎn)

3、不在同一階層上，而(b)是屬於B-tree of order 3，因?yàn)樗械臉淙~節(jié)點(diǎn)皆在同一階層。B-tree of order 3表示除了樹葉節(jié)點(diǎn)外每一節(jié)點(diǎn)的分支度（degree）不是等於2就是等於3，因此B-tree of order 3就是著名的2-3 tree。假使m=4，則是2-3-4 tree。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 1811.2.1 B-tree 的加入假設(shè)加入P節(jié)點(diǎn)，若n該節(jié)點(diǎn)少於m-1個(gè)鍵值。n該節(jié)點(diǎn)的鍵值已等於m-1，則將此節(jié)點(diǎn)分為二，因?yàn)橐豢胦rder為m的B-tree，最多只能有m-1個(gè)鍵值。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 19請(qǐng)看下

4、例之說明（此處的B-tree為order 5）資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 20加入88於圖11-3資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 21承(1)加入98資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 22承(2)加入91資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 23承(3)加入93資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 24承(4)加入99資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 2511.2.2 B-tree的刪除B-tree的刪除與2-3 tree和2-3-4 tree的刪除基本上原理是相同的，此處也分成兩部份：n刪除的節(jié)點(diǎn)是樹葉節(jié)點(diǎn)（leaf n

5、ode），n刪除的節(jié)點(diǎn)為非樹葉節(jié)點(diǎn)（non-leaf node）。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 26以B-tree of order 5如圖11-4來說明。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 27如將圖11-4刪除70資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 28n如欲將圖11-4中的鍵值26刪除資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 29n若欲刪除85資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 30n有一棵B-tree of order 5如圖11-5所示資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 31先從圖11-5刪除59資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 32由於合併後c節(jié)點(diǎn)僅存放一個(gè)鍵值，不符合B-tree的定義資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 33資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 34若刪除圖11-6的鍵值50，找到p節(jié)點(diǎn)為g，從中取出最小值52，並代替50。資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 35若再刪除52資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 36承上圖，若繼續(xù)刪除55資料結(jié)構(gòu)資料結(jié)構(gòu) - 使用使用 C 語(yǔ)言語(yǔ)言 37由於g節(jié)點(diǎn)其鍵值數(shù)少於 個(gè)鍵值，且其兄弟節(jié)點(diǎn)h也沒有大於 個(gè)鍵值，故將g、h