B + TREE: Contoh Cari, Masukkan dan Padam Operasi

Isi kandungan:

Anonim

Apa itu Pokok B +?

A B + Tree terutamanya digunakan untuk melaksanakan pengindeksan dinamik pada pelbagai peringkat. Berbanding dengan B- Tree, B + Tree menyimpan penunjuk data hanya di simpul daun Pohon, yang menjadikan proses pencarian lebih tepat dan cepat.

Dalam tutorial B + Tree ini, anda akan belajar:

  • Apa itu Pokok B +?
  • Peraturan untuk B + Tree
  • Mengapa menggunakan B + Tree
  • Pokok B + Pokok B
  • Operasi Carian
  • Masukkan Operasi
  • Padam Operasi

Peraturan untuk B + Tree

Berikut adalah peraturan penting untuk B + Tree.

  • Daun digunakan untuk menyimpan rekod data.
  • Ia disimpan di nod dalaman Pokok.
  • Sekiranya nilai kunci sasaran kurang dari simpul dalaman, maka titik di sebelah kirinya diikuti.
  • Sekiranya nilai kunci sasaran lebih besar daripada atau sama dengan nod dalaman, maka titik di sebelah kanannya diikuti.
  • Akarnya mempunyai sekurang-kurangnya dua anak.

Mengapa menggunakan B + Tree

Berikut adalah sebab penggunaan B + Tree:

  • Kunci digunakan terutamanya untuk membantu pencarian dengan mengarahkan ke Daun yang betul.
  • Pokok B + menggunakan "faktor pengisian" untuk menguruskan kenaikan dan penurunan pokok.
  • Di pokok B +, banyak kunci boleh diletakkan dengan mudah di halaman memori kerana tidak mempunyai data yang berkaitan dengan nod dalaman. Oleh itu, ia akan cepat mengakses data pokok yang terdapat di simpul daun.
  • Imbasan penuh yang komprehensif untuk semua elemen adalah pokok yang hanya memerlukan satu lorong linier kerana semua simpul daun pokok B + saling berkaitan antara satu sama lain.

Pokok B + Pokok B

Berikut adalah perbezaan utama antara B + Tree vs B Tree

Pokok B + B Pokok
Kekunci carian boleh diulang. Kekunci carian tidak boleh berlebihan.
Data hanya disimpan di simpul daun. Kedua-dua simpul daun dan nod dalaman dapat menyimpan data
Data yang disimpan di simpul daun menjadikan carian lebih tepat dan cepat. Pencarian lambat kerana data yang tersimpan di Leaf dan nod dalaman.
Penghapusan tidak sukar kerana elemen hanya dikeluarkan dari simpul daun. Penghapusan unsur adalah proses yang rumit dan memakan masa.
Node daun yang dipaut menjadikan carian cekap dan pantas. Anda tidak dapat menghubungkan simpul daun.

Operasi Carian

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

Algoritma carian berikut boleh digunakan:

  • Untuk mencari rekod yang diperlukan, anda perlu menjalankan carian binari pada rekod yang ada di Pohon.
  • Sekiranya terdapat padanan tepat dengan kunci carian, rekod yang sesuai dikembalikan kepada pengguna.
  • Sekiranya kunci yang tepat tidak dijumpai oleh carian di simpul induk, semasa, atau daun, maka "mesej tidak dijumpai" akan ditampilkan kepada pengguna.
  • Proses pencarian dapat dijalankan semula untuk hasil yang lebih baik dan tepat.

Algoritma Operasi Carian

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 :

Rekod yang dipadankan dengan kunci tepat ditunjukkan kepada pengguna; jika tidak, percubaan yang gagal ditunjukkan kepada pengguna.

Masukkan Operasi

Algoritma berikut berlaku untuk operasi sisipan:

  • 50 peratus elemen dalam nod dipindahkan ke daun baru untuk penyimpanan.
  • Ibu bapa Daun baru dihubungkan dengan tepat dengan nilai kunci minimum dan lokasi baru di Pohon.
  • Pisahkan nod induk ke lebih banyak lokasi sekiranya dapat digunakan sepenuhnya.
  • Sekarang, untuk hasil yang lebih baik, kunci tengah dikaitkan dengan simpul tingkat atas Daun itu.
  • Sehingga simpul tingkat atas tidak dijumpai, 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 :

