Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree.

Presentation on theme: "Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree."— Presentation transcript:

1 Chapter 11 B-tree 11.1 m-way 搜尋樹 11.2 B-tree

2 B-tree B-tree的功能非常強大，有許多資料庫系統皆採用B-tree來儲存與刪除其資料。

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 。

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搜尋樹。

5 11.1 m-way搜尋樹 例如有一3-way的搜尋樹，其中有12個鍵值分別為12, 17, 23, 25, 28, 32, 38, 45, 48, 55, 60, 70。 表為圖11-1中每個節點之3-way的搜尋樹表示法。

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。

7 11.1 m-way搜尋樹 m-way搜尋樹的加入

8 11.1 m-way搜尋樹

9 11.1 m-way搜尋樹

10 11.1 m-way搜尋樹

11 11.1 m-way搜尋樹 m-way搜尋樹的刪除 而在刪除方法上則與二元搜尋樹極為相同，若刪除非樹葉節點上的鍵值，則以左子樹中最大的鍵值或右子樹中的最小鍵值取代之。

12 11.1 m-way搜尋樹 刪除3則直接刪除之：

13 11.1 m-way搜尋樹 刪除8： 刪除12：

14 11.1 m-way搜尋樹 刪除7： 刪除10：

15 11.2 B-tree 一棵order為m的B-tree是一m-way搜尋樹。若是空樹，也算B-tree，假若高度 > 1必須滿足以下的特性： 樹根至少有二個子節點（children），亦即節點內至少有一鍵值（key value）。 除了樹根外，所有節點至少有個子節點，至多有m個子節點。此表示至少應有 - 1個鍵值，至多有m-1個鍵值（表示大於m/2的最小正整數）。 所有的樹葉節點皆在同一階層。

16 11.2 B-tree

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。

18 11.2 B-tree 11.2.1 B-tree 的加入 假設加入P節點，若 該節點少於m-1個鍵值。
該節點的鍵值已等於m-1，則將此節點分為二，因為一棵order為m的B-tree，最多只能有m-1個鍵值。

19 11.2 B-tree 請看下例之說明（此處的B-tree為order 5）

20 11.2 B-tree 加入88於圖11-3

21 11.2 B-tree 承(1)加入98

22 11.2 B-tree 承(2)加入91

23 11.2 B-tree 承(3)加入93

24 11.2 B-tree 承(4)加入99

25 11.2 B-tree B-tree的刪除 B-tree的刪除與2-3 tree和2-3-4 tree的刪除基本上原理是相同的，此處也分成兩部份： 刪除的節點是樹葉節點（leaf node）， 刪除的節點為非樹葉節點（non-leaf node）。

26 11.2 B-tree 以B-tree of order 5如圖11-4來說明。

27 11.2 B-tree 若刪除的節點是樹葉節點 如將圖11-4刪除70

28 11.2 B-tree 如欲將圖11-4中的鍵值26刪除

29 11.2 B-tree 若欲刪除85

30 11.2 B-tree 有一棵B-tree of order 5如圖11-5所示

31 11.2 B-tree 先從圖11-5刪除59

32 11.2 B-tree 由於合併後c節點僅存放一個鍵值，不符合B-tree的定義

33 11.2 B-tree 若刪除的節點為非樹葉節點

34 11.2 B-tree 若刪除圖11-6的鍵值50，找到p'節點為g，從中取出最小值52，並代替50。

35 11.2 B-tree 若再刪除52

36 11.2 B-tree 承上圖，若繼續刪除55

37 11.2 B-tree 由於g節點其鍵值數少於 個鍵值，且其兄弟節點h也沒有大於 個鍵值，故將g、h、與c的鍵值65合併於g節點，結果如下圖：

38 11.2 B-tree 此時c節點的鍵值數也少於 ，且其兄弟節點的鍵值數不大於 ，故將b、c與a節點合併，結果如下：