struktur data 07 (b tree)

Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah

BAGIAN VIBAGIAN VI


B-TreeB-Tree

B-tree merupakan gabungan antara struktur l inier dengan struktur tree, dengan jumlah anak t idak terbatas (walaupun ada batas praktis), sehingga sesuai untuk menampung data (target data / key) yang sangat banyak.


B-TreeB-TreeKarakterist ik B-tree

1. Node atau sering juga disebut Page, dapat berisi lebih dari satu elemen.2. Jumlah elemen didalam page menunjukan orde B-tree, dengan notasi d.3. Jumlah minimum elemen didalam page, kecuali root page adalah d.4. Jumlah maksimum elemen dalam page adalah

2d.5. Jumlah anak: 0 ≤ anak ≤ 2d + 1 6. Seluruh Leaf page berada dalam satu level.


B-TreeB-TreeInsert

Misalkan B-tree dirancang dengan orde d = 2.Urutan data yang masuk: 12 24 25 19 20

Insert(12):

Insert(24):

Insert(25):

Insert(19):

12

12 24

12 24 25

12 19 24 25


B-TreeB-TreeInsert(20), menyebabkan page overflow, karena page

berisi 2d + 1 sehingga page perlu split (memecah dir i) menjadi dua bagian, dengan aturan sebagai berukut:

a. Satu dengan ni lai tengah naik ke parent page, bi la parent page tidak ada maka dibuat parent

baru.

b. Dua elemen yang nilainya lebih kecil dari elemen tengah, masuk ke page kir i.

c. Dua elemen yang nilainya lebih besar dari elemen tengah, masuk ke page kanan


B-TreeB-Tree

Page Split

12 19 24 25

20

(12 dan 19) < 20 (24 dan 25) > 20

20 naik keatas


B-TreeB-Tree

Text

struktur data 07 (b tree)

Documents