B POHON dalam Struktur Data: Cari, Sisipkan, Hapus OperaContoh tion

Aturan untuk B-Tree

Berikut adalah aturan penting untuk membuat B_Tree

• Semua daun akan dibuat pada level yang sama.
• B-Tree ditentukan oleh sejumlah derajat, yang juga disebut “urutan” (ditentukan oleh aktor eksternal, seperti programmer), disebut sebagai

  m

  dan seterusnya. Nilai dari

  m

  tergantung pada ukuran blok pada disk tempat data utama berada.

• Subpohon kiri dari node akan memiliki nilai yang lebih kecil dibandingkan sisi kanan subpohon. Artinya node juga diurutkan dalam urutan menaik dari kiri ke kanan.
• Jumlah maksimum simpul anak, simpul akar, serta simpul turunannya dihitung dengan rumus ini:

  m – 1

  Sebagai contoh:

  m = 4
  max keys: 4 – 1 = 3
  

• Setiap node, kecuali root, harus berisi kunci minimum

  [m/2]-1

  Sebagai contoh:

  m = 4
  min keys: 4/2-1 = 1
  

• Jumlah maksimum node anak yang dapat dimiliki sebuah node sama dengan derajatnya, yaitu

  m

• Anak minimum yang dapat dimiliki sebuah node adalah setengah dari order, yaitu m/2 (nilai plafon diambil).
• Semua kunci dalam sebuah node diurutkan dalam urutan yang meningkat.

Mengapa menggunakan B-Tree

Inilah alasan menggunakan B-Tree

• Mengurangi jumlah pembacaan yang dilakukan pada disk
• B Trees dapat dengan mudah dioptimalkan untuk menyesuaikan ukurannya (yaitu jumlah node anak) sesuai dengan ukuran disk
• Ini adalah teknik yang dirancang khusus untuk menangani data dalam jumlah besar.
• Ini adalah algoritma yang berguna untuk database dan sistem file.
• Pilihan yang baik untuk dipilih saat membaca dan menulis blok data yang besar

Sejarah Pohon B

• Data disimpan di disk dalam bentuk blok, data ini, ketika dibawa ke memori utama (atau RAM) disebut struktur data.
• Jika datanya sangat besar, pencarian satu rekaman dalam disk memerlukan pembacaan keseluruhan disk; ini meningkatkan waktu dan konsumsi memori utama karena frekuensi akses disk dan ukuran data yang tinggi.
• Untuk mengatasi hal ini, tabel indeks dibuat yang menyimpan referensi catatan dari catatan berdasarkan blok tempat mereka berada. Hal ini secara drastis mengurangi konsumsi waktu dan memori.
• Karena kami memiliki data yang sangat besar, kami dapat membuat tabel indeks bertingkat.
• Indeks multi-level dapat dirancang dengan menggunakan B Tree untuk menjaga agar data diurutkan secara mandiri.

Pencarian Operaproduksi

Operasi pencarian adalah operasi paling sederhana di B Tree.

Algoritma berikut diterapkan:

• Biarkan kunci (nilai) dicari dengan “k”.
• Mulailah mencari dari akar dan telusuri ke bawah secara rekursif.
• Jika k lebih kecil dari nilai akar maka carilah subpohon sebelah kiri, jika k lebih besar dari nilai akar maka carilah subpohon sebelah kanan.
• Jika node telah menemukan k, cukup kembalikan node tersebut.
• Jika k tidak ditemukan di node, turunkan ke anak dengan kunci yang lebih besar.
• Jika k tidak ditemukan di pohon, kami mengembalikan NULL.

Menyisipkan Operaproduksi

Karena B Tree adalah pohon yang menyeimbangkan diri, Anda tidak dapat memaksa memasukkan kunci ke sembarang node.

Algoritma berikut berlaku:

• Jalankan operasi pencarian dan temukan tempat penyisipan yang sesuai.
• Masukkan kunci baru di lokasi yang tepat, tetapi jika node sudah memiliki jumlah kunci maksimum:
• Node, bersama dengan kunci yang baru dimasukkan, akan dipisahkan dari elemen tengah.
• Elemen tengah akan menjadi induk bagi dua node anak lainnya.
• Node harus mengatur ulang kunci dalam urutan menaik.

TIP	Berikut ini tidak benar tentang algoritma penyisipan: Karena node sudah penuh, maka node akan terpecah, dan kemudian nilai baru akan dimasukkan

Dalam contoh di atas:

• Cari posisi yang sesuai di node untuk kuncinya
• Masukkan kunci di node target, dan periksa aturannya
• Setelah penyisipan, apakah node memiliki lebih dari sama dengan jumlah kunci minimum, yaitu 1? Dalam hal ini, ya, benar. Periksa aturan selanjutnya.
• Setelah penyisipan, apakah node memiliki lebih dari jumlah kunci maksimum, yaitu 3? Dalam hal ini, tidak, tidak. Artinya Pohon B tidak melanggar aturan apa pun, dan penyisipan selesai.

Dalam contoh di atas:

• Node telah mencapai jumlah kunci maksimal
• Node tersebut akan terpecah, dan kunci tengahnya akan menjadi simpul akar dari dua simpul lainnya.
• Jika jumlah kunci genap, simpul tengah akan dipilih berdasarkan bias kiri atau bias kanan.

Dalam contoh di atas:

• Node memiliki kunci kurang dari maksimal
• 1 disisipkan di sebelah 3, tetapi aturan urutan menaik dilanggar
• Untuk memperbaikinya, kunci diurutkan

Demikian pula, 13 dan 2 dapat dimasukkan dengan mudah ke dalam node karena memenuhi aturan kunci kurang dari maksimal untuk node.

Dalam contoh di atas:

• Node memiliki kunci yang sama dengan kunci maks.
• Kuncinya dimasukkan ke node target, tetapi melanggar aturan kunci maks.
• Node target dipecah, dan kunci tengah dengan bias kiri sekarang menjadi induk dari node anak baru.
• Node baru disusun dalam urutan menaik.

Demikian pula, berdasarkan aturan dan kasus di atas, nilai lainnya dapat disisipkan dengan mudah di Pohon B.

Delete Operaproduksi

Operasi penghapusan memiliki lebih banyak aturan daripada operasi penyisipan dan pencarian.

Algoritma berikut berlaku:

• Jalankan operasi pencarian dan temukan kunci target di node
• Tiga kondisi diterapkan berdasarkan lokasi kunci target, seperti yang dijelaskan di bagian berikut

Jika kunci target ada di simpul daun

• Target ada di simpul daun, lebih dari kunci min.
• Menghapus ini tidak akan melanggar properti B Tree
• Target ada di simpul daun, ia memiliki simpul kunci minimum
• Menghapus ini akan melanggar properti B Tree
• Target simpul dapat meminjam kunci dari simpul sebelah kiri, atau simpul sebelah kanan (saudara)
• Adiknya akan berkata iya nih jika memiliki lebih dari jumlah kunci minimum
• Kunci akan dipinjam dari node induk, nilai maksimal akan ditransfer ke node induk, nilai maksimal dari node induk akan ditransfer ke node target, dan menghapus nilai target
• Target ada di simpul daun, tetapi tidak ada saudara kandung yang memiliki jumlah kunci lebih dari minimal
• Cari kunci
• Gabungkan dengan saudara kandung dan minimum node induk
• Total kunci sekarang akan lebih dari min
• Kunci target akan diganti dengan minimum node induk

Jika kunci target ada di node internal

• Entah memilih, dalam urutan pendahulunya atau dalam urutan penerusnya
• Jika pendahulunya diurutkan, kunci maksimum dari subpohon kirinya akan dipilih
• Jika penerusnya berurutan, kunci minimum dari subpohon kanannya akan dipilih
• Jika in-order pendahulu kunci target memiliki lebih dari kunci min, barulah kunci target dapat diganti dengan max dari in-order pendahulunya.
• Jika kunci target dalam urutan pendahulunya tidak memiliki lebih dari kunci min, carilah kunci minimum penerus dalam urutan.
• Jika pendahulu dan penerus kunci target memiliki kunci kurang dari min, maka gabungkan pendahulu dan penerusnya.

Jika kunci target ada di simpul akar

• Ganti dengan elemen maksimum dari subpohon pendahulunya secara berurutan
• Jika, setelah penghapusan, target memiliki kunci kurang dari min, maka node target akan meminjam nilai maksimal dari saudaranya melalui induk saudaranya.
• Nilai maksimal dari induk akan diambil oleh target, tetapi dengan node dari nilai maksimal saudaranya.

Sekarang, mari kita pahami operasi penghapusan dengan sebuah contoh.

Diagram di atas menampilkan berbagai kasus operasi penghapusan di B-Tree. B-Tree ini berorde 5, artinya jumlah minimum node anak yang dapat dimiliki setiap node adalah 3, dan jumlah maksimum node anak yang dapat dimiliki oleh setiap node adalah 5. Sedangkan jumlah kunci minimum dan maksimum setiap node dapat memiliki masing-masing 2 dan 4.

Dalam contoh di atas:

• Node target memiliki kunci target untuk dihapus
• Node target memiliki lebih banyak kunci daripada kunci minimum
• Hapus saja kuncinya

Dalam contoh di atas:

• Node target mempunyai kunci yang sama dengan kunci minimum, sehingga tidak dapat menghapusnya secara langsung karena akan melanggar ketentuan

Sekarang, diagram berikut menjelaskan cara menghapus kunci ini:

• Node target akan meminjam kunci dari saudara terdekat, dalam hal ini, pendahulunya (saudara kiri) karena tidak memiliki penerus dalam urutan (saudara kanan)
• Nilai maksimum dari inorder pendahulunya akan ditransfer ke induk, dan induk akan mentransfer nilai maksimum ke node target (lihat diagram di bawah)

Contoh berikut mengilustrasikan cara menghapus kunci yang memerlukan nilai dari penerusnya yang berurutan.

• Node target akan meminjam kunci dari saudara terdekatnya, dalam hal ini penerus dalam urutan (saudara kanan) karena pendahulunya dalam urutan (saudara kiri) memiliki kunci yang sama dengan kunci minimum.
• Nilai minimum penerus pesanan akan ditransfer ke induk, dan induk akan mentransfer nilai maksimum ke node target.

Pada contoh di bawah, node target tidak memiliki saudara yang dapat memberikan kuncinya ke node target. Oleh karena itu, diperlukan penggabungan.

Lihat prosedur menghapus kunci tersebut:

• Gabungkan node target dengan saudara terdekatnya beserta kunci induknya
• Kunci dari node induk dipilih yang merupakan saudara kandung di antara dua node yang bergabung
• Hapus kunci target dari node yang digabungkan

Delete OperaKode Pseudo

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Keluaran:

Elemen terbesar dihapus dari B-Tree.

Kesimpulan

• B Tree adalah struktur data yang menyeimbangkan diri untuk pencarian, penyisipan, dan penghapusan data dari disk yang lebih baik.
• B Pohon diatur oleh derajat yang ditentukan
• B Kunci dan simpul pohon disusun dalam urutan menaik.
• Operasi pencarian B Tree adalah yang paling sederhana, yang selalu dimulai dari root dan mulai memeriksa apakah kunci target lebih besar atau lebih kecil dari nilai node.
• Operasi penyisipan B Tree agak mendetail, yang pertama-tama menemukan posisi penyisipan yang sesuai untuk kunci target, menyisipkannya, mengevaluasi validitas B Tree terhadap kasus yang berbeda, dan kemudian merestrukturisasi node B Tree sesuai dengan itu.
• Operasi penghapusan B Tree terlebih dahulu mencari kunci target yang akan dihapus, menghapusnya, mengevaluasi validitas berdasarkan beberapa kasus seperti kunci minimum dan maksimum dari node target, saudara kandung, dan induk.