PENGKAJIAN STRUKTUR DATA B-TREE DAN CONTOH PENERAPANNYA

PENGKAJIAN STRUKTUR DATA B-TREE DAN CONTOH PENERAPANNYA Sindy Gita Ratri – NIM : 13505071 Program Studi Teknik Informatika Sekolah Teknik Elektro dan Informatika Institut Teknologi Bandung Jl. Ganesha 10, Bandung E-mail : [email protected]

Abstrak Makalah ini membahas tentang pengkajian stuktur data B-tree dan beberapa contoh penerapannya. Dalam ilmu komputer, B-tree adalah struktur data pohon yang paling umum digunakan dalam basis data dan file system. B-tree menjaga data tetap terurut dan seimbang. Ide di balik B-tree ini yaitu simpul internal dapat memiliki sejumlah simpul anak dalam cakupan (range) yang telah terdefinisi. Ketika data disisipkan atau dipidah dari struktur data, sejumlah simpul anak dapat bertukar sepanjang simpul. Untuk tetap mempertahankan cakupan yang telah didefinisikan, simpul internal digabungkan atau dipisahkan. Karena adanya cakupan (range) pada simpul anak, maka B-tree tidak perlu diseimbangkan secara berkala seperti struktur data pohon seimbang yang lain, misalnya self-balancing binary search trees. Akan tetapi, B-tree dapat menghabiskan tempat karena simpul tidak selalu penuh. Batas atas dan batas bawah jumlah simpul anak biasanya tetap untuk implementasi tertentu. Sebagai contoh, dalam 2-3 B-tree (disebut juga 2-3 tree), setiap simpul internal hanya dapat memiliki 2 atau 3 simpul anak. Sebuah B-tree dijaga keseimbangannya dengan membuat semua simpul daun berada pada ketinggian yang sama. Ketinggian ini akan meningkat perlahan saat elemen-elemen ditambahkan pada pohon, tetapi peningkatan ketinggian secara keseluruhan jarang terjadi. Hal disebabkan karena sebuah B-tree didesain dapat memiliki cabang dalam jumlah besar dan mengandung sejumlah kunci pada tiap simpulnya sehingga ketinggian pohon relatif kecil. Hal ini berarti hanya sedikit simpul yang harus dibaca dari disk untuk mengambil data.Tujuannya yaitu untuk mendapatkan akses pada data yang cepat. B-Tree memiliki kelebihan dibanding implementasi alternatif yang lain karena waktu akses dalam simpulnya jauh di atas waktu akses antarsimpul. Hal ini biasanya muncul ketika kebanyakan simpul berada di penyimpanan sekunder seperti hard drives. Dengan memaksimalkan jumlah simpul anak pada setiap simpul internal, ketinggian pohon berkurang, penyeimbangan muncul tidak terlalu sering, dan efisiensi meningkat. Biasanya nilai ini diset agar setiap simpul mengisi sebuah blok penuh atau pada ukuran yang analog di tempat penyimpanan sekunder. Kata Kunci : struktur pohon, B-tree, 2-3 tree, simpul, balanced search tree, self-balancing binary search trees

1

1 Pendahuluan Struktur pohon menunjang berbagai operasi dinamik dasar termasuk search, predecessor, successor, minimum, maximum, insert, dan delete dalam proporsional waktu terhadap ketinggian pohon. Idealnya, sebuah pohon seimbang dan ketinggiannya adalah log n di mana n adalah jumlah simpul pohon. Untuk memastikan ketinggian pohon sekecil mungkin dan menghasilkan waktu yang terbaik, maka struktur pohon seimbang seperti B-tree sebaiknya digunakan.

1.1 Sejarah B-Tree B-tree memiliki sejarah yang pendek tetapi penting. Pada akhir tahun 1960-an perusahaan komputer dan grup peneliti independen bersaing mengembangkan tujuan umum file systems dan disebut dengan “metode akses” untuk mesinmesin mereka. Di Sperry Univac Corporation (bekerja sama dengan Universitas Case Western Reserve), H. Chiat, M. Schwartz, dan yang lainnya mengembangkan dan mengimplementasi sebuah sistem yang menghasilkan operasi insert dan find dalam tata cara yang menyerupai metode B-tree yang akan dijelaskan nanti. Secara terpisah, B. Cole, S. Radcliffe, M. Kaufman, dan yang lainnya mengembangkan sistem yang mirip di Control Data Corporation (bekerja sama dengan Unversitas Stanford). Kemudian pada tahun 1972, R.Bayer dan E. McCreight di Boeing Scientific Research Labs mengajukan sebuah mekanisme indeks eksternal dengan waktu proses yang relatif rendah untuk kebanyakan operasi-operasi yang telah disebutkan sebelumnya. Mereka menamakan metode tersebut dengan Btree. Para pencipta B-Tree, Rudolf Bayer dan Ed McCreight, tidak menjelaskan arti dari huruf B pada B-Tree tersebut. Yang paling diyakini adalah B merupakan singkatan dari balanced yang artinya seimbang, karena semua simpul daun pada pohon

berada pada tingkat (level) yang sama. B juga dapat berarti Bayer, nama penciptanya, atau Boeing karena mereka bekerja di Boeing Scientific Research Labs pada waktu itu.

