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.
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.
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
referensi:
Introduction to Algorithm, third edition
"Sehingga untuk data yang besar proses penyimpanan tidak mungkin dilakukan di secondary memory"
BalasHapusItu memang gitu atau maksudnya "..tidak mungkin dilakukan di main memory" mas?
ah, iya, haha, typo, makasih2
BalasHapus