Pohon B+
Pohon B+ atau B+Tree merupakan salah satu varian dari B-Tree. B-tree aksesnya akan lebih cepat dibandingkan dengan AVL tree jika ketinggiannya dijaga seminimal mungkin. Operasi dasar B-Tree 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 external node. Index node merupakan sebutan dari internal node B+tree. Perbedaan antara B-tree dan B+ tree adalah jika B-tree key dan record dapat disimpan sebagai internal maupun leaf node, sedangkan untuk B+ tree pada record disimpan sebagai leaf node dan key hanya dapat disimpan sebagai internal node.[1]
Keuntungan dari B+ tree antara lain untuk mengambil record dibutuhkan jumlah access disk yang sama ; Dalam B+ tree data dapat diakses secara berurutan dan langsung; B+tree memiliki level yang lebih rendah dan sangat cepat sekaligus efisien dalam mengakses record dari disk. [2]
Searching
Langkah-langkah mencari record dengan search-key : k
1. Mulai dari root node . Bandingkan k dengan key pada root node [ k1, k2, k3,….. k m-1]
2. Jika k < k 1, pergi ke anak kiri dari root 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 leaf node tercapai.
6. Jika k ada di leaf node, kembalikan true jika tidak kembalikan false. [3]
Insertion
Hal-hal yang perlu diperhatikan dalam sebelum insertion:
1. Root setidaknya memiliki 2 anak
2. Setiap node kecuali root dapat memiliki maksimal m anak dan setidaknya m/2 anak
3. Setiap node dapat berisi maksimal m - 1 key dan minimal ⌈m/2⌉ - 1 key.
Untuk memasukkan elemen maka dapat diikuti langkah yang pertama yakni setiap elemen dimasukkan ke dalam leaf node dan buka leaf node yang sesuai, kemudian masukkan key pada leaf node. Jika key tidak full maka msukkan key ke dalam leaf node dengan urutan meningkat, namun jika leaf sudah penuh, masukkan key ke leaf node dengan urutan meningkat dan seimbangkan tree dengan menghancurkan node pada posisi m/2 dan tambhakan juga key m/2 ke node induk. [4]
Deleting
Menghapus pada B+ tree memiliki 3 hal utama antara lain mencari node dimana ada key yang akan dihapus, menghapus key dan menyeimbangkan tree jika diperlukan, dan underflow yakni ketika jumlah key dalam sebuah node lebih sedikit dari jumlah minimum key yang harus dipegang. Untuk menghapus key, key pada node internal (indeks) harus dijaga karena nilainya berlebihan di B+tree.[5]
Referensi
- ^ "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.
- ^ "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.