1.2 Definisi B-Tree B-Tree adalah sebuah m-ary balanced search tree khusus yang digunakan dalam basis data karena strukturnya memungkinkan data yang disimpan untuk disisipi, dihapus, dan diambil dengan jaminan proses dengan waktu terburuk, di mana setiap simpulnya terdiri dari (m/2) sampai m buah simpul anak, di mana m > 1 merupakan bilangan bulat. m adalah orde. Akar pohon B-tree paling sedikit memiliki 2 simpul anak. Ini adalah struktur yang baik jika pohon digunakan pada memori yang lambat, karena ketinggian dan jumlah akses dapat diperkecil dengan mengambil bilangan m yang besar. Balanced tree atau pohon seimbang adalah pohon dimana tidak ada simpul daun yang lebih panjang terhadap daun yang lain. Search tree adalah pohon dimana setiap subpohon dari sebuah simpul mempunyai kunci lebih kecil dari subpohon kanan simpul tersebut. Kunci dalam sebuah simpul secara konsep berada di antara subpohon-subpohon dan lebih besar dari kunci di subpohon kiri simpul dan lebih kecil dari kunci di subpohon kanan simpul. Sebuah B-Tree didesain untuk digunakan pada disk. Disk hanya dapat membaca dan menulis blok data ukuran tetap (berukuran besar) sekaligus. Sebuah B-tree menyimpan banyak kunci di setap simpulnya sehingga (1) sebuah disk dapat mengakses banyak kunci, dan (2) faktor cabang pohon sangat tinggi (dalam prakteknya lebih besar dari 1000) sehingga pohon dengan ketinggian kecil dapat menyimpan kunci dalam jumlah yang sangat besar, yang dapat diakses hanya dengan beberapa operasi.

2

2 Struktur dari B-Tree 2.1 Struktur Simpul B-Tree Tidak seperti pohon biner, setiap simpul pada B-tree dapat memiliki sejumlah variabel kunci dan anak. Setiap elemen simpul internal adalah nilai-nilai yang berbeda yang membagi subpohonnya. Kunci disimpan dalam urutan membesar. Setiap kunci memiliki anak yang berhubungan dengan kunci tersebut, yaitu akar dari subpohon yang mengandung semua simpul dengan kunci-kunci lebih kecil atau sama dengan kunci simpul akar tetapi lebih besar dari kunci sebelumnya. Sebuah simpul juga mempunyai anak tambahan paling kanan yaitu akar dari subpohon yang mengandung semua kunci lebih besar dari semua kunci pada simpul. Sebagai contoh, jika sebuah simpul internal memiliki tiga simpul anak (atau subpohon) maka simpul tersebut pasti meiliki dua nilai berbeda atau elemen a1 dan a 2 . Semua nilai di paling kiri subpohon lebih kecil dari a1, semua nilai di subpohon tengah akan berada di antara a 1 dan a 2 , dan semua nilai di paling kanan subpohon akan lebih besar dari a2 . Sebuah B-tree memiliki jumlah minimum anak yang mungkin untuk setiap simpul disebut sebagai minimization factor atau faktor minimalisasi. Jika t adalah faktor minimalisasi, setiap simpul harus memiliki paling sedikit t-1 kunci. Dalam keadaan tertentu, simpul akar diperbolehkan melanggar ketentuan tersebut dengan memiliki lebih kecil dari t-1 kunci. Setiap simpul dapat memiliki paling banyak 2t-1 kunci atau setara dengan 2t anak. Simpul internal di B-tree – simpulsimpul yang bukan merupakan simpul daun – biasanya digambarkan sebagai susunan elemen dan pointer anak yang teratur. Setiap simpul internal terdiri dari maksimum U anak dan – selain akar – minimum L anak. Untuk semua simpul internal selain akar, jumlah elemennya lebih kecil satu dari jumlah pointer anak, jumlah elemennya antara L-1 dan U-1. Nilai U harus 2L ataupun 2L-1, jadi setiap simpul internal harus paling sedikit setengah penuh. Hubungan antara U dan L ini mengakibatka bahwa dua

simpul setengah penuh dapat digabung menjadi simpul yang legal, dan satu simpul penuh dapat dipisah menjadi dua simpul yang legal (jika ada ruangan untuk menggeser satu elemen ke simpul orang tuanya). Hal ini memungkinkan untuk menghapus dan memasukkan nilai baru ke dalam B-tree dan mengatur pohon sesuai dengan ketentuannya. Simpul daun memiliki larangan yang sama pada jumlah elemen, tetapi tidak memiliki simpul anak dan tidak ada pointer anak. Simpul daun masih memiliki batas atas pada jumlah anak, tetapi tidak memiliki batas bawah. Sebagai contoh, ketika ada lebih sedikit dari L-1 elemen pada keseluruhan pohon. akar akan menjadi satu-satunya simpul pada pohon, dan akar tidak memiliki anak sama sekali. Beberapa pohon seimbang menyimpan nilai hanya pada simpul daun, jadi memiliki simpul-simpul yang berbeda pada simpul daun dan simpul internal. Btree tetap menjaga nilai-nilai di setiap simpul pada pohon, dan dapat menggunakan struktur yang sama pada setiap simpul. Bagaimanapun, sejak simpul daun tidak memiliki anak, struktur khusus untuk simpul daun pada B-tree akan meningkatakan performa.

2.2 Ketinggian pada B-Tree Untuk n lebih besar atau sama dengan satu, ketinggian dari n-kunci B-tree ,dengan tinggi h dan derajat minimum t lebih besar atau sama dengan 2,

Bukti :

3

Jadi :

