B-TreesB-Treesm-m-way search treeway search treeAdalah tree yang memiliki batasan s.b.b:Adalah tree yang memiliki batasan s.b.b: Root memiliki maksimum m subtrees dan memiliki struktur Root memiliki maksimum m subtrees dan memiliki struktur

n, A0, (K1,A1), (K2,A2),...,(Kn,An) dimana n, A0, (K1,A1), (K2,A2),...,(Kn,An) dimana Ai, 0 Ai, 0 ≤ i ≤ n < m adalah pointer ke substrees dan ≤ i ≤ n < m adalah pointer ke substrees dan Ki, 1 Ki, 1 ≤ i ≤ n < m merupakan nilai Key.≤ i ≤ n < m merupakan nilai Key.

Ki < Ki+1, 1 Ki < Ki+1, 1 ≤ i < n≤ i < n Seluruh nilai Key pada subtree Ai lebih kecil dari Ki+1 dan lebih besar dari Seluruh nilai Key pada subtree Ai lebih kecil dari Ki+1 dan lebih besar dari

Ki, 0 < i < n. Ki, 0 < i < n. Seluruh nilai Key pada subtree An lebih besar dari Kn dan yang di A0 lebih Seluruh nilai Key pada subtree An lebih besar dari Kn dan yang di A0 lebih

lebih kecil dari K1. lebih kecil dari K1. Seluruh subtree Ai, Seluruh subtree Ai, 0 0 ≤ i ≤ n juga merupakan ≤ i ≤ n juga merupakan m-m-way search treeway search tree

T0026-Data Structure-D1789

20, 40TT a

10, 15 25, 30 45, 50

35

b c d

e

nodenode schematic formatschematic format

a 2,b,(20,c),(40,d)

b 2,0,(10,0),(15,0)

c 2,0,(25,0),(30,e)

d 2,0,(45,0),(50,0)

e 1,0,(35,0)33--way search treeway search tree

Pencarian pada Pencarian pada m-m-way search treeway search tree dimulai dari root (top down) dimulai dari root (top down) Jika target elemen ditemukan, maka poses selesai.Jika target elemen ditemukan, maka poses selesai. Jika target tidak ditemukan maka dilanjutkan ke subtree Ai.Jika target tidak ditemukan maka dilanjutkan ke subtree Ai. Proses pencarian key dalam node bisa menggunakan metode Proses pencarian key dalam node bisa menggunakan metode

sequential search ataupun binary search tergantung pada sequential search ataupun binary search tergantung pada jumlah key yang ada dalam node.jumlah key yang ada dalam node.

Cari 35

ditemukan

SearchingSearching

20, 40

10, 15 25, 30 45, 50

35

B-TreeB-TreeB-Tree dengan order m adalah B-Tree dengan order m adalah m-m-way search tree tree yang memiliki batasan way search tree tree yang memiliki batasan

s.b.b:s.b.b: Root memiliki minimum 2 childrenRoot memiliki minimum 2 children.. Seluruh node kecuali root node dan failure node memiliki minimum [m/2] Seluruh node kecuali root node dan failure node memiliki minimum [m/2]

children. children. Seluruh failure node berada pada level yang sama.Seluruh failure node berada pada level yang sama.

Dengan demikian, 2-3 tree adalah B-tree dengan order 3 sedangkan 2-3-4 tree Dengan demikian, 2-3 tree adalah B-tree dengan order 3 sedangkan 2-3-4 tree adalah B-tree dengan order 4. Disamping itu, B-tree dengan order 2 adalah B-tree dengan order 4. Disamping itu, B-tree dengan order 2 merupakan Full Binary Tree.merupakan Full Binary Tree.

Jumlah Key dalam B-treeJumlah Key dalam B-tree

B-tree dengan order m dan level tertinggi l, memiliki jumlah key B-tree dengan order m dan level tertinggi l, memiliki jumlah key

maksimum sebanyak m - 1.maksimum sebanyak m - 1.ll

• Proses insert pada B-tree merupakan generalisasi proses insert pada Proses insert pada B-tree merupakan generalisasi proses insert pada 2-3 tree.2-3 tree.

• Untuk m>3 menggunakan pendekatan top down sebagaimana insert Untuk m>3 menggunakan pendekatan top down sebagaimana insert pada 2-3-4 tree.pada 2-3-4 tree.

InsertionInsertion

30

Insert (Insert (3030))

3-way ( order 3 )3-way ( order 3 )

InsertionInsertion

10 30

Insert (Insert (1010))

30

Insert (Insert (4040))

4010

30

Insert (Insert (6060))

40 6010

30 50

Insert (Insert (5050))

4010 60

30 50

Insert (Insert (7070))

4010 60 70 30

Insert (Insert (8080))

4010 60 80

70

50

DeletionDeletion• Proses delete pada B-tree juga merupakan generalisasi proses delete Proses delete pada B-tree juga merupakan generalisasi proses delete

pada 2-3 tree.pada 2-3 tree.• Pertama yang dilakukan adalah mencari target key, misal x.Pertama yang dilakukan adalah mencari target key, misal x.• Jika x ditemukan pada nonleaf node, maka dilakukan transformasi key dari Jika x ditemukan pada nonleaf node, maka dilakukan transformasi key dari

leaf node.leaf node.• Terdapat 4 kasus/kondisi jika x ditemukan pada leaf node, misal p:Terdapat 4 kasus/kondisi jika x ditemukan pada leaf node, misal p:

• p merupakan root node, ada kemungkinan B-tree menjadi kosong.p merupakan root node, ada kemungkinan B-tree menjadi kosong.• p paling tidak memilki key sebanyak [m/2] – 1 setelah didelete, proses p paling tidak memilki key sebanyak [m/2] – 1 setelah didelete, proses

delete langsung dilakukan tanpa ada transformasi.delete langsung dilakukan tanpa ada transformasi.• p paling tidak memilki key sebanyak [m/2] – 2 dan sibling terdekat p paling tidak memilki key sebanyak [m/2] – 2 dan sibling terdekat

misal q memiliki key sebanyak [m/2], proses delete akan diikuti oleh misal q memiliki key sebanyak [m/2], proses delete akan diikuti oleh rotasi satu key dari q ke p melalui parent misal r.rotasi satu key dari q ke p melalui parent misal r.

• p paling tidak memilki key sebanyak [m/2] – 2 dan sibling terdekat p paling tidak memilki key sebanyak [m/2] – 2 dan sibling terdekat misal q memiliki key sebanyak [m/2] – 1, proses delete akan diikuti misal q memiliki key sebanyak [m/2] – 1, proses delete akan diikuti oleh penggabungan node pdang q sehingga menghasilkan single oleh penggabungan node pdang q sehingga menghasilkan single node.node.

DeletionDeletion

30 Delete (Delete (3030))

40 6010 20

40

6010 20

Delete (Delete (6060)) 20

4010

Delete (Delete (4040))

10 20 . . .. . . 30 Delete (Delete (4040))

40 6010 20

30

6010 20

LatihanLatihanUntuk B-tree order 3 dilakukan opersai berturut-turut s.b.b. :Untuk B-tree order 3 dilakukan opersai berturut-turut s.b.b. :

+60 +20 +30 +10 +50 +80 +40 +25 -35+60 +20 +30 +10 +50 +80 +40 +25 -35