Algoritma akan menentukan elemen dan berjaya memasukkannya ke dalam simpul daun yang diperlukan.

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

  • Pertama, kita mempunyai 3 nod, dan 3 elemen pertama, iaitu 1, 4, dan 6, ditambahkan pada lokasi yang sesuai di nod.
  • Nilai seterusnya dalam rangkaian data adalah 12 yang perlu dijadikan sebahagian daripada Pohon.
  • Untuk mencapai ini, bahagikan nod, tambahkan 6 sebagai elemen penunjuk.
  • Sekarang, hierarki kanan pohon dibuat, dan nilai data yang tersisa disesuaikan dengan memperhatikan peraturan yang berlaku sama dengan atau lebih besar daripada nilai terhadap simpul nilai-kunci di sebelah kanan.

Padam Operasi

Kerumitan prosedur penghapusan di B + Tree melebihi fungsi sisipan dan carian.

Algoritma berikut boleh digunakan semasa menghapus elemen dari B + Tree:

  • Pertama, kita perlu mencari entri daun di Pohon yang memegang kunci dan penunjuk. , hapus entri daun dari Pokok jika Daun memenuhi syarat-syarat yang tepat dari penghapusan rekod.
  • Sekiranya simpul daun hanya memenuhi faktor memuaskan separuh penuh, maka operasi selesai; jika tidak, simpul Daun mempunyai entri minimum dan tidak dapat dihapuskan.
  • Node lain yang dihubungkan di kanan dan kiri dapat mengosongkan sebarang entri kemudian memindahkannya ke Daun. Sekiranya kriteria ini tidak dipenuhi, maka mereka harus menggabungkan simpul daun dan simpulnya yang berkaitan dalam hierarki pohon.
  • Setelah penggabungan simpul daun dengan jirannya di sebelah kanan atau kiri, entri nilai di simpul daun atau jiran yang dihubungkan yang menunjuk ke simpul tingkat atas akan dihapuskan.

Contoh di atas menggambarkan prosedur untuk membuang unsur dari Pokok B + dari urutan tertentu.

  • Pertama, lokasi tepat elemen yang akan dihapuskan dikenal pasti di Pokok.
  • Di sini elemen yang akan dihapus hanya dapat dikenal pasti dengan tepat pada peringkat daun dan bukan pada penempatan indeks. Oleh itu, elemen tersebut dapat dihapuskan tanpa mempengaruhi peraturan penghapusan, yang merupakan nilai kunci minimum.

  • Dalam contoh di atas, kita mesti memadam 31 dari Pokok.
  • Kita perlu mencari contoh 31 di Index dan Leaf.
  • Kita dapat melihat bahawa 31 boleh didapati di peringkat simpul Indeks dan Leaf. Oleh itu, kami memadamkannya dari kedua-dua keadaan.
  • Tetapi, kita harus mengisi indeks menunjuk ke 42. Sekarang kita akan melihat anak yang tepat di bawah 25 tahun dan mengambil nilai minimum dan meletakkannya sebagai indeks. Jadi, 42 menjadi satu-satunya nilai yang ada, ia akan menjadi indeks.

Padamkan 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" dihapuskan, dan kunci dipinjam dari adik-beradik untuk menyesuaikan nilai dalam n dan nod induknya jika diperlukan.

Ringkasan:

  • B + Tree adalah struktur data yang mengimbangkan diri untuk melaksanakan prosedur mencari, memasukkan dan menghapus data yang tepat dan pantas
  • Kita boleh mendapatkan data lengkap atau sebahagian data dengan mudah kerana melalui struktur pokok yang dipautkan menjadikannya cekap.
  • Struktur pokok B + tumbuh dan menyusut dengan peningkatan / penurunan bilangan rekod yang disimpan.
  • Penyimpanan data pada simpul daun dan percabangan simpul dalaman seterusnya dengan jelas memendekkan ketinggian pohon, yang mengurangkan operasi input dan output cakera, akhirnya memakan ruang yang lebih sedikit pada peranti penyimpanan.