B – tree adalah sebuah tree yang dapat menyimpan data secara berurutan dan memungkinkan untuk pencarian, akses sekuensial, penambahan, serta penghapusan dalam waktu yang relatif singkat. B – tree adalah generalisasi dari binary search tree, di mana setiap node dapat memiliki lebih dari 2 chlidren. Tidak seperti self – balancing binary search trees, B – tree lebih dikhususkan untuk sistem yang membutuhkan pembacaan dan penulisan data dalam jumlah yang relatif besar / banyak. B – tree biasadigunakan untuk database dan filesystem.
Dalam B – tree, internal nodes (non - leaf) dapat memiliki variabel jumlah node anak dalam batas yang sudah ditentukan. Ketika sebuah data ditambahkan atau dihapus dari sebuah node, jumlah node anak dari tree tersebut berubah. Dengan tujuan untuk mempertahankan batas yang sudah ditentukan tersebut, internal nodes dapat bergabung atau berpisah. Karena berbagai batas dari node – node anak diijinkan, maka B – tree tidak perlu menyeimbangkan diri sesering mungkin layaknya self – balancing search trees, tetapi hal semacam ini akan membuang – buang tempat yang ada, karena setiap node yang ada tidak terisi semua. Batas bawah dan batas atas pada jumlah node anak biasanya tetap untuk implementasi tertentu. Sebagai contoh, pada 2 – 3 tree, setiap internal node hanya dapat memiliki 2 atau 3 node – node anak.
Setiap node – node internal pada B – tree akan berisi sejumlah kunci. Biasanya, jumlah kunci dipilih secara bervariasi antara d dan 2d. Pada prakteknya, kunci yang ada mengambil sebagian besar space (tempat) dalam setiap node. Faktor ‘2’ akan menjamin setiap node yang ada dapat dipisahkan atau digabungkan. Jika node internal memiliki kunci sebanyak 2d, maka penambahan kunci lain pada node tersebut dapat dilakukan dengan memisahkan node kunci 2d tersebut menjadi 2 node kunci d dan menambahkan kunci tersebut pada node parent – nya. Setiap node yang akan dipisahkan, memiliki jumlah kunci yang minimun. Demikian juga jika sebuah node internal dan ‘tetangga’ nya masing – masing memiliki kunci d, maka sebuah kunci dapat dihapus dari node internal tersebut dengan menggabungkannya dengan ‘tetangga’ node tersebut. Penghapusan kunci tersebut akan mengakibatkan node internal memiliki kunci sebanyak d – 1; penggabungan dengan ‘tetangga’ akan menambahkan sebuah kunci d dan satu kunci lagi yang berasal dari parent ‘tetangga’ nya. Hasilnya adalah seluruh node yang ada penuh dengan kunci 2d.
Jumlah cabang (anak node) dari sebuah node akan satu lebih banyak dari jumlah kunci yang tersimpan dalam node. Dalam sebuah 2-3 B – tree, node internal akan menyimpan baik satu kunci (dengan 2 buah node anak) atau dua kunci (dengan tiga node anak). Sebuah B- tree kadang – kadang digambarkan dengan parameter (d + 1) – (2d + 1) atau yang lebih mudah dengan urutan cabang tertinggi, (2d + 1).
Sebuah B – tree akan tetap seimbang dengan syarat semua node – node daun (node terluar) berada dalam kedalaman yang sama. Kedalaman ini akan bertambah secara perlahan – lahan sebagai satu syarat yang ditambahkan pada sebuah tree, tetapi pertambahan pada keseluruhan kedalaman jarang terjadi, dan sebagai hasilnya pada semua node - node daun menjadi satu node lebih jauh dari root – nya.
B – tree memiliki keuntungan substansial atas implementasi alternatif ketika waktu untuk mengakses sebuah node menjadi jauh melebihi waktu akses antara sesama node. Hal ini biasanya terjadi ketika node – node tersebut berada pada penyimpanan sekunder seperti diks drives. Dengan memaksimalkan jumlah dari anak – anak node dari setiap node – node internal, ketinggian tree tersebut akan berkurang dan jumlah akses node yang mahal (lama) akan berkurang. Selain itu, proses menyeimbangan kembali tree jarang terjadi. Jumlah maksimum dari node – node anak bergantung dari informasi (data) yang harus disimpan dalam setiap node anak dan ukuran blok dari sebuah disk penuh atau ukuran yang analog dalam penyimpanan sekunder. Sementara 2-3 B – tree lebih mudah untuk dijelaskan, secara praktis B – tree yang memakai penyimpanan sekunder menginginkan node anak dalam jumlah besar untuk meningkatkan kinerja tree tersebut.
Searching
Searching dalam B – tree mirip dengan searching dalam binary search tree. Dimulai dari root, tree akan dilaluli secara rekursif dari atas sampai bawah (root sampai node terluar). Dalam setiap level, search memilih sebuah child pointer (subtree) yang memisahkan nilai – nilai pada kedua sisi dari nilai pencarian.
Binary search biasanya (tapi tidak selalu) digunakan dalam setiap node untuk menemukan nilai – nilai pemisahan dan nilai penting dari child tree.
Insertion
Setiap penambahan dimulai dari sebuah node daun (node terluar). Untuk menambahkan sebuah elemen (data) baru.
Pencarian dilakukan pada tree untuk menemukan node terluar di mana elemen baru (data) harus ditambahkan. Tambahkan data baru tersebut ke dalam node dengan langkah – langkah berikut :
1. Jika node berisi lebih sedikit dari jumlah elemen (data) maksimum yang sudah ditentukan, maka terdapat ruangan untuk e
lemen yang baru (data baru). Tambahkan elemen baru tersebut ke dalam node, jaga data – data dalam node tetap teratur.
2. Jika node – node sudah penuh, sehingga terbagi rata menjadi 2 node,
· Sebuah median tunggal dipilih dari antara unsur – unsur daun dan elemen baru.
· Nilai yang kurang dari median diletakkan pada node baru sebelah kiri dan nilai yang lebih dari median diletakkan pada node baru sebelah kanan, dengan median bertindak sebagai nilai pemisah.
· Tambahkan nilai pemisah pada node parent, yang akan menyebabkan node tersebut akan memisah, dan seterusnya. Jika node tidak memiliki parent (yaitu jika node adalah root), buat root baru di atas node tersebut (menambahkan tinggi dari tree tersebut).
Jika pembelahan terjadi terus menerus sampai ke akarnya (root), itu akan menciptakan root baru dengan satu nilai pemisah dan dua anak (node child), itulah sebabnya mengapa batas bawah dari ukuran node internal tidak berlaku untuk root. Jumlah maksimum data setiap node adalah U – 1. Di mana node berpisah, sebuah data bergerak menuju parent, tetapi satu data baru telah ditambahkan. Jadi, harus dimungkinkan untuk membagi jumlah maksimum U – 1 data ke dalam dua node yang sah. Jika jumlah ini adalah ganjil, maka U = 2L dan salah satu dari node ini berisi (U - 2) / 2 = L – 1 data dalam node. Setengah dari jumlah adalah L – 1, yang merupakan jumlah minimum data yang dibolehkan tiap node. (U untuk jumlah maksimum, dan L untuk jumlah minimum).
Algoritma yang sudah dikembangkan mendukung single pass dari root ke node di mana insertion akan menempatkan dirinya, pembelahan node penuh akan ditemui setiap jalan selama insertion. Hal ini untuk mencegah kebutuhan mengingat node parent ke dalam memori, yang akan menghabiskan memori jika node berada pada penyimpanan sekunder. Namun, untuk menggunakan algoritma yang sudah dikembangkan ini, kita harus dapat mengirimkan sebuah elemen (data) kepada parent dan membelah elemen U – 2 sisanya menjadi dua node yang sah, tanpa menambahkan elemen baru. Hal ini membutuhkan U = 2L dibandingkan dengan U = 2L – 1, yang menjelaskan mengapa beberapa buku mengenakan persyaratan ini untuk menjelaskan B – tree.
Deletion
Ada 2 cara mengenai penghapusan dari sebuah B – tree,
· Temukan dan hapus data itu, kemudian atur ulang tree untuk mengembalikan keseimbangannya
atau
· Lakukan single pass pada tree tersebut, tetapi sebelum masuk pada sebuah node, atur ulang tree sehingga setelah data yang akan dihapus ditemukan. Data tersebut dapat dihapus tanpa memicu terjadinya atur ulang kembali.
Ø Penghapusan terjadi pada node terluar (leaf node)
· Cari data yang akan dihapus.
· Jika data tersebut berada pada node terluar (leaf node), data tersebut dapat dengan mudah dihapus dari node.
· Jika underflow terjadi, periksa saudara, baik mengirim kunci maupun menggabungkan kedua saudara tersebut bersama – sama.
· Jika proses penghapusan terjadi dari anak sebelah kanan mengambil nilai maksimum dari anak sebelah kiri, jika tidak ada underflow pada anak sebelah kiri.
· Dalam situasi sebaliknya, ambil elemen terkecil dari sebelah kanan.
Ø Penghapusan pada internal node
Kasus pertama, kedua node anak ke kiri dan kanan dari elemen yang akan dihapus memiliki jumlah elemen yang minimum, uaitu L – 1. Mereka dapat digabungkan menjadi satu node dengan 2L – 2 elemen, jumlah yang tidak melebihi
U – 1 dan adalah node yang sah. Kecuali jika diketahui bahwa B – tree tidak mengandung data yang sama, kita juga harus (secara rekursif) menghapus elemen yang dicari dari node yang baru.
Kasus kedua, satu dari dua node anak berisi lebih dari jumlah minimum elemen. Kemudian pemisah yang baru untuk subtree tersebut harus ditemukan. Perhatikan bahwa elemen terbesar dari subtree kiri masih kurang dari pemisahnya. Demikian juga, elemen terkecil dari subtree kanan masih lebih besar dari pemisahnya. Kedua node tersebut ada di node luar (leaf node), dan dapat berupa pemisah yang baru untuk kedua subtree.
Ø Menyeimbangkan setelah penghapusan
· Jika saudara sebelah kanan memiliki lebih dari jumlah elemen minimum
o Tambahkan pemisah pada akhir node yang tidak sempurna
o Ganti pemisah pada parent dengan elemen pertama dari saudara kanan
o Tambah anak pertama dari saudara kanan sebagai anak terakhir dari node yang tidak sempurna
· Sebaliknya, jika saudara kiri memiliki lebih dari jumlah elemen minimum
o Tambah pemisah pada awal node yang rusak
o Ganti pemisah parent dengan elemen terakhir dari saudara kiri
o Tambahkan anak terakhir dari saudara kiri dengan anak pertama dari node yang rusak
· Jika kedua saudara hanya punya jumlah elemen minimum
o Buat node baru dengan semua data dari node yang rusak, semua data berasal dari salah satu saudara (sibling), dan pemisah parent antara dua node saudara digabungkan.
o Hilangkan pemisah dari parent dan gantikan kedua anak yang dipisahkan dengan node gabungan.
o Jika hal itu membawa jumlah data dalam parent lebih rendah dari batas minimum data, ulang langkah – langkah tersebut dengan node yang rusak, karena root tidak diizinkan untuk rusak.
