B-Tree

Pada B-Tree dikenal istilah order. Order menentukan jumlah maksimum/minimum anak yang dimiliki oleh setiap node, sehingga order merupakan hal yang cukup penting dalam B-Tree.

Aturan pada B-Tree : m = order
Setiap node (kecuali leaf) memiliki anak paling banyak sejumlah m anak
Setiap node (kecuali root) memiliki anak paling sedikit m/2 anak
Root memiliki anak minimal 2, selama root bukan leaf
Jika node non leaf memiliki k anak, maka jumlah data yang tersimpan dalam node k-1
Data yang tersimpan pada node harus terurut secara inorder
Semua leaf berada pada level yang sama, level terbawah

Insertion

Anggap data yang mau di insert adalah key
Posisikan key pada node yang sesuai, seperti pada BST dan 2-3 Tree, anggap node tersebut A
Jika A adalah node dengan jumlah data kurang dari m-1, maka langsung masukan saja
Jika A adalah node dengan jumlah data m-1, maka masukan nilai tengah kemudian masukan ke parentnya. Kemudian anggaplah parent tersebut A. Kemudian periksa kembali sesuai aturan point ke 3 dan 4.

Deletion

Anggap node yang mau di delete adalah key
Delete dilakukan pada leaf. Meskipun pada saat menghapus node parent, kita tetap menganggapnya menghapus leaf, karena ketika parent dihapus lalu digantikan oleh anak terbesar subtree kiri atau anak terkecil subtree kanan sama saja kita seolah-olah menghapus anak yang menggantikannya. dimana anak tersebut selalu berada pada posisi leaf. Maka leaf tersebut dianggap P.
Jika ukuran P > m/2 maka langsung delete saja data yang ingin dihapus
Jika ukuran P = m/2 maka : perhatikan siblingnya (anggap sibling adalah Q)
Q > m/2, maka rotasi pada P
Q = m/2, satukan P dan Q