Pohon B+
Pohon B+ merupakan salah satu varian dari Pohon B-. Pohon B- aksesnya akan lebih cepat dibandingkan dengan pohon AVL jika ketinggiannya dijaga seminimal mungkin. Operasi dasar pohon B- antara lain Searching , Insection, dan Deletion. Pencarian data dalam database yang besar membutuhkan banyak waktu, namun hal ini dapat di tingkatkan dengan menggunakan Pohon B+ dalam mengindeks data. Pohon B+ terdiri dari internal node dan leaf atau eksternal node. Indeks node merupakan sebutan dari internal node pohon B+. Perbedaan antara pohon B- dan pohon B+ adalah jika pohon B- kunci dan rekord dapat disimpan sebagai internal maupun daun node, sedangkan untuk pohon B+ pada rekord disimpan sebagai daun node dan kunci hanya dapat disimpan sebagai internal node.[1]
Keuntungan dari pohon B+ antara lain untuk mengambil rekord dibutuhkan jumlah akses disk yang sama ; Dalam pohon B+ data dapat diakses secara berurutan dan langsung; pohon B+ memiliki level yang lebih rendah dan sangat cepat sekaligus efisien dalam mengakses rekord dari disk. [2]
Algoritma Pohon B+
[sunting | sunting sumber]Searching
[sunting | sunting sumber]Langkah-langkah mencari rekord dengan kunci pencarian:k[3]
1. Mulai dari akar node . Bandingkan k dengan kunci pada akar node [ k1, k2, k3,….. k m-1]
2. Jika k < k 1, pergi ke anak kiri dari akar node
3. Beda jika k = k1, bandingkan k2. Jika k < k2, k terletak antara k1 dan k2. Jadi, cari di anak kiri k2.
4. Jika k > k2, pilih k3, k4,...km-1 seperti pada langkah 2 dan 3.
5. Ulangi langkah di atas sampai daun node tercapai.
6. Jika k ada di daun node, kembalikan true jika tidak kembalikan false.
Insertion
[sunting | sunting sumber]Hal-hal yang perlu diperhatikan dalam sebelum insertion:[4]
1. Akar setidaknya memiliki 2 anak
2. Setiap node kecuali akar dapat memiliki maksimal m anak dan setidaknya m/2 anak
3. Setiap node dapat berisi maksimal m - 1 kunci dan minimal ⌈m/2⌉ - 1 kunci.
Untuk memasukkan elemen maka dapat diikuti langkah yang pertama yakni setiap elemen dimasukkan ke dalam daun node dan buka daun node yang sesuai, kemudian masukkan kunci pada daun node. Jika kunci tidak full maka msukkan kunci ke dalam daun node dengan urutan meningkat, namun jika daun sudah penuh, masukkan kunci ke daun node dengan urutan meningkat dan seimbangkan pohon dengan menghancurkan node pada posisi m/2 dan tambhakan juga kunci m/2 ke node induk. [4]
Deleting
[sunting | sunting sumber]Menghapus pada pohon B+ memiliki 3 hal utama antara lain mencari node di mana ada kunci yang akan dihapus, menghapus kunci dan menyeimbangkan pohon jika diperlukan, dan underflow yakni ketika jumlah kunci dalam sebuah node lebih sedikit dari jumlah minimum kunci yang harus dipegang. Untuk menghapus kunci, kunci pada node internal (indeks) harus dijaga karena nilainya berlebihan di pohon B+.[5]
Referensi
[sunting | sunting sumber]- ^ "B Tree And B+ Tree Data Structure In C++". Software Testing Help (dalam bahasa Inggris). Diakses tanggal 2022-12-03.
- ^ "Introduction of B+ Tree". GeeksforGeeks (dalam bahasa Inggris). 2018-04-04. Diakses tanggal 2022-12-03.
- ^ "B+ Tree". www.programiz.com. Diakses tanggal 2022-12-03.
- ^ a b "Insertion on a B+ Tree". www.programiz.com. Diakses tanggal 2022-12-03.
- ^ "Deletion from a B+ Tree". www.programiz.com. Diakses tanggal 2022-12-03.