Pohon B+: Cari, Sisipkan, dan Hapus Operations

Apa itu Pohon B+?

A B+ Pohon Terutama digunakan untuk mengimplementasikan pengindeksan dinamis pada beberapa level. Dibandingkan dengan B-Tree, B+Tree hanya menyimpan pointer data pada node daun pohon, yang membuat proses pencarian lebih akurat dan cepat.

Aturan untuk Pohon B+

Berikut adalah aturan-aturan penting untuk Pohon Nilai B+.

• Daun digunakan untuk menyimpan catatan data.
• Data disimpan di node internal Pohon.
• Jika nilai kunci target kurang dari node internal, maka penunjuk yang berada tepat di sebelah kirinya akan diikuti.
• Jika nilai kunci target lebih besar dari atau sama dengan node internal, maka penunjuk yang berada tepat di sebelah kanannya akan diikuti.
• Akar mempunyai minimal dua anak.

Mengapa menggunakan Pohon B+

Berikut adalah alasan mengapa menggunakan B+ Tree:

• Kunci terutama digunakan untuk membantu pencarian dengan mengarahkan ke lembar yang tepat.
• Pohon tipe B+ menggunakan "faktor pengisian" untuk mengatur peningkatan dan penurunan pada pohon tersebut.
• 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 lengkap semua elemen hanya membutuhkan satu kali proses linier karena semua node daun dari pohon B+ saling terhubung.

Pohon B+ vs. Pohon B

Berikut perbedaan utama antara Pohon B+ dan Pohon B.

Cari Operaproduksi

Dalam B+ Tree, pencarian adalah salah satu prosedur termudah untuk dijalankan dan memberikan 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.

Cari 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 tersebut terhubung secara akurat dengan nilai kunci minimum dan lokasi baru di dalam 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 daun tersebut.
• Hingga node tingkat atas tidak ditemukan, terus ulangi proses yang dijelaskan pada langkah di atas.

Menyisipkan OperaAlgoritma

1. If 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 di lokasi yang sesuai pada node tersebut.
• Nilai selanjutnya dalam rangkaian data adalah 12, yang perlu dijadikan bagian dari Pohon.
• Untuk mencapai hal ini, bagi simpul tersebut dan tambahkan 6 sebagai elemen penunjuk.
• Sekarang, hierarki kanan dari sebuah pohon dibuat, dan nilai data yang tersisa disesuaikan sesuai dengan itu dengan cara menjaganya.ping dengan memperhatikan aturan yang berlaku mengenai nilai yang sama dengan atau lebih besar dari terhadap node key-value 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 menemukan entri daun di dalam Pohon yang menyimpan kunci dan penunjuk, kemudian menghapus entri daun dari Pohon jika daun tersebut memenuhi kondisi penghapusan catatan yang tepat.
• Jika node daun hanya memenuhi faktor kepuasan yaitu setengah penuh, maka operasi selesai; jika tidak, node daun memiliki entri minimum dan tidak dapat dihapus.
• Node-node terkait lainnya di sebelah kanan dan kiri dapat mengosongkan entri apa pun dan kemudian memindahkannya ke daun. Jika kriteria ini tidak terpenuhi, maka mereka harus menggabungkan node daun dan node terkaitnya dalam hierarki pohon.
• Saat simpul daun bergabung dengan tetangganya di sebelah kanan atau kiri, entri nilai dalam simpul daun atau tetangga yang terhubung yang menunjuk ke simpul tingkat atas akan dihapus.

Contoh di atas mengilustrasikan prosedur untuk menghapus elemen dari B+ Tree 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 tersebut dapat dihapus tanpa memengaruhi aturan penghapusan, yang merupakan nilai dari kunci minimum.

• Dalam contoh di atas, kita harus menghapus 31 dari Pohon.
• Kita perlu menemukan instance angka 31 di Index dan Leaf.
• Kita dapat melihat bahwa angka 31 tersedia baik di tingkat node Indeks maupun node Daun. Oleh karena itu, kita menghapusnya dari kedua instance tersebut.
• Namun kita harus mengisi indeks yang menunjuk ke 42. Sekarang kita akan melihat anak kanan di bawah 25 dan mengambil nilai minimum lalu menempatkannya sebagai indeks. Jadi, karena 42 adalah satu-satunya nilai yang ada, maka itu akan menjadi indeks.

Delete OperaAlgoritma

1) Start at the root and go up to the 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 saudara kandung untuk menyesuaikan nilai di n dan node induknya jika diperlukan.

Pertanyaan Umum Demo Slot