Manfaat Penggunaan B-Tree pada Secondary Storage

Pengertian B-Tree dan Secondary Storage

B-Tree yang merupakan kependekan dari Balanced Tree merupakan bentuk umum dari red black tree. B-Tree dirancang seimbang sehingga memiliki ketinggian yang sama pada setiap daunnya untuk memudahkan pencarian. Tidak seperti binary search tree (BST) yang hanya memperbolehkan treenya memiliki dua child, internal node pada B-Tree boleh memiliki lebih dari dua child. Dengan demikian, B-Tree memungkinkan untuk menyimpan banyak data dalam satu node.

Secondary storage merupakan media penyimpanan komputer yang berupa disk. Secondary storage memiliki kapasitas yang lebih besar, harga yang lebih murah, dan akses yang lebih lambat dibandingkan dengan primary storage. Data pada secondary storage tidak dapat diakses langsung oleh CPU, melainkan harus dicopy terlebih dahulu ke primary storage.

Implementasi

Karena keterbatasan mekanik, suatu akses pada secondary storage akan membutuhkan waktu yang relatif lama. Akses ke disk diperkirakan 1000x lebih lambat dibandingkan akses ke main memory atau primary storage. Di sisi lain, main memory tidak memiliki kapasitas yang cukup besar. Oleh karena itu manusia tentu membutuhkan disk untuk menyimpan berbagai macam data.

Bisa diambil contoh suatu data di yellow page suatu wilayah yang tiap entrinya terdiri dari data pribadi berupa nama, nomor telepon, serta alamat. Katakanlah ada 4.000.000 penduduk dan masing-masing entri disimpan dalam sebuah record yang besarnya 512 byte. Maka total ukuran file yang dibutuhkan adalah sebesar 4.000.000 x 512 = 2.048.000.000 atau sekitar 2 GB. Ukuran file ini akan terlalu besar jika disimpan dalam main memory sehingga perlu disimpan dalam disk. Sementara bisa dibayangkan jika yang didata adalah ratusan juta data, maka akan dibutuhkan disk yang lebih besar lagi kapasitasnya.

Ketika menggunakan disk untuk penyimpanan, akan digunakan struktur blok pada disk untuk menyimpan data. Blok merupakan satuan unit transfer antar disk dengan memory agar dapat dibaca pada komputer. Suatu secondary storage akan dibagi menjadi blok-blok yang berukuran sama. Katakanlah 1 disk block berukuran 8.192 byte atau sekitar 8 KB. Maka akan diperlukan 2 GB/8 KB per blok = 250.000 blok. Dimana setiap blok akan menyimpan sebesar 8.192/512 = 16 records.

Semakin membutuhkan disk berkapasitas besar, maka permintaan terhadap akses data pada disk atau secondary storage juga semakin tinggi. B-Tree adalah metode indexing data yang memungkinkan untuk memperkecil waktu akses data pada suatu disk. B-Tree yang dapat menyimpan banyak data dalam satu node akan memungkinkan jumlah subtree dari B-Tree dapat sangat banyak. Karena itulah B-Tree sangat cocok digunakan dalam pengelolaan data dalam disk. Karena didesain memiliki banyak cabang, B-Tree dapat meminimalisasi jumlah akses terhadap disk.

B-Tree termasuk pada teknik pencarian “multiway search tree” yang dapat meminimalkan jumlah akses ke disk. Setiap node akan disesuaikan dengan ukuran blok pada disk. Mengacu pada contoh yang telah diuraikan sebelumnya, maka 1 node akan memuat 1 blok atau 8 KB. Hal ini bertujuan untuk meminimalkan jumlah blok transfer. Pada node-node B-Tree, data disimpan secara terurut agar mempermudah pencarian sehingga waktu yang digunakan lebih efisien. B-Tree juga memberi indeks pada blok-blok tertentu sehingga pencarian tidak dilakukan di seluruh data namun hanya pada blok-blok tertentu. Pemberian indeks ini dilakukan B-Tree dengan algoritma rekursif.

Referensi :

~. 2007. Bab 2 : Landasan Teori. Diunduh dari http://thesis.binus.ac.id/Asli/Bab2/2007-2-00213-IF-Bab%202.pdf pada 4 Maret 2014 pukul 11.49.

Manurung, Ruli dan Azurat, Ade. 2007. IKI 20100 : Struktur Data dan Algoritma “B Tree”. Diunduh dari http://aren.cs.ui.ac.id/sda/resources/sda2010/13_btree.pdf pada 27 Februari 2014 pukul 13:55.

Mushofan, Aldyaka. 2013. Makalah IF 2120 Matematika Diskrit – Sem. I Tahun 2013/2014 “B-Tree dan Penerapan di Basis Data”. Diunduh dari http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2013-2014/Makalah2013/MakalahIF2120-2013-104.pdf pada 27 Februari 2014 pukul 13:57.

Wahyu, Pakasius. 2011. Makalah IF 2091 Struktur Diskrit – Sem. I Tahun 2011/2012 “Cara Kerja B-Tree dan Aplikasinya”. Diunduh dari http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2011-2012/Makalah2011/Makalah-IF2091-2011-029.pdf pada 4 Maret 2014 pukul 11.43.

 dibuat untuk memenuhi Tugas I Analisis dan Desain Algoritma II,

4 Maret 2014