Lalu kedua sisi di-logaritma. Tinggi dari kasus terburuk adalah O(log n). Karena percabangan dari B-tree bisa lebih besar dibandingkan struktur pohon seimbang yang lain, basis dari logaritma cenderung lebih besar. Sehingga jumlah simpul yang dikunjungi selama pencarian cenderung lebih kecil dari yang dibutuhkan oleh struktur pohon yang lain. Walaupun hal ini tidak mempengaruhi tinggi asimtotik kasus terburuk, B-tree cenderung memiliki tinggi yang lebih kecil dari pohon lain yang memiliki tinggi asimtotik yang sama.

tidak dapat disimpan pada tempat penyimpanan primer dan akses pada tempat penyimpanan sekunder membutuhkan banyak waktu. Waktu pencarian kasus terburuk pada derajat n-kunci B-tree adalah O(log(n)). Sebuah simpul pada pohon B-tree memiliki t-1 <= K <= 2t-1 kunci yang terurut. Kasus terburuk : - K = t-1 untuk semua simpul - X tidak ada pada pohon Diberikan sebuah simpul W dala pohon T. Berapa lama waktu yang dibutuhkan untuk mencari subpohon dari W yang mengandung X ? Dengan mengguanakan binary search dibutuhkan

=

2.3 Waktu Proses pada B-Tree Sebuah B-tree dengan ketinggian n+1 dapat menghabiskan U waktu sebanyak jumlah nilai pada B-tree dengan ketinggian n, tetapi waktu yang dibutuhkan untuk melakukan operasi search, insert, dan delete bertambah sesuai ketinggian pohon. Dibandingkan dengan pohon seimbang lain, pertambahan pada B-tree leih lambat dibandingakan jumlah elemen. Karena setiap simpul cenderung memiliki faktor percabangan yang besar (jumlah anak yang besar), maka perlu untuk menelusuri beberapa simpul sebelum menempatkan kunci yang diinginkan. Jika akses ke setiap simpul memerlukan disk access, maka sebuah B-tree akan meminimumkan jumlah akses disk yang dibutuhkan. Faktor minimalisasi biasanya dipilih agar ukuran total setiap simpul berkorespondensi pada sebuah ukuran blok yang banyak pada sebuah alat penyimpanan. Pilihan ini memudahkan dan mengoptimumkan akses disk. Oleh karena itu, sebuah B-tree adalah struktur data yang ideal untuk situasi di mana data

=

Karena adalah

tinggi

pohon

kasus

terburuk

maka total waktu yang diperlukan adalah

2.4 Contoh Struktur B-tree Beberapa contoh struktur B-tree sabagai berikut.

4

Gambar 1 Struktur B-Tree Orde 5 Contoh di atas adalah contoh B-Tree dengan orde 5. Maksudnya adalah (selain dari simpul akar) semua simpul internal memiliki paling sedikit 5/2= 2.5 = 3

(pembulatan) anak dan paling sedikit 2 kunci. Tentu saja maksimum jumlah anak yang bisa dimiliki sebuah simpul adalah 5 dan maksimum jumlah kuncinya 4.

Gambar 2 B-Tree Orde 4

Contoh di atas adalah B-tree dengan orde 4. Simpul paling sedikit memiliki 2 kunci dan 2 pointer anak, maksimum memiliki 4 anak 3 kunci.

Contoh lain dari gambar struktur B-tree sebagai berikut.

Gambar 3 Contoh B-Tree Terurut dan Seimbang

5

3 Algoritma B-Tree Algoritma untuk operasi search, create, dan insert ditunjukkan di bawah. Perlu diperhatikan bahwa algoritma-algoritma ini hanya sekali pass. Dengan kata lain, algoritma tersebut tidak menelusuri pohon kembali. Karena B-tree berusaha melakukan akses disk seminimum mungkin dan simpul-simpul biasanya disimpan pada disk, pass sekali ini akan mengurangi jumlah kunjungan pada simpul dan jumlah akses disk. Dua kali pass yang lebih sederhana pada pohon untuk mempesbaiki pelanggaran mungkin terjadi. Karena semua simpul diasumsikan disimpan pada tempat penyimpanan sekunder (disk) daripada tempat peyimpanan primer (memori), semua referensi pada simpul yang diberikan sebelumnya dengan melakukan operasi read dilambangkan dengan Disk-Read. Sama halnya, apabila sebuah simpul dimodifikasi dan tidak lagi diperlukan, simpul harus eitulis pada tempat penyimpanan sekunder dengan operasi write dilambangkan dengan Disk-Write. Algoritma-algoritma di bawah diasumsikan bahwa semua simpul yag memiliki parameter telah memiliki operasi Disk-Read yang sesuai. Simpul baru dibuat dan di-assign dengan fungsi Allocate-Node. Implementasi secara detail dari Disk-Read, Disk-Write, dan AllocateNode tergantung pada sistem operasi (operating system).

3.1 Search Operasi search pada B-tree mirip dengan search pada binary tree. Dimulai dari akar, pohon ditelusuri dari atas sampai ke bawah, memilih pointer anak yang nilainya berada pada sisi nilai yang dicari. Binary search umum digunakan (tidak selalu) di antara simpul untuk menemukan nilai yang berbeda dan anak pohon yang

