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
