Implementasi B-Tree dalam Secondary Storage

Pada tahun 1972, diciptakan sebuah metode indexing yang disebut B-Tree (Balanced Tree). Balanced Tree merupakan sebuah struktur data pohon yang memiliki ketinggian yang sama pada tiap daunnya. Tujuan awal dari pembuatan B-Tree sendiri adalah untuk memungkinkan penyimpanan banyak data, karena sifat B-Tree yang dapat memiliki node children lebih dari 2.

Implementasi B-Tree dengan secondary storage terjadi apabila kita hendak menyimpan suatu basis data yang cukup besar sehingga tidak cukup jika hanya tersimpan di memori (primary storage). Adapun hal-hal yang perlu diperhatikan dalam pengaplikasian struktur data ke dalam basis data, yaitu:

- Lama pencarian sebuah elemen. Data dengan ukuran yang besar atau data yang tidak tersimpan secara terurut akan memperlambat proses pencarian data pada.

- Pengindeksan data. Kita dapat meringkas waktu pencarian dengan hanya mencari data di blok tertentu sehingga tidak perlu memeriksa seluruh elemen.

- Penghapusan dan penambahan data. Penambahan data bisa berbahaya karena harus mengalokasikan tempat untuk data yang baru, yang berarti harus menggeser data-data yang sudah ada sebelumnya. Salah satu cara mengatasinya adalah dengan sengaja membiarkan sebagian memori tetap kosong, dan dipakai hanya jika ingin menambahkan elemen baru.

Sebagai contoh kasus, misal kita harus membuat program basis data untuk menyimpan data siswa SMA di Pulau Jawa, misalnya ada 2.000.000 data. Setiap entry terdapat nama, asal sekolah, alamat, dll. Asumsi setiap entry disimpan dalam sebuah record yang besarnya 512 byte. Sehingga total size file menjadi 1GB, di mana itu terlalu besar untuk disimpan dalam memory (primary storage)‏ dan perlu disimpan di disk (secondary storage). Jika kita menggunakan disk untuk penyimpanan, kita harus menggunakan struktur blok pada disk untuk menyimpan basis data tersebut. Disk dibagi menjadi blok-blok yang ukurannya sama, misal 8 KB (8.192 byte). Maka jumlah blok yang diperlukan adalah 1 GB / 8 KB per blok = 125,000 blok. Sehingga setiap blok dapat menyimpan 8,192 / 512 = 16 records.

Akses ke disk bisa 10.00 kali lebih lambat daripada ke main memory. Sehingga hal ini akan mendominasi running time. Untuk itu dibutuhkan teknik pencarian yang dapat meminimalkan jumlah akses ke disk. Teknik ini berupa multiway search tree, dan lebih kita kenal bernama B-Tree. Dengan sifat B-Tree kita dapat menjaga data tetap terurut untuk akses sekuensial, menggunakan indeks hierarki untuk meminimalisir akses ke media penyimpanan, menggunakan blok penuh atau parsial untuk mempercepat penambahan dan penghapusan data, meminimalisir proses yang terbuang dengan memastikan semua simpul setidaknya setengah penuh. Indeks juga disesuaikan mengggunakan algoritma rekursif. Jadi sesuai kasus di atas, setiap node akan memuat 1 blok. Hal ini akan meminimalkan block transfer.

Referensi:

• http://aren.cs.ui.ac.id/sda/resources/sda2010/13_btree.pdf diakses pada 9 Maret 2014
• http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2011-2012/Makalah2011/Makalah-IF2091-2011-029.pdf diakses pada 9 Maret 2014

Ingin blogmu dibaca? Baca dulu ini

    Saya bingung mau nulis apa. Kata orang yang pintar menulis, kebingungan itu bisa jadi topik untuk bahan tulisan. Tapi kalau kata orang yang kurang pintar menulis, lebih baik nggak usah nulis. Jadi saya memilih untuk tidak menulis. Saya ngetik.
     Cerita tentang menulis, saya suka membaca blog teman-teman yang punya hobi nulis dan masing-masing punya cara menyampaikan yang berbeda. Ada yang pakai bahasa puitis, ada yang formal banget, ada yang sok nge-inggris dan banyak yang pake bahasa sehari-hari yang lebih nyantai. Tapi bahasa nyantai kalau isinya nggak mutu sama aja kan? Masa iya kita ngebacain blog yang isinya semua cuma curhatan tentang mantan pacar dia yang udah lama banget putusnya. Percayalah, baca blog kaya begitu cuma nambah dosa.
    Nah, supaya blogmu sering dibaca, isilah dengan tulisan yang menarik. Misalnya:

• Informasi-informasi terbaru tapi bukan hasil copy-paste blog orang. Jaga harga diri juga dong.
• Resep makanan atau kue-kue yang lagi nge-trend, seperti rainbow cake, red velvet, dan kue eksis lainnya. Selanjutnya, silakan upload ke instagram dan jb-in orang-orang, “sist, mampir ya ke IG dan blog kita ada jual ranbow cake uenak banget.” Selamat mencoba.
• Info k-pop. Pasti blogmu diburu oleh penggemar-penggemar fantastis yang kerjaannya cuma teriak “Kyaaa, oppa! >,<” Saran sih, mumpung 'oppa gangnam style' masih jadi trending topic twitter, coba aja bikin video lipsync-nya plus jogetnya yang lebih ekstrim. Niscaya, kamu akan dapat penggemar juga.
• Bikin review pake bahasa inggris. Dijamin blog kamu akan sering dikunjungi orang-orang bule. Lumayan kan, kalo ada yang ngeliat visitors kamu rata-rata orang Eropa kan kesannya gimana gitu.

Nggak penting ya? Iya deh, saya memang selalu nggak penting :v *meluk lutut*