dicari. Akan tetapi, daripada memilih di antara anak kiri dan anak kanan pada Btree, sebuah search pada B-tree harus membuat pilihan sebanyak n cara. Anak yang sesuai dipilih dengan melakukan pencarian linier pada nilai-nilai dalam simpul. Setelah menemukan nilai lebih besar atau sama dengan nilai yang diinginkan, pencarian pointer anak di sebelah kiri segera dilakukan. Jika semua nilai yang dicari lebih kecil dari nilai yang diinginkan, pencarian dilakukan pada pointer anak paling kanan. Tetntu saja pencarian dapat terhenti apabila simpul yang diinginkan telah ditemukan. Karena waktu yang dibutuhkan untuk melakukan search tergantung pada tinggi pohon, maka proses search pada B-Tree adalah O(log n). Berikut ini adalah pseudocodes proses search pada B-tree. B-Tree-Search (x,k) i <- 1 while (i<=n[x] and k>keyi[x]) do i <- i + 1 if (i<=n[x] and k=keyi[x]) then return (x, i) if (leaf[x]) then return NIL else Disk-Read(ci[x]) return B-Tree-Search(ci[x], k) Contoh search pada B-tree Sebagai contoh, di bawah adalah B-tree dengan orde 2 (simpul paling sedikit memiliki 2 kunci dan 3 pointer anak). Simpul dibatasi dengan kurung siku. Kunci adalah nama kota dan terurut pada setiap simpul. Pada sisi lain dari setiap kunci adalah pointer anak yang menghubungkan kunci pada simpul berikutnya.

6

Mulai dari sini | v [ Chicago | +-----------+ | v [ Aptos | Boston ] | | | v v v

| Hoboken ] | | | +-------------+ | | v v [ Denver | Detroit ] [ San-Jose | Seattle ] | | | | | | v v v v v v X

Untuk menemukan kunci “Dallas”, kita mulai pencarian dari akar simpul paling atas. “Dallas” tidak berada simpul , tetapi terurut di antara “Chicago” dan “Hoboken” jadi kita menelusuri pointer anak yang di tengah. Sekali lagi “Dallas: tidak ada dalm simpul tetapi terurut sebelum “Denver”, jadi kita menelusuri pointer anak yang pertama menuju ke simpul berikutnya yang ditandai dengan “X”. Pada akhirnya kita akan menemukan kunci yang dicari ataupun menemukan simpul daun pada tingkat bawah dari Btree tanpa pointer anak menuju simpul bawah lain dan tanpa kunci yang kita inginkan, menandakan bahwa kunci yang dicari tidak ada dalam B-tree. Di bawah adalah contoh lain dari B-tree orde 1 (simpul memiliki paling sedikit 1 kunci dan 2 pointer anak). Pencarian kunci “Chicago” dimulai dari “Marin”, mengikuti pointer pertama menuju “Aptos” (“Chicago” terurut sebelum “Marin”), kemudian menelusuri pointer simpul kedua menuju level berikutnya (“Chicago” terurut setelah “Aptos”) yang ditandai dengan “X”. | v [ Marin ] | | +--+ +---+ | | v v [ Aptos ] [ Seattle ] | | | | v v v v X

3.2 Insertion Untuk melakukan insertion pada sebuah B-tree, simpul yang tepat untuk kunci harus dicari menggunakan algoritma yang

sama seperti search pada B-tree. Berikutnya, kunci disisipkan pada simpul. Semua proses insertion terjadi pada simpul daun. • Dengan melakukan pencarian pada pohon, temukan simpul daun di mana elemen baru seharusnya berada. Jika simpul daun mengandung lebih sedikit dari nilai maksimum jumlah elemen legal, maka ada tempat kosong. Sisipkan elemen baru pada simpul, tetap jaga keterurutan elemen simpul. • Selainnya apabila simpul penuh, simpul daun harus dipisah menjadi dua simpul. Karena pemisahan simpul menghasilkan pemindahan sebuah kunci ke simpul orang tuanya, simpul tersebut tidak boleh penuh atau operasi pemisahan dilakukan kembali. Proses ini dapat berulang sepanjangperjalanan menuju akar dan memungkinkan pemisahan simpul akar. Hal ini memerlukan dua kali pass. Pass pertama mencari simpul di mana kunci harus diletakkan, yang kedua melakukan pemisahan yang diperlukan pada simpul-simpul sebelumnya. Pemisahan simpul akar ditangani sebagai kasus khusus karena simpul baru harus dibuat untuk menampung kunci tengah dari simpul lama. Pemisahan dilakukan sebagai berikut : median dipilih di antara elemen daun dan elemen baru. Nilai yang lebih kecil dari median diletakkan di simpul kiri yang baru dan nilai yang lebih besar dari median diletakkan di simpul kanan yang baru, dengan median sebagai nilai pemisah. Nilai pemisah tersebut ditambahkan pada simpul orang tuanya, yang dapat mnyebabkan adanya pemisahan lagi, dst. Maksimum jmlah elemen setiap simpul adalah U-1. Ketika sebuah simpul dipisah, satu elemen

7

