B + Tree

Cari
Akar B + Tree mewakili keseluruhan rentang nilai di pohon, di mana setiap simpul internal adalah subinterval.Kami mencari nilai kdi B + Tree. Mulai dari akar, kami mencari daun yang mungkin mengandung nilainya k. Pada setiap node, kita mencari tahu pointer mana yang harus kita ikuti. Bilah Tree internal B + paling banyak  ≤  anak-anak, di mana masing-masing mewakili sub-interval yang berbeda. Kami memilih node yang sesuai dengan mencari pada nilai kunci dari node.

Fungsi : pencarian (k)   mengembalikan tree_search (k, root); Fungsi : tree_search (k, node)   jika simpul adalah daun kemudian kembali simpul;  switch k do case k <k_0     return tree_search (k, p_0);  kasus k_i ≤ k <k_ {i + 1}     mengembalikan tree_search (k, p_ {i + 1});  kasus k_d ≤ k     mengembalikan tree_search (k, p_ {d + 1});Pseudocode ini mengasumsikan bahwa tidak ada duplikat yang diperbolehkan.

Kompresi kunci awalan 
• Penting untuk meningkatkan fan-out, karena ini memungkinkan pencarian langsung ke tingkat daun lebih efisien.
• Entri Indeks hanya untuk 'mengarahkan lalu lintas', sehingga kita bisa memampatkannya.

Penyisipan 
Lakukan pencarian untuk menentukan ember mana yang harus dicatat oleh rekaman baru.
• Jika ember tidak penuh (paling banyak   entri setelah penyisipan), tambahkan catatan.
• Jika tidak, pisahkan ember.
• Alokasikan daun baru dan gerakkan setengah dari elemen ember ke ember baru.
• Masukkan kunci terkecil dan alamat baru ke orang tua.
• Jika orang tua sudah kenyang, pisahkan juga.
• Tambahkan kunci tengah ke simpul induk.
• Ulangi sampai orang tua ditemukan yang tidak perlu dipisah.
• Jika akar membelah, buatlah akar baru yang memiliki satu kunci dan dua petunjuk. (Artinya, nilai yang didorong ke akar baru akan dihapus dari simpul aslinya)B-pohon tumbuh di akar dan tidak di daun.

Penghapusan 
• Mulai dari akar, temukan daun L dimana masuk.
• Hapus entri
• Jika L setidaknya setengah penuh, selesai!
• Jika L memiliki lebih sedikit entri daripada seharusnya,
• Jika saudara kandung (simpul yang berdekatan dengan orang tua yang sama dengan L ) lebih dari setengah penuh, distribusikan ulang, meminjam sebuah entri darinya.
• Jika tidak, saudara kandungnya benar-benar setengah penuh, jadi kita bisa menggabungkan L dan saudara kandung.
• Jika penggabungan terjadi, harus menghapus entri (menunjuk ke L atau saudara) dari induk L .
• Gabung bisa merambat ke akar, menurunkan tinggi badan.

Pemuatan massal 
Dengan koleksi data record, kami ingin membuat indeks B + tree pada beberapa field kunci. Salah satu pendekatannya adalah dengan memasukkan setiap record ke dalam sebuah pohon kosong. Namun, ini cukup mahal, karena setiap entri mengharuskan kita untuk memulai dari akar dan turun ke halaman daun yang sesuai. Alternatif yang efisien adalah menggunakan bulk-loading.
• Langkah pertama adalah mengurutkan entri data sesuai dengan tombol pencarian dalam urutan menaik.
• Kami mengalokasikan halaman kosong untuk dijadikan root, dan memasukkan pointer ke halaman pertama entri ke dalamnya.
• Bila akar sudah penuh, kita membagi akarnya, dan membuat halaman root yang baru.
• Terus masukkan entri ke halaman indeks paling kanan tepat di atas permukaan daun, sampai semua entri diindeks.
Catatan :
• Saat halaman indeks paling kanan di atas permukaan daun terisi, terbelah;
• Tindakan ini dapat, pada gilirannya, menyebabkan terbelahnya halaman indeks paling kanan pada langkah mendekati akar;
• Perpecahan hanya terjadi pada jalur yang paling kanan dari akar sampai ke tingkat daun.

sib.stts.edu