B-Trees dan Implementasinya

Jadi ceritanya pak Arif dosen Analisis dan Desain Algoritma lagi ngasih tugas ke mahasiswanya buat bikin yaa semacam artikel, tentang B-Tree dan Implementasinya pada secondary memory. Artikelnya mesti ditulis di blog dan linknya ntar dikasih ke paknya.

Karena aku males bikin blog baru, ya sudahlah, pake blog ini aja. Jadi kalau ada yang gak ngerti apa itu B-tree atau istilah-istilah yang ada di sini ya udah gak usah di baca artikel ini, ini kan spesial untuk Pak Arif :p

B-Tree 
Jadi B-Tree itu adalah salah satu struktur data berbentuk tree yang balance, alias seimbang. Ada banyak sebenernya jenis tree yang balance, seperti red-black tree atau avl tree.

Yang khas di B-Tree, setiap node-nodenya (kecuali node root) bisa diisi lebih dari 1 key. Banyak key yang bisa disimpan di sebuah node ditentukan oleh tree degree yang disimbolkan t (t ≥ 2). Sebuah node mampu menampung minimal t-1 key dan maksimal 2t-1 key. selain itu B-Tree juga punya leaf dengan kedalaman yang sama.

Efek dari keberadaan degree ini jadinya tinggi tree bisa jadi lebih pendek. Lho kok bisa? Ya, dengan degree ini tinggi tree bisa dipendekkan dengan menambah lebar pohon (yang dipengaruhi t). ketinggian dan lebar tree inilah yang digunakan untuk memperhitungkan waktu akses pada implementasinya di secondaru memory. Untuk info lebih jelas dan detail tentang definisi B-Tree bisa lihat langsung di sini -> http://en.wikipedia.org/wiki/B-tree

B-Tree dan Secondary Memory

Kalau istilah Indonesianya, Main Memory itu RAM, sedangkan Secondary Memory itu Harddisk Internal atau lebih gampang disebut disk. Seperti kita tahu main memory punya kecepatan akses yang jauh lebih cepet ketimbang kecepatan secondary memory, ini dikarenakan fisik dari main memory yang berupa chip sedangkan disk berbentuk piringan dengan hardware yang bergerak. Tapi main memory punya kapasitas memory yang jauh lebih kecil ketimbang kapasitas secondary memory. Sehingga untuk data yang besar proses penyimpanan tidak mungkin dilakukan di main memory.

Nah, agar kecepatan akses di secondary memory atau disk bisa lebih cepat, dibutuhin konsep peletakan data pada disk yang tepat, salah satunya menggunakan B-Tree ini.

Pada saat kita akan mengakses sebuah data pada komputer, maka proses pencarian akan melakukan pencarian pada main memory terlebih dahulu, ini dilakukan agar tidak terjadi pencarian yang lebih memakan waktu di secondary memory jika data tersebut ada di main memory, keberadaan data di main memory biasanya karena data sudah pernah dibaca sebelumnya dan tidak terhapus (cek lagi materi kuliah organisasi dan arsitektur komputer). Jika tidak ditemukan, data akan dicari pada secondary memory.

Dalam implementasinya setiap node pada B-Tree ber-degree t memiliki minimal t-1 key dan t pointer yang menunjuk ke address child dari node tersebut. Root node sebuah B-Tree berada pada main memory sedangkan child-childnya ada pada disk. Sehingga proses pembacaan akan melalui main memory dulu, sesuai proses di atas. Jika data tidak ditemukan proses berjalan mencari pada child-childnya yang berada pada secondary memory.

Saat proses pembacaan data dari secondary memory setiap node B-Tree menampung key sebesar ukuran page pada disk. Sehingga setiap kali proses pembacaan disk, jumlah data yang terbaca adalah maksimal (seukuran page).

referensi:
Introduction to Algorithm, third edition