Struktur Data B Tree: Pencarian, Penyisipan, Penghapusan

⚡ Ringkasan Cerdas

B-Tree dalam Struktur Data adalah pohon yang menyeimbangkan diri sendiri yang menjaga data tetap terurut untuk operasi pencarian, penyisipan, dan penghapusan yang cepat pada disk. Buku ini menjelaskan aturan B-Tree, sejarahnya, dan algoritma pencarian, penyisipan, dan penghapusan dengan contoh.

🌲 Penyeimbangan Diri: Sebuah B-Tree menjaga semua daun pada level yang sama dan tetap seimbang selama setiap operasi.
🔢 Urutan (m): Derajat m menentukan jumlah maksimum anak (m) dan kunci (m − 1) per node.
🔍 Pencarian: Pencarian dimulai dari akar dan bergerak ke kiri atau ke kanan dengan membandingkan kuncinya.
➕ Memasukkan: Operasi insertion menemukan titik yang tepat dan memisahkan node penuh dari kunci tengahnya.
➖ Menghapus: Penghapusan menangani kasus daun, internal, dan akar menggunakan peminjaman dan penggabungan.

Baca Selengkapnya

Apa itu Pohon B?

B Pohon B Tree adalah struktur data yang menyeimbangkan diri sendiri berdasarkan serangkaian aturan khusus untuk mencari, memasukkan, dan menghapus data dengan cara yang lebih cepat dan efisien dalam penggunaan memori. Untuk mencapai hal ini, aturan-aturan berikut diikuti untuk membuat B Tree.

B-Tree adalah jenis pohon khusus dalam struktur data. Pada tahun 1972, metode ini pertama kali diperkenalkan oleh McCreight dan Bayer, yang menamakannya Height Balanced m-way Search Tree. B-Tree membantu menjaga data tetap terurut dan memungkinkan berbagai operasi seperti penyisipan, pencarian, dan penghapusan dalam waktu yang lebih singkat.

Aturan untuk B-Tree

Berikut adalah aturan penting untuk membuat B-Tree:

Semua daun akan dibuat pada level yang sama.
Sebuah B-Tree ditentukan oleh sejumlah derajat, yang juga disebut "urutan" (ditentukan oleh aktor eksternal, seperti seorang programmer), yang 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 kunci yang dapat dimiliki oleh sebuah node akar, serta node anaknya, dihitung dengan rumus ini: m − 1. Sebagai contoh:
```
m = 4
max keys: 4 − 1 = 3
```

Setiap node, kecuali node akar, harus berisi jumlah 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

Berikut adalah alasan mengapa menggunakan B-Tree:

Mengurangi jumlah pembacaan yang dilakukan pada disk.
B-Tree 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 tepat untuk membaca dan menulis blok data dalam jumlah besar.

Sejarah Pohon B

Data disimpan di disk dalam bentuk blok. Data ini, ketika dimasukkan ke memori utama (atau RAM), disebut struktur data.
Dalam kasus data yang sangat besar, pencarian satu record pada disk memerlukan pembacaan seluruh disk; hal ini meningkatkan waktu dan konsumsi memori utama karena frekuensi akses disk yang tinggi dan ukuran data yang besar.
Untuk mengatasi hal ini, dibuatlah tabel indeks yang menyimpan referensi catatan berdasarkan blok tempat catatan tersebut berada. Hal ini secara drastis mengurangi waktu dan konsumsi memori.
Karena kami memiliki data yang sangat besar, kami dapat membuat tabel indeks bertingkat.
Indeks bertingkat dapat dirancang dengan menggunakan B Tree untuk menjagaping Data diurutkan secara seimbang.

Cari Operaproduksi

Operasi pencarian adalah operasi paling sederhana pada B Tree. Algoritma berikut diterapkan:

Misalkan kunci (nilai) yang akan dicari adalah “k”.
Mulailah mencari dari akar dan telusuri ke bawah secara rekursif.
Jika k lebih kecil dari nilai akar, cari di subpohon kiri; jika k lebih besar dari nilai akar, cari di subpohon 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 memaksakan penyisipan 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.

💡 TIPS: Berikut ini tidak Yang benar tentang algoritma penyisipan: “Karena node sudah penuh, maka node akan dipisah, dan kemudian nilai baru akan disisipkan.” Kunci disisipkan terlebih dahulu, dan baru kemudian node dipisah jika jumlah kuncinya melebihi jumlah maksimum.

Dalam contoh di atas:

Cari kunci pada posisi yang sesuai di dalam node.
Masukkan kunci ke dalam node target, dan periksa aturannya.
Setelah penyisipan, apakah node tersebut memiliki jumlah kunci lebih dari atau sama dengan jumlah minimum, yaitu 1? Dalam hal ini, ya, node tersebut memiliki jumlah kunci lebih dari atau sama dengan jumlah minimum. Periksa aturan selanjutnya.
Setelah penyisipan, apakah node tersebut memiliki lebih dari jumlah kunci maksimum, yaitu 3? Dalam hal ini, tidak. Ini berarti bahwa B Tree tidak melanggar aturan apa pun, dan penyisipan telah selesai.

Dalam contoh di atas:

Node tersebut telah mencapai jumlah kunci maksimum.
Node tersebut akan terpecah, dan kunci di tengah akan menjadi node akar dari dua node yang tersisa.
Jika jumlah kunci genap, node tengah akan dipilih dengan bias kiri atau bias kanan.

Dalam contoh di atas:

Node tersebut memiliki jumlah kunci kurang dari jumlah maksimum.
Angka 1 disisipkan di sebelah angka 3, tetapi aturan urutan menaik dilanggar.
Untuk mengatasi hal ini, kunci-kunci tersebut diurutkan.

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

Dalam contoh di atas:

Node memiliki kunci yang sama dengan kunci maks.
Kunci dimasukkan ke dalam node target, tetapi melanggar aturan jumlah kunci maksimum.
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 dalam node.
Tiga kondisi diterapkan berdasarkan lokasi kunci target, seperti yang dijelaskan pada bagian-bagian berikut.

Jika kunci target ada di simpul daun

Target berada di node daun, lebih dari jumlah kunci minimum. Menghapus ini tidak akan melanggar properti dari B Tree.
Target berada di simpul daun, dan memiliki simpul kunci minimum. Menghapus ini akan melanggar properti Pohon B.
Node target dapat meminjam kunci dari node yang berada tepat di sebelah kiri atau node yang berada tepat di sebelah kanan (saudara kandung).
Adiknya akan berkata iya nih jika jumlah kuncinya melebihi jumlah minimum.
Kunci akan dipinjam dari node induk, nilai maksimum akan ditransfer ke induk, nilai maksimum dari node induk akan ditransfer ke node target, dan nilai target akan dihapus.
Target berada di node daun, tetapi tidak ada saudara kandung yang memiliki lebih dari jumlah kunci minimum: cari kunci tersebut, gabungkan dengan saudara kandung dan minimum dari node induk, total kunci sekarang akan lebih dari minimum, dan kunci target akan diganti dengan minimum dari node induk.

Jika kunci target ada di node internal

Pilih salah satu, yaitu pendahulu yang berurutan atau penerus yang berurutan.
Dalam kasus pendahulu yang berurutan, kunci maksimum dari subpohon sebelah kirinya akan dipilih.
Dalam kasus penerus berurutan (in-order successor), kunci minimum dari subpohon kanannya akan dipilih.
Jika pendahulu kunci target memiliki lebih dari jumlah kunci minimum, barulah kunci target dapat digantikan dengan kunci maksimum dari pendahulunya.
Jika pendahulu in-order dari kunci target tidak memiliki lebih dari min kunci, carilah kunci minimum dari penerus in-order.
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 pendahulu yang berurutan.
Jika, setelah penghapusan, target memiliki kurang dari jumlah kunci minimum, maka node target akan meminjam nilai maksimum dari saudara kandungnya melalui induk saudara kandung tersebut.
Nilai maksimum dari induk akan diambil oleh target, tetapi dengan node yang memiliki nilai maksimum dari saudara kandung.

Sekarang, mari kita pahami operasi penghapusan dengan sebuah contoh.

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

Dalam contoh di atas:

Node target memiliki kunci target yang akan dihapus.
Node target memiliki kunci lebih banyak daripada jumlah kunci minimum.
Cukup hapus kuncinya.

Dalam contoh di atas:

Node target memiliki jumlah kunci yang sama dengan jumlah minimum kunci, jadi kita tidak dapat menghapusnya secara langsung karena akan melanggar ketentuan.

Sekarang, diagram berikut menjelaskan cara menghapus kunci ini:

Node target akan meminjam kunci dari saudara kandung terdekatnya, dalam hal ini, pendahulu berurutan (saudara kandung kiri), karena ia tidak memiliki penerus berurutan (saudara kandung kanan).
Nilai maksimum dari pendahulu yang berurutan 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 kandung terdekatnya, dalam hal ini, penerus berurutan (saudara kandung kanan), karena pendahulu berurutannya (saudara kandung 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 ini, node target tidak memiliki saudara kandung yang dapat memberikan kuncinya ke node target. Oleh karena itu, penggabungan diperlukan. Lihat prosedur penghapusan kunci tersebut:

Gabungkan node target dengan salah satu saudara kandungnya yang terdekat beserta kunci induknya.
Kunci dari node induk dipilih yang terletak di antara dua node yang bergabung.
Hapus kunci target dari node yang digabungkan.

Delete Operation Pseudo Code

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.

Pertanyaan Umum Demo Slot

Ya. Alat AI dapat menghasilkan diagram atau animasi langkah demi langkah tentang penyisipan, pemisahan, dan penghapusan untuk urutan tertentu. Ini membantu para pembelajar melihat bagaimana pohon menyeimbangkan kembali dirinya, meskipun Anda harus memverifikasi setiap langkah terhadap aturan B-Tree.

B-Tree dan variannya mengindeks kumpulan data besar dan penyimpanan vektor yang diandalkan oleh sistem AI, sehingga pencarian data pelatihan atau embedding tetap cepat. Basis data, bukan modelnya, menggunakan B-Tree untuk mengurangi pembacaan disk.

Sebuah node Binary Search Tree (B-Tree) memiliki paling banyak dua anak dan satu kunci. Sebuah node B-Tree dapat menyimpan banyak kunci dan banyak anak.ping Struktur pohon yang pendek dan mengurangi pembacaan disk, sehingga ideal untuk basis data dan sistem file.

Pencarian, penyisipan, dan penghapusan masing-masing berjalan dalam waktu O(log n), di mana n adalah jumlah kunci. Karena setiap node menyimpan banyak kunci, pohon tetap dangkal, sehingga jumlah akses disk sangat kecil.

Struktur Data B Tree: Pencarian, Penyisipan, Penghapusan