pindah ke simpul orangtuanya, tetapi elemen lain ditambahkan. Jadi mungkin untuk membagi jmlah maksimum U-1 elemen menjadi dua simpul legal. Jika jumlahnya ganjil maka U = 2L dan setiap simpul baru mengandung (U-2)/2 = L-1 elemen dan kemudian menjadi simpul legal. Jika jumlahnya genap maka U = 2L1, sehingga ada 2L-2 elemen pada simpul. Setengah dari jumlah tersebut adalah L-1, merupakan jumlah elemen minimum pada setiap simpul. Karena setiap akses pada simpul berhubungan dengan akses disk, diusahakan menghindari pass kedua dengan memastikan bahwa simpul orang tuanya tidak pernah penuh. Untuk memenuhi hal tersebut, algoritma yang telah dijelaskan memisahkan setiap simpul penuh yang ditemukan ketika menelusuri pohon. Walaupan hal ini mengakibatkan operasi pemisahan yang teidak diperlukan, hal ini menjamin setiap simpul orang tua tidak pernah perlu dipisahkan dan menghapus kebutuhan pass kedua pada pohon. Proses pemisahan berjalan dalam waktu yang linear sehingga mempengaruhi pada O(t logt n) pada waktu pelaksanaan insert pada Btree. Berikut ini adalah pseudocodes proses insert dan split pada B-tree. B-Tree-Insert(T,k) r <- root[T] if (n[r] = 2t–1)then s <- Allocate-Node() root[T] <- s leaf[s] <- FALSE n[s] <- 0 c1 <- r B-Tree-SplitChild(s,1,r) B-Tree-InsertNonfull(s,k) else B-Tree-InsertNonfull(r,k)

i <- n[x] if (leaf[x])then while (i>=1 and k=1 and kkeyi[x])then i <- i + 1 B-Tree-InsertNonfull(ci[x],k) B-Tree-Split-Child(x,i,y) z <- Allocate-Node() leaf[z] <- leaf[y] n[z] <- t-1 for j<-1 to t-1 do keyj[z] <- keyj+t[y] if not leaf[y]then for j<-1 to t do cj[z] <- cj+t[y] n[y] <- t-1 for j<-n[x]+1 downto i+1 do cj+1[x] <- cj[x] ci+1 <- z for j <- n[x] downto i do keyj+1[x] <- keyj[x] keyi[x] <- keyt[y] n[x] <- n[x] + 1 Disk-Write(y) Disk-Write(z) Disk-Write(x) Contoh insertion pada B-tree Di bawah adalah contoh B-tree orde 2 dengan kunci nilai bilangan bulat. Kecuali untuk simpul akar khusus, setiap simpul pada orde 2 memiliki 2-4 kunci dan 3-5 pointer anak. Tempat kosong ditandai dengan “.”, menunjukkan kunci belum disimpan pada kunci.

B-Tree-Insert-Nonfull(T,k)

8

[ 57 . . .] | | +---------------+ +---------------------+ | | v v [ 14 40 . .] [ 72 84 . .] | | | | | | +--------+ | +----------+ +----------+ | +-----------+ | | | | | | v v v v v v [01 12 . .] [15 16 17 .] [47 56 . .] [58 60 61 .] [74 75 76 78] [85 86 99 .] Untuk menyisip kunci “59”, pertama kita mencari kunci tersebut. Jika 59 ditemukan, maka kunci sudah berada pada pohon dan insertion tidak perlu dilakukan. Sebaliknya, pencarian akan berakhir di simpul daun pada tingkat bawah di mana 59 akan diletakkan. Pada kasus di atas, simpul daun terdiri dari 58, 60 , 61, dan ruangan untuk kunci keempat, jadi 59 disisip dengan mudah ke dalam simpul daun dengan urutan : [58 59 60 61] Sekarang kita akan menyisip kunci 77. Pencarian menuju simpul daun di mana 77 akan dsisipkan. Akan tetapi simpul sudah

Before inserting 77 [ 72 84 . .] | | | -+ | +| | | v [74 75 76 78]

penuh dengan 4 kunci : 74.75.76,78. Menambahkan kunci lain akan melanggar aturan bahwa pohon tidak boleh memiliki lebih dari 4 kunci. Karena kondisi overflow ini, simpul daun dipisah menjadi dua. Dua kunci paling kiri diletakkan ke dalam simpul kiri, 2 kunci paling kanan diletakkan pada simpul kanan, dan kunci median disisip ke dalam simpul di atas simpul daun. Di sini menyisip 77 menyebabkan simpul 74-75-76-78 terpisah menjadi dua simpul dan 76 dipindah ke atas ke simpul orang tuanya yang mengandung 72 dan 84.

After inserting 77 [ 72 76 84 .] | | | | --+ | | +-| | +----+ +------+ | | v v [74 75 . .] [77 78 . .]

Dalam kasus ini, simpul orang tua terdiri hanya 2 kunci, menyisakan tempat untuk 76. Tetapi jika simpul orang tua penuh, maka simpul tersebut harus dipisahkan juga. Pemisahan mungkin terjadi sampai pada simpul akar. Ketika simpul akar dipisahkan, B-tree akan bertambah tingginya 1 tingkat, dan simpul akar baru terbentuk.

Contoh lainnya, menyisipkan huruf berikut pada B-Tree kosong berorde 5 : C NGAHEKQMFWLTZDPRXY S. Orde 5 berarti simpul lain selain akar memiliki 2-4 kunci. Empat huruf pertama disisip pada simpul yang sama.

9

Ketika kita mencoba menyisipkan H, ditemukan bahwa tidak ada tempat pada simpul ini. Maka kita memisahkan simpul menjadi 2 lalu memindahkan median G ke simpul akar yang baru. A dan C berada pada simpul lama dan H dan W ditempatkan pada simpul baru sebelah kanan dari simpul lama. Penyisipan E, K, dan Q tidak memerlukan pemisahan simpul. Penyisipan M memeelukan proses pemisahan. M menjadi kunci median sehingga dipindah ke simpul orang tua. Huruf F, W, L, T ditambahkan tanpa pemisahan. Ketika Z ditambahkan, simpul paling kanan harus dipsah. Median T

