際際滷

際際滷Share a Scribd company logo

Struktur data 07 (b tree)

Download as PPT, PDF
Sunarya Marwah
Sunarya Marwah

Dokumen ini membahas tentang B-Tree, yaitu struktur data yang menggabungkan struktur linier dan tree untuk menyimpan data secara efisien. B-Tree memiliki karakteristik seperti node yang dapat berisi lebih dari satu elemen, jumlah elemen dalam node menentukan orde B-Tree, dan proses insert yang dapat menyebabkan pemecahan node jika terjadi overflow.

1 of 11
Downloaded 42 times
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah BAGIAN VIBAGIAN VI
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree B-tree merupakan gabungan antara struktur linier dengan struktur tree, dengan jumlah anak tidak terbatas (walaupun ada batas praktis), sehingga sesuai untuk menampung data (target data / key) yang sangat banyak.
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Karakteristik 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.
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Insert 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
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Insert(20), menyebabkan page overflow, karena page berisi 2d + 1 sehingga page perlu split (memecah diri) menjadi dua bagian, dengan aturan sebagai berukut: a. Satu dengan nilai tengah naik ke parent page, bila parent page tidak ada maka dibuat parent baru. b. Dua elemen yang nilainya lebih kecil dari elemen tengah, masuk ke page kiri. c. Dua elemen yang nilainya lebih besar dari elemen tengah, masuk ke page kanan
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Page Split 12 19 24 25 20 (12 dan 19) < 20 (24 dan 25) > 20 20 naik keatas
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text
Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text

More Related Content

Struktur data 07 (b tree)

  • 1. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah BAGIAN VIBAGIAN VI
  • 2. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree B-tree merupakan gabungan antara struktur linier dengan struktur tree, dengan jumlah anak tidak terbatas (walaupun ada batas praktis), sehingga sesuai untuk menampung data (target data / key) yang sangat banyak.
  • 3. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Karakteristik 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.
  • 4. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Insert 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
  • 5. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Insert(20), menyebabkan page overflow, karena page berisi 2d + 1 sehingga page perlu split (memecah diri) menjadi dua bagian, dengan aturan sebagai berukut: a. Satu dengan nilai tengah naik ke parent page, bila parent page tidak ada maka dibuat parent baru. b. Dua elemen yang nilainya lebih kecil dari elemen tengah, masuk ke page kiri. c. Dua elemen yang nilainya lebih besar dari elemen tengah, masuk ke page kanan
  • 6. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Page Split 12 19 24 25 20 (12 dan 19) < 20 (24 dan 25) > 20 20 naik keatas
  • 7. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text
  • 8. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text
  • 9. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text
  • 10. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text
  • 11. Copyright Sunarya D. MarwahCopyright Sunarya D. Marwah B-TreeB-Tree Text