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