dipindahkan ke atas dalam simpul orang tuannya. (Dengan memindahkan kunci median, pohon akan tetap seimbang, dengan 2 kunci pada setiap simpul). Penyisipan D menyebabkan daun paling kiri dipisah. D adalah kunci median sehingga dipindah ke simpul orang tuanya. Huruf P, R, X, dan Y ditambahkan tanpa perlu pemisahan. Akhirnya ketika S ditambah simpul berisi N, P, Q, dan R dipisah dan mengirim median Q menuju simpul orangtua. Tetapi simpul orang tuanya juga penuh, sehingga dilakukan pemisahan, mengirimkan median M membentuk simpul akar baru.

10

11

3.3 Deletion Penghapusan kunci dari B-tree mungkin terjadi. Bagaimanapun juga, penanganan khusus dilakukan untuk memastikan Btree terjaga dengan baik. Beberapa kasus perlu diperhatikan. Jika penghapusan menyebabkan jumlah kunci pada simpul di bawah jumlah minimum, pelanggaran ini harus diperbaiki dengan menkombinasi beberapa simpul dan memungkinkan pengurangan tinggi pohon Jika kunci memiliki anak, anak-anak tersebut harus diatur ulang. Ada dua strategi yang populer dalam melakukan deletion pada B-tree : • mencari dan menghapus nilai, lalu strukturisasi ulang pohon tersebut berdasarkan invariannya • melakukan sekali pass menuruni pohon, tetapi sebelum memasuki simpul, strukturisasi ulang pada pohon sehingga bila kunci yang akan dihapus ditemukan, kunci dapat dihapus tanpa mengakibatkan kebutuhan strukturisasi ulang lagi. Ada dua masalah saat penghapusan elemen. Pertama, elemen dala simpul internal dapat bersifat sebagai pemsah terhadap simpul anaknya. Dan kedua, penghapusan elemen mungkin membuat jumlah elemen dan anak di bawah nilai minimum. Masing-masing permasalahan diatasi dengan pengaturan.

3.3.1 Deletion pada Simpul Daun • Dilakukan pencarian pada nilai yang inging dihapus. • Jika nilai berada pada simpul daun, dapat dengan mudah dilakukan penghapusan. Tetapi memungkinkan menyisakan terlalu sedikit elemen sehingga perubahan tambahan pada pohon perlu dilakukan.

3.3.2 Deletion pada Simpul Internal Setiap elemen pada simpul internak berlaku sebagai nilai pemisah antara dua subpohon, dan ketika elemen tersebut dihapus muncul dua kasus. Kasus pertama, kedua simpul anak kiri dan kanan dari elemen yang dihapus memiliki jumlah elemen minimum L-1 sehingga mereka dapat digabung menjadi simpul tunggal berisi 2L-2 elemen, yang tidak melebihi U-1 dan merupakan simpul legal. Kecuali ada pernyataan elemen bersifat unik, maka harus dilakukan penghapusan semua elemen yang sama secara rekursif. Kasus kedua, salah satu dari kedua simpul anak mengandung lebih dari jumlah elemen minimum. Kemudian separator yang baru untuk kedua subpohon ditemukan. Catatan, elemen terbesar subpohon kiri lebih kecil dari nilai separator dan elemen terkecil subpohon kanan lebih besar dari nili separator. Kedua elemen berada di simpul daun, dan

12

salah satunya dapat menjadi separator yang baru. • Jika nilai berada dalam simpul internal, pilih separator baru, pindahkan dari simpul daun asalnya, dan tempatkan kembali elemen yang telah dihapus dengan separator yang baru. • Hal ini telah menghapus sebuah elemen dari simpul daun sehingga sekarang ekivalen dengan kasus sebelumnya.

3.3.3 Penyeimbangan Setelah Deletion

Kembali

Jika penghapusan elemen dari simpul daun menyebabkan di bawah ukuran minimum, beberapa elemen harus didistribusi ulang agar semua simpul tidak dibawah ukuran minimum. Dalam beberapa kasus, pengaturan ulang akan memindahkan kekurangan pada simpul orang tuanya, dan redistribusi harus diaplikasikan secara iteratif ke atas pohon, bahkan mungkin samapai pada akar. Karena jumlah elemen minimum tidak berlaku pada akar, akar menjadi satu-satunya simpul yang kekurangan tanpa menjadi masalah. Strateginya adalah mencari saudara dari simpul yang kekurangan yang memiliki jumlah elemen lebih dari jumlah minimum dan mendistribusikan elemen kepada saudara yang lain sehingga semeua memiliki lebih dari jumlah elemen minimum. Hal ini akan mengubah separator dalam persaudaraan dari simpul orang tua juga. • Jika simpul saudara sebelah kanan dari simpul yang kekurangan memiliki lebih dari jumlah minimum elemen, pilih median dari separator dan nilai dalam kedua simpul sebagai separator baru dan letakkan ke simpul orang tuanya. • Redistribusi elemen yang tersisa ke anak kanan dan kiri. • Redistribusi subpohon dari kedua simpul pada paralel elemen redistribusi. Subpohon sendiri akan terplantasi keseluruhan dan tidak akan berubah jika dipindahkan ke orang tua yang berbeda, dan hal ini dapat dilakukan saat elemen diredistribusi.

• Jika simpul saudara di kanan simpul yang kekurangan memiliki jumlah elemen minimumm periksa simpul saudara sebelah kiri. • Jika keduanya hanya memiliki jumlah elemen minimum, buat elemen aru dengan semua elemen dari simpul yang kekuranggan, semua elemen berasal dari salah sati simpul saudaranya, dan separator dalam simpul orang tua daintara keduanya berkombinasi menjadi simpul saudara. • Pindahkan separator dari simpul orangtuanya, dan tempatkan kedua anak yang dipisahkan dengan simpul yang telah dikombinasi • Jika jumlah elemen di simpul orangtua menjadai di bawah minimum, ulnagi langkah-langkah di atas dengan simpul yang kekurangan, kecuali simpul akar. Contoh deletion pada B-tree Sebagai contoh, pada B-tree di bawah ini kita ingin menghapus “37” yang tidak berada pada simpul daun. “xx” menyatakan nilai kunci yang tidak menjadi masalah. Kita menelusuri pointer anak langsung ke sebelah kanan dari 37 untuk menemukan subpohon kanan dari 37, kemudian menelusuri pointer paling kiri setiap subdimpul sampai mencapai simpul daun. Kunci pertama dari daun adalah 41. Dengan menukar 37 dengan 41 kita dapat memindahkan 37 ke simpul daun untuk dihapus tanpa merusak urutan kunci atau pointer pada keseluruhan pohon. Saat kunci berada di daun, kita dapat menghapusnya. Jika paling sedikit n kunci ada di simpul, penghapusan selesai. Sebaliknya akan underflow karena tiap simpul (kecuali akar) harus mempunyai paling sedikit n kunci.

[ xx 37 xx xx ] | | +->[ xx xx xx xx ] | | +->[ xx xx xx xx ] | | +->[41 43 . .]

13

Jika sebuah simpul ubderflow, kita dapat meredistribusi kunci dengan meminjam beberapa dari simpul saudara. Contohnya, pada B-tree orde 3 di bawah kunci 67 dihapus menyebabkan simpul menjadi

underflow karena hanya tinggal memiliki 66 dan 88. Maka kunci dari simpul saudara kiri dipindahkan ke simpul orang uta dan didistribusi sehingga kedua daun memiliki 4 kunci.

Before deleting 67

After deleting 67

[ xx 55 xx ] | | +--------+ +----+ | | v v

[ xx 33 xx ] | | +---------+ ++ | | v v

[22 24 26 28 33 44] [66 67 88 . . .]

[22 24 26 28 . .] [44 55 66 88 . .]

Akan tetapi jika simpul yang kekurangan dan simpul saudaranya memiliki kurang dari 2n kunci untuk didistribusi, kedua simpul akan dikombinasi. Contohnya, di bawah kunci 52 dihapus dari pohon, sehingga menyebabkan ubderflow dan Before deleting 52 [ 35 45 55 . ] | | | | -+ | | +| | +-----+ +---+ | | v v [40 42 . .] [50 52 . .]

simpul saudaranya tidak dapat memberi kuncinya untuk redistribusi. Maka salah satu simpul dibuang dan simpul orang tua bergeser ke bawah dengan kunci lain untuk mengisi simpul tunggal.

After deleting 52 [ 35 55 . . ] | | | -+ | +| | | v [40 42 45 50]

Pada kasus di atas, memindahkan kunci 45 dari simpul orang tua menyisakan 2 kunci. Tetapi jika simpul orang tua hanya memiliki n kunci, maka simpul orang tua juga akan underflow ketika kunci simpulnya digeser ke bawah untuk bergabung dengan simpul daun. ekurangan dan simpul yang telah

berkombinasi dapat menyebar ke atas samapi ke simpul akar. Ketika kar kekurangan, B-tree menyusut tingginya satu tingkat dan simpul di bawah simpul akara yang lama berkombinasi membentuk akar baru. Contoh lainnya pada B-tree berikut

14

H dihapus. Karena H berada pada daun yang memiliki jumlah kunci lebih dari minimum, penghapusan mudah dilakukan. Selanjutnya menghapus T. T tidak berada pada simpul daun, maka cari suksesornya (kunci berikutnya dalam urutan menaik), yang merupakan W, dan memindahkan W untuk menggantikan T. Dengan cara tersebut yang harus kita lakukan adalah menghapus W dari daun. Berikutnya menghapus R. Walaupun R berada pada daun, penghapusan menyebabkan kekurangan pada daun. Jadi, suksesor W dari S (kunci terakhir pada simpul di mana deletion terjadi) digeser ke simpul orang tua, dan X digeser ke atas. Akhirnya, kita menghapus E yang menyebabkan banyak masalah. Walaupun

E berada dalam daun, penghapusan menyebabkan kekurangan dan simpul saudaranya hanya memiliki jumlah minimum. Dalam kasus seperti ini daun harus dikombinasi dengan kedua simpul saudara. Hal ini termasuk menggeser ke bawah kunci simpul orang tua yang berada di antara kedua daun. Pada contoh, dikombinasi daun yang mengandung F dengan daun berisi A C. Kita juga menggeser D ke bawah.Tentu saja, simpul orang tua hanya tinggal memiliki 1 kunci, G. Karena pada contoh tidak mungkin meminjam kunci dari simpul saudara, maka sekali lagi dilakukan kombinasi dengan simpul saudara dan menggeser M ke bawah. Dalam kasus ini, pohon berkurang ketinggiannya 1 tingkat.

15

16

4 Contoh Aplikasi B-Tree Salah satu penerapan struktur data B-tree adalah database atau basis data. Basis data ada koleksi data diatur dalam suatu cara yang memfasilitasi proses updating, pengambilan, dan pengelolaan data. Data dapat terdiri atas apa saja, termasuk nama, alamat, gambar, dan angka. Basis data sudah umum dan digunakan setiap hari. Contohnya, sistem pemesanan pesawat mungkin mengatur basis data penerbangan yang tersedia, para pelanggan, dan tiket. Seorang guru mungkin mengatur basis data nama dan nilai murid. Karena komputer berkembangcepat, dengan tepat memanipulasi, menyimpan, dan mengmabil data, basis data sering diatur secara eltronik dengan menggunakan database management system. Sistem pengelolaan basis data adalah komponen penting dalam operasi bisnis sehari-hari. Produk basis data contohnya Microsoft SQL Server, Sybase Adaptive Server, IBMDB2,dan Oracle melayani dasar dari sistem akuntnsi, sistem penyimpanan, sistem pencatatan medis, sistem pemesanan tiket pesawat, dan aspek-aspek penting bisnis modern lain yang tidak terhitung banyaknya. Basis data terdiri dari jutaan data dalam ukuran gigabyte. Sebagai contoh, TELSTRA, sebuah perusahaan telekomunikasi Australia, mengurus basis data tagihan pelanggan dengan 51milyar baris dan data sebanyak 4,2 terabyte. Supaya basis data berguna dan dapat digunakan, maka harus mendukung operasi seperti pengambilan dan penyimpanan secara cepat. Karena basis data tidak dapat diatur seluruhnya di memori, B-tree sering digunakan mengurutkan data dan akses yang cepat. Contohnya, mencari basis data yang tidak terurut terdiri dari n nilai kunci memiliki

waktu pelaksanaan kasus terburuk O(n). Jika data yang sama terurut dengan Btree, operasi pencarian yang sama terlaksana dalam O(log n). Untuk menjalankan pencarian sebuah data pada satu juta data, pencarian linear memerlukan paling banyak sebanding dengan 1.000.000. Jika data yang sama diurutkan dengan B-tree dengan tingkat minimum, 10.114 akan dibutuhkan pada kasus terburuk. Sangat jelas, meurutkan data dalam jumlah besar meningkatkan performa pencarian. Walaupun struktur pohon seimbang yang lain dapat digunakan, B-tree juga mengoptimasi waktu akses disk yang berhubungan dengan data dalam jumlah banyak.

5 Kesimpulan Kesimpulan yang dapat diambil dari pengkajian struktur data B-tree dan contoh penerapannya ini adalah : 1. Sebuah pohon disebut dengan Btree dengan derajat t apabila : a. semua daunnya memiliki ketinggian yang sama b. semua simpul kecuali akar memiliki paling sedikit t-1 kunci c. semua simpul kecuali akar memiliki paling sedikit 2t-1 kunci d. akar paling sedikit memiliki 1 kunci e. sebuah simpul dengan n kunci memiliki n+1 simpul anak 2. B-Tree adalah sebuah m-ary balanced search tree khusus yang digunakan dalam basis data karena strukturnya memungkinkan data yang disimpan untuk disisipi, dihapus, dan diambil nilainya. 3. B-Tree memiliki kelebihan dibanding implementasi

17

4.

5.

alternatif yang lain karena waktu akses dalam simpulnya cepat. Sebuah B-Tree didesain untuk digunakan pada disk. Sebuah Btree menyimpan banyak kunci di setap simpulnya sehingga dapat mengakses banyak kunci, dan faktor cabang pohon sangat tinggi sehingga pohon dengan ketinggian kecil dapat menyimpan kunci dalam jumlah yang sangat besar, yang dapat diakses hanya dengan beberapa operasi. Salah satu penerapan struktur data B-tree adalah database atau basis data.

DAFTAR PUSTAKA [1] Carlson, David. (2006). http://cis.stvincent.edu/html/tutorials/ swd/btree/btree.html. Tanggal akses : 2 Januari 2007 pukul 10:30 WIB [2] Liem, Inggriani. (2001). Diktat Struktur Data IF222 Kurikulum 1998. Jurusan Teknik Informatika, Institut Teknologi Bandung. [3] Munir, Rinaldi. (2004). Diktat Kuliah IF2151 Matematika Diskrit. Departemen Teknik Informatika, Institut Teknologi Bandung.

[4] Neubauer, Peter. (1999). B-Trees : Balanced Tree Data Structures. http://bluerwhite.org/btree. Tanggal akses : 2 Januari 2007 pukul 10:30 WIB [5] Paul E. Black. (2005). Dictionary of Algorithms and Data Structures [online]. U.S. National Institute of Standards and Technology. http://www.nist.gov/dads/HTML/btree .html. Tanggal akses : 2 Januari 2007 pukul 11:00 WIB [6] Ruskey, Frank. (2003). Information on B-Trees. http://www.theory.csc.uvic.ca/~cos/inf /tree/BTrees.html. Tanggal akses ; 3 Januari 2007 pukul 12:15 WIB [7] Semaphore Corporation. (2000). Btree Algorithms. http://www.semaphorecorp.com/btp/b 1k.html . Tanggal akses : 2 Januari 2007 pukul 10:30 WIB [8] Weisstein, Eric W. "B-Tree." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BTree.html . Tanggal akses : 3 Januari 2007 pukul 12:15 WIB [9] Wikipedia Foundation, Inc. (2006). http://en.wikipedia.org. Tanggal akses : 2 Januari 2007 pukul 10:30 WIB

18