B Tree

B-Tree

Pohon sebanyak M-cara yang dibuat oleh Rudolf Bayer dan Ed McCreight yang digunakan secara luas untuk mengakses disk. Sebuah B-Tree dengan orde M, dapat mempuyai key sebanyak M-1, dan pointer sebanyak M ke sub-tree. B-Tree dirancang untuk menyimpan data terurut dan memungkinkan untuk searching, insertion, dan deletion.

Konsep nya mirip sama 2-3 tree beda nya kalo 2-3 tree itu b-tree dengan orde 3, sedangkan b-tree itu ordenya  bebas.

Contoh B-Tree:

*B-tree dengan order 5

Ketentuan B-Tree:

a.       Jika B-Tree order n:

a.       Tiap node maksimal bisa punya n anak.

b.      Tiap node minimal punya n/2 anak.

c.       Root min punya 2 anak.

d.      Semua leaf berada di level yang sama.

e.      Data disusun berdasar sorted order.

f.        Node maks punya n-1 data.

Operasi-operasi pada B-Tree:

a.       Insert:

a.       Jika jmlh data di leaf<order-1, maka masukkin data nya disitu.

b.      Jika sudah full, maka push middle data nya dan split/pisah jadi 2 node yaitu data-data dikiri middle data dan data-data di kanan middle data.

b.      Delete:

a.       Jika jumlah data di node nya>order/2, maka delete saja.

b.      Jika jumlah data di node nya<=order/2:

                                                               i.      Jika jumlah data di node sibling nya>order/2 maka lakukan rotasi.

                                                             ii.      Jika jumlah data di node siblingnya<=order/2 maka lakukan turun dan merge.

                                                            iii.      Lakukan seterusnya.