B+ Tree.

Presentation on theme: "B+ Tree."— Presentation transcript:

1 B+ Tree

2 definition B+ tree of order m 由兩個level所組成： Index level 及Data level 所組成
所有Data均存在於Data Blocks on Data Level, Data Blocks之間以Link list串連 Index Block主要是依據key,配合索引,找到對應的Data Block 而Index Block及Data Block中的Degree數必須符合B tree of order m的規定 B+ Tree (balanced Tree)：所有樹葉到樹根的距離都相同 每個節點有 +m/2T～ ｍ個子女（樹根除外） 所有樹葉都在同一層（樹根到樹葉的深度皆相同） 具有n個子女非樹葉節點有n-1個鍵 可以support ISAM (Index Sequential Access Method),主要用在external search,SORT上

3 例：

4 B 與 B+ tree 的比較 B+_tree在定義上與B_tree不同，圖2畫出一個B+_Tree的例子，在B+_Tree中，只有葉節點的索引記錄才含有資料指標，其餘的節點中僅含有單純的索引值，請注意圖1中B_tree的情況是與此不同的。 為何要有B+_Tree呢? 由於B+_Tree的內節點（Internal node）不含資料指標，每個節點能存放的索引數目會比較多，相對地樹狀結構的層級數目就少一點，減少了資料方塊存取的數目，所以在實際的應用上，仍以B+_Tree較為多見。 圖1 圖2 8 6 , 9 9 , 10 6 1, 4 6, 7 8 9 10,13 1, 4 7, 8 10,13

5 Creat a B+ tree 插入的順序為 : 9, 6, 1, 8, 4, 13, 10, 7 6 6 , 8 6, 9 1 6, 9 1 6 8, 9 8 6 , 8 9 6 1, 4 6 8, 9 1, 4 6 8 9,13

6 8 9 , 10 6 1, 4 6 8 9 10,13 8 9 , 10 6 1, 4 6, 7 8 9 10,13

7 Insert a key Insert a key into a leaf which still has some room (not overflow). Put the keys of this leaf in order. No changes are made in the index level. insert 4 6 6 1 6, 9 1, 4 6, 9

8 If a key is inserted into a full leaf (overflow)
Split, the new leaf node is included in the sequence set, keys are distributed evenly between the old and the new leaves, and the first key from the new node is copied (not moved, as in B-tree) 6 Insert 10 Insert 3 6 6, 9 3 6, 9 9,10 1, 4 6, 9 1, 4 6 1 3, 4 6 9,10 The parent is not full The parent is full

9 Delete a key Delete a key from a leaf leading to no underflow
Delete the leaf and keep remaining keys in order index level 可刪可不刪 6, 9 delete 4 6, 9 9,10 1, 4 6 9,10 1 6 delete 9 6, 10 6, 9 10 10 1, 4 6 1, 4 6

10 Delete a key from a leaf causes an underflow Rotation or Combination
6 6 delete 1 3 6, 9 4 6, 9 1 3, 4 6 9,10 3 4 6 9,10 delete 6 6, 9 1 3, 4 9,10

11 EX: B+ Tree of order 3. (a) Initial tree 60 20 , 40 80 5,10 20 40,50
Index level 20 , 40 80 5,10 20 40,50 60 80,100 Data level

12 (b) Insert “120” 60 Overflow 20 , 40 80 5,10 20 40,50 60 80,100,120 60 20 , 40 80 , 100 5,10 20 40,50 60 80 100,120

13 (c) Insert “150” 60 Overflow 20 , 40 80 , 100 5,10 20 40,50 60 80 100,120,150 60 , 100 20 , 40 80 120 5,10 20 40,50 60 80 100 120,150

14 (c) Delete “40” 60 , 100 20 , 40 80 120 5,10 20 40,50 60 80 100 120,150 60 , 100 20 , 50 80 120 5,10 20 50 60 80 100 120,150

15 (c) Delete “100” 60 , 100 20 , 40 80 120 5,10 20 40,50 60 80 100 120,150 Under flow rotation 60 , 120 20 , 50 80 150 5,10 20 50 60 80 120 150

16 (c) Delete “150” 60 , 120 20 , 50 80 150 5,10 20 50 60 80 120 150 60 20 , 50 80 , 120 5,10 20 50 60 80 120