B+ TREE : Cari, Sisipkan dan Hapus OperaContoh

Apa itu Pohon B+?

A B+ Pohon terutama digunakan untuk menerapkan pengindeksan dinamis pada berbagai tingkat. Dibandingkan dengan B-Tree, B+ Tree menyimpan penunjuk data hanya pada node daun Pohon, yang menjadikan proses pencarian lebih akurat dan lebih cepat.

Aturan untuk Pohon B+

Berikut adalah aturan penting untuk B+ Tree.

• Daun digunakan untuk menyimpan catatan data.
• Itu disimpan di node internal Pohon.
• Jika nilai kunci target lebih kecil dari simpul internal, maka titik di sisi kirinya akan diikuti.
• Jika nilai kunci target lebih besar atau sama dengan node internal, maka titik di sisi kanannya akan diikuti.
• Akar mempunyai minimal dua anak.

Mengapa menggunakan Pohon B+

Berikut alasan menggunakan B+ Tree:

• Kunci terutama digunakan untuk membantu pencarian dengan mengarahkan ke Daun yang tepat.
• B+ Tree menggunakan “faktor pengisian” untuk mengatur kenaikan dan penurunan pohon.
• Pada pohon B+, banyak kunci dapat dengan mudah ditempatkan pada halaman memori karena kunci tersebut tidak memiliki data yang terkait dengan node interior. Oleh karena itu, ia akan dengan cepat mengakses data pohon yang ada pada node daun.
• Pemindaian penuh yang komprehensif terhadap semua elemen adalah sebuah pohon yang hanya membutuhkan satu lintasan linier karena semua simpul daun dari pohon B+ terhubung satu sama lain.

Pohon B+ vs. Pohon B

Berikut adalah perbedaan utama antara B+ Tree vs. B Tree

B+ Pohon	B Pohon
Kunci pencarian dapat diulang.	Kunci pencarian tidak boleh berlebihan.
Data hanya disimpan di node daun.	Node daun dan node internal dapat menyimpan data
Data yang disimpan pada node daun membuat pencarian lebih akurat dan cepat.	Pencarian lambat karena data disimpan di Leaf dan node internal.
Penghapusannya tidak sulit karena sebuah elemen hanya dihapus dari simpul daun.	Penghapusan elemen adalah proses yang rumit dan memakan waktu.
Node daun yang terhubung membuat pencarian menjadi efisien dan cepat.	Anda tidak dapat menghubungkan node daun.

Pencarian Operaproduksi

Di B+ Tree, pencarian adalah salah satu prosedur termudah untuk dijalankan dan mendapatkan hasil yang cepat dan akurat.

Algoritma pencarian berikut ini berlaku:

• Untuk menemukan catatan yang diperlukan, Anda perlu menjalankan pencarian biner pada catatan yang tersedia di Pohon.
• Jika sama persis dengan kunci pencarian, catatan terkait dikembalikan ke pengguna.
• Jika kunci yang tepat tidak ditemukan melalui pencarian di node induk, saat ini, atau daun, maka “pesan tidak ditemukan” ditampilkan kepada pengguna.
• Proses pencarian dapat dijalankan kembali untuk hasil yang lebih baik dan akurat.

Pencarian OperaAlgoritma

 1. Call the binary search method on the records in the B+ Tree.
 2. If the search parameters match the exact key
            The accurate result is returned and displayed to the user
          Else, if the node being searched is the current and the exact key is not found by the algorithm
            Display the statement "Recordset cannot be found."

Keluaran:

Kumpulan rekaman yang cocok dengan kunci yang tepat ditampilkan kepada pengguna; jika tidak, upaya yang gagal akan ditampilkan kepada pengguna.

Menyisipkan Operaproduksi

Algoritma berikut ini berlaku untuk operasi penyisipan:

• 50 persen elemen dalam node dipindahkan ke daun baru untuk disimpan.
• Induk dari Daun baru ditautkan secara akurat dengan nilai kunci minimum dan lokasi baru di Pohon.
• Pisahkan node induk menjadi lebih banyak lokasi jika node tersebut dimanfaatkan sepenuhnya.
• Sekarang, untuk hasil yang lebih baik, kunci tengah dikaitkan dengan node tingkat atas dari Leaf tersebut.
• Hingga node tingkat atas tidak ditemukan, terus ulangi proses yang dijelaskan pada langkah di atas.

Menyisipkan OperaAlgoritma

1.	Even inserting at-least 1 entry into the leaf container does not make it full then add the record  
     2. Else, divide the node into more locations to fit more records.
      a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the tree
      b. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.
      c. Divide the top-level node if it gets full of keys and addresses.
          i. Similarly,  insert a key in the center of the top-level node in the hierarchy of the Tree.
     d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore. 

3) Build a new top-level root node of 1 Key and 2 indicators.  

Keluaran:

Algoritme akan menentukan elemen dan berhasil memasukkannya ke dalam node daun yang diperlukan.

Contoh contoh Pohon B+ di atas dijelaskan pada langkah-langkah di bawah ini:

• Pertama, kita memiliki 3 node, dan 3 elemen pertama, yaitu 1, 4, dan 6, ditambahkan pada lokasi yang sesuai di node.
• Nilai berikutnya dalam rangkaian data adalah 12 yang perlu dijadikan bagian dari Pohon.
• Untuk mencapai hal ini, bagilah node, tambahkan 6 sebagai elemen penunjuk.
• Sekarang, hierarki kanan pohon dibuat, dan nilai data yang tersisa disesuaikan dengan mengingat aturan yang berlaku yaitu nilai yang sama atau lebih besar dari nilai terhadap node nilai kunci di sebelah kanan.

Delete Operaproduksi

Kompleksitas prosedur penghapusan di Pohon B+ melampaui kompleksitas fungsi penyisipan dan pencarian.

Algoritma berikut ini berlaku saat menghapus elemen dari Pohon B+:

• Pertama, kita perlu mencari entri daun di Pohon yang memegang kunci dan penunjuk. , hapus entri daun dari Pohon jika Daun memenuhi kondisi penghapusan rekaman yang tepat.
• Bila simpul daun hanya memenuhi faktor kepuasan setengah penuh, maka operasi selesai; jika tidak, simpul daun memiliki entri minimum dan tidak dapat dihapus.
• Node tertaut lainnya di kanan dan kiri dapat mengosongkan entri apa pun lalu memindahkannya ke Leaf. Jika kriteria ini tidak terpenuhi, maka node daun dan node tertautnya harus digabungkan dalam hierarki pohon.
• Setelah penggabungan simpul daun dengan tetangganya di kanan atau kiri, entri nilai dalam simpul daun atau tetangga tertaut yang menunjuk ke simpul tingkat atas akan dihapus.

Contoh di atas mengilustrasikan prosedur untuk menghapus elemen dari Pohon B+ dengan urutan tertentu.

• Pertama, lokasi pasti dari elemen yang akan dihapus diidentifikasi di Pohon.
• Di sini elemen yang akan dihapus hanya dapat diidentifikasi secara akurat pada tingkat daun dan bukan pada penempatan indeks. Oleh karena itu, elemen dapat dihapus tanpa mempengaruhi aturan penghapusan, yaitu nilai kunci minimum.

• Dalam contoh di atas, kita harus menghapus 31 dari Pohon.
• Kita perlu menemukan contoh 31 di Index dan Leaf.
• Kita dapat melihat bahwa 31 tersedia di level node Indeks dan Daun. Oleh karena itu, kami menghapusnya dari kedua contoh.
• Tapi, kita harus mengisi indeks yang menunjuk ke 42. Sekarang kita akan melihat anak yang tepat di bawah 25 tahun dan mengambil nilai minimum dan menempatkannya sebagai indeks. Jadi, 42 menjadi satu-satunya nilai yang ada, itu akan menjadi indeks.

Delete OperaAlgoritma

1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
    A. If n is root, remove K
         a. if root has more than one key, done
         b. if root has only K
            i) if any of its child nodes can lend a node
               Borrow key from the child and adjust child links
            ii) Otherwise merge the children nodes. It will be a new root
         c. If n is an internal node, remove K
            i) If n has at least ceil(m/2) keys, done!
            ii) If n has less than ceil(m/2) keys,
                If a sibling can lend a key,
                Borrow key from the sibling and adjust keys in n and the parent node
                    Adjust child links
                Else
                    Merge n with its sibling
                    Adjust child links
         d. If n is a leaf node, remove K
            i) If n has at least ceil(M/2) elements, done!
                In case the smallest key is deleted, push up the next key
            ii) If n has less than ceil(m/2) elements
            If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
            Else
                Merge n and its sibling
                Adjust keys in the parent node

Keluaran:

Kunci “K” dihapus, dan kunci dipinjam dari saudaranya untuk menyesuaikan nilai dalam n dan node induknya jika diperlukan.

Kesimpulan

• B+ Tree adalah penyeimbang diri struktur data untuk melaksanakan prosedur pencarian, penyisipan dan penghapusan data yang akurat dan lebih cepat
• Kita dapat dengan mudah mengambil data lengkap atau sebagian data karena melalui struktur pohon tertaut membuatnya efisien.
• Struktur pohon B+ tumbuh dan menyusut seiring bertambahnya/menurunnya jumlah catatan yang disimpan.
• Penyimpanan data pada node daun dan percabangan selanjutnya dari node internal jelas memperpendek tinggi pohon, sehingga mengurangi operasi input dan output disk, yang pada akhirnya menghabiskan lebih sedikit ruang pada perangkat penyimpanan.