B + TREE: Cari, Sisipkan dan Hapus Contoh Operasi

Daftar Isi:

Anonim

Apa itu Pohon B +?

A B + Pohon terutama digunakan untuk menerapkan pengindeksan dinamis pada beberapa tingkat. Dibandingkan dengan Pohon B, Pohon B + menyimpan penunjuk data hanya pada simpul daun Pohon, yang membuat proses pencarian lebih akurat dan lebih cepat.

Dalam tutorial B + Tree ini, Anda akan belajar:

  • Apa itu Pohon B +?
  • Aturan untuk Pohon B +
  • Mengapa menggunakan B + Tree
  • B + Pohon vs. Pohon B.
  • Operasi Pencarian
  • Sisipkan Operasi
  • Hapus Operasi

Aturan untuk Pohon B +

Berikut adalah aturan penting untuk Pohon B +.

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

Mengapa menggunakan B + Tree

Berikut, alasan menggunakan B + Tree:

  • Kunci terutama digunakan untuk membantu pencarian dengan mengarahkan ke Leaf yang tepat.
  • B + Tree menggunakan "faktor pengisian" untuk mengatur kenaikan dan penurunan pohon.
  • Di pohon B +, banyak kunci dapat dengan mudah ditempatkan pada halaman memori karena mereka tidak memiliki data yang terkait dengan node interior. Oleh karena itu, ia akan dengan cepat mengakses data pohon yang ada di simpul daun.
  • Pemindaian lengkap yang komprehensif dari semua elemen adalah pohon yang hanya membutuhkan satu jalur linier karena semua simpul daun dari pohon B + terhubung satu sama lain.

B + Pohon vs. Pohon B.

Di sini, adalah perbedaan utama antara Pohon B + vs. Pohon B.

B + Pohon B Pohon
Tombol pencarian dapat diulang. Kunci pencarian tidak boleh berlebihan.
Data hanya disimpan di node daun. Node daun dan simpul internal dapat menyimpan data
Data yang disimpan di node daun membuat pencarian lebih akurat dan lebih cepat. Pencarian lambat karena data yang disimpan di Leaf dan node internal.
Penghapusan tidak sulit karena 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.

Operasi Pencarian

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

Algoritme pencarian berikut dapat diterapkan:

  • Untuk menemukan record yang diperlukan, Anda perlu menjalankan pencarian biner pada record yang tersedia di Tree.
  • Jika sama persis dengan kunci pencarian, catatan terkait dikembalikan ke pengguna.
  • Jika kunci yang tepat tidak ditemukan oleh 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 lebih akurat.

Algoritma Operasi Pencarian

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

Keluaran :

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

Sisipkan Operasi

Algoritme berikut dapat diterapkan untuk operasi penyisipan:

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

Masukkan Algoritma Operasi

1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. 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 treeb. 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 simpul daun yang diperlukan.

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

  • Pertama, kami 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 ini, bagi node, tambahkan 6 sebagai elemen penunjuk.
  • Sekarang, hierarki kanan pohon dibuat, dan nilai data yang tersisa disesuaikan dengan mengingat aturan yang berlaku sama dengan atau lebih besar dari nilai terhadap node nilai kunci di sebelah kanan.

Hapus Operasi

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

Algoritme berikut dapat diterapkan saat menghapus elemen dari Pohon B +:

  • Pertama, kita perlu mencari entri daun di Tree yang menahan key dan pointer. , hapus entri daun dari Pohon jika Daun memenuhi kondisi persis penghapusan catatan.
  • Jika simpul daun hanya memenuhi faktor yang memuaskan yaitu setengah penuh, maka operasi selesai; jika tidak, node Leaf memiliki entri minimum dan tidak dapat dihapus.
  • Node terkait lainnya di kanan dan kiri dapat mengosongkan entri apa pun lalu memindahkannya ke Daun. Jika kriteria ini tidak terpenuhi, maka mereka harus menggabungkan node daun dan node tertautnya dalam hierarki pohon.
  • Setelah penggabungan node daun dengan tetangganya di kanan atau kiri, entri nilai di node daun atau tetangga tertaut yang menunjuk ke node tingkat atas 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. Karenanya, elemen dapat dihapus tanpa memengaruhi aturan penghapusan, yang merupakan nilai dari kunci minimal-telanjang.

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

Hapus Algoritma Operasi

1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) 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 nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust 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.

Ringkasan:

  • B + Tree adalah struktur data yang menyeimbangkan diri untuk menjalankan prosedur pencarian, penyisipan, dan penghapusan data yang akurat dan lebih cepat
  • Kita dapat dengan mudah mengambil data lengkap atau sebagian karena melalui struktur pohon yang ditautkan membuatnya efisien.
  • Struktur pohon B + tumbuh dan menyusut dengan peningkatan / penurunan jumlah rekaman yang disimpan.
  • Penyimpanan data pada node daun dan percabangan berikutnya dari node internal ternyata memperpendek tinggi pohon, yang mengurangi operasi input dan output disk, yang pada akhirnya menghabiskan lebih sedikit ruang pada perangkat penyimpanan.