资料结构-使用C语言2B-tree课件.ppt
Chapter 11 B-tree,11.1 m-way 搜尋樹11.2 B-tree,資料結構-使用 C 語言 2,B-treeB-tree的功能非常強大，有許多資料庫系統皆採用B-tree來儲存與刪除其資料。,資料結構-使用 C 語言 3,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。,資料結構-使用 C 語言 4,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搜尋樹。,資料結構-使用 C 語言 5,11.1 m-way搜尋樹,例如有一3-way的搜尋樹，其中有12個鍵值分別為12,17,23,25,28,32,38,45,48,55,60,70。表為圖11-1中每個節點之3-way的搜尋樹表示法。,資料結構-使用 C 語言 6,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。,資料結構-使用 C 語言 7,11.1 m-way搜尋樹,11.1.1 m-way搜尋樹的加入,資料結構-使用 C 語言 8,11.1 m-way搜尋樹,資料結構-使用 C 語言 9,11.1 m-way搜尋樹,資料結構-使用 C 語言 10,11.1 m-way搜尋樹,資料結構-使用 C 語言 11,11.1 m-way搜尋樹,11.1.2 m-way搜尋樹的刪除而在刪除方法上則與二元搜尋樹極為相同，若刪除非樹葉節點上的鍵值，則以左子樹中最大的鍵值或右子樹中的最小鍵值取代之。,資料結構-使用 C 語言 12,11.1 m-way搜尋樹,刪除3則直接刪除之：,資料結構-使用 C 語言 13,11.1 m-way搜尋樹,刪除8：刪除12：,資料結構-使用 C 語言 14,11.1 m-way搜尋樹,刪除7：刪除10：,資料結構-使用 C 語言 15,11.2 B-tree,一棵order為m的B-tree是一m-way搜尋樹。若是空樹，也算B-tree，假若高度 1必須滿足以下的特性：樹根至少有二個子節點（children），亦即節點內至少有一鍵值（key value）。除了樹根外，所有節點至少有個子節點，至多有m個子節點。此表示至少應有-1個鍵值，至多有m-1個鍵值（表示大於m/2的最小正整數）。所有的樹葉節點皆在同一階層。,資料結構-使用 C 語言 16,11.2 B-tree,資料結構-使用 C 語言 17,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。,資料結構-使用 C 語言 18,11.2 B-tree,11.2.1 B-tree 的加入假設加入P節點，若該節點少於m-1個鍵值。該節點的鍵值已等於m-1，則將此節點分為二，因為一棵order為m的B-tree，最多只能有m-1個鍵值。,資料結構-使用 C 語言 19,11.2 B-tree,請看下例之說明（此處的B-tree為order 5）,資料結構-使用 C 語言 20,11.2 B-tree,加入88於圖11-3,資料結構-使用 C 語言 21,11.2 B-tree,承(1)加入98,資料結構-使用 C 語言 22,11.2 B-tree,承(2)加入91,資料結構-使用 C 語言 23,11.2 B-tree,承(3)加入93,資料結構-使用 C 語言 24,11.2 B-tree,承(4)加入99,資料結構-使用 C 語言 25,11.2 B-tree,11.2.2 B-tree的刪除B-tree的刪除與2-3 tree和2-3-4 tree的刪除基本上原理是相同的，此處也分成兩部份：刪除的節點是樹葉節點（leaf node），刪除的節點為非樹葉節點（non-leaf node）。,資料結構-使用 C 語言 26,11.2 B-tree,以B-tree of order 5如圖11-4來說明。,資料結構-使用 C 語言 27,11.2 B-tree,若刪除的節點是樹葉節點如將圖11-4刪除70,資料結構-使用 C 語言 28,11.2 B-tree,如欲將圖11-4中的鍵值26刪除,資料結構-使用 C 語言 29,11.2 B-tree,若欲刪除85,資料結構-使用 C 語言 30,11.2 B-tree,有一棵B-tree of order 5如圖11-5所示,資料結構-使用 C 語言 31,11.2 B-tree,先從圖11-5刪除59,資料結構-使用 C 語言 32,11.2 B-tree,由於合併後c節點僅存放一個鍵值，不符合B-tree的定義,資料結構-使用 C 語言 33,11.2 B-tree,若刪除的節點為非樹葉節點,資料結構-使用 C 語言 34,11.2 B-tree,若刪除圖11-6的鍵值50，找到p節點為g，從中取出最小值52，並代替50。,資料結構-使用 C 語言 35,11.2 B-tree,若再刪除52,資料結構-使用 C 語言 36,11.2 B-tree,承上圖，若繼續刪除55,資料結構-使用 C 語言 37,11.2 B-tree,由於g節點其鍵值數少於 個鍵值，且其兄弟節點h也沒有大於 個鍵值，故將g、h、與c的鍵值65合併於g節點，結果如下圖：,資料結構-使用 C 語言 38,11.2 B-tree,此時c節點的鍵值數也少於，且其兄弟節點的鍵值數不大於，故將b、c與a節點合併，結果如下：,
