Implementasi B-tree dalam Penyimpanan Sekunder

Pengertian struktur data dalam ilmu komputer adalah cara penyimpanan, penyusunan dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien. Struktur data sangat banyak macamnya, salah satu yang akan saya bahas adalah B-tree. Selain itu saya juga akan membahas pengimplementasiannya dalam penyimpanan sekunder. B-tree adalah struktur data pohon yang membuat data diurutkan dan memungkinkan pencarian, akses sekuensial, penyisipan, dan penghapusan dalam waktu singkat. B-tree dapat dioptimalkan untuk sistem yang membaca dan menulis blok data yang besar. Hal ini umumnya digunakan dalam basis data dan sistem berkas (file system).Secara struktur, B-tree sama dengan pohon pencarian biner. Bedanya, B-tree bersifat multiway, artinya setiap simpul dapat memiliki lebih dari 2 anak.  

 Gambar 1. B-tree 

B-tree memiliki keunggulan dibandingkan implementasi alternatif yang lain yaitu waktu akses simpul internal lebih cepat dari waktu akses antar simpul. Dengan memaksimalkan jumlah simpul anak pada setiap simpul internal, ketinggian pohon berkurang, jarang terjadi penyeimbangan kembali sehingga efisiensi meningkat.

B-tree sering digunakan dalam media penyimpanan sekunder. Media penyimpanan sekunder adalah tempat penyimpanan data dan program oleh pengguna. Data dan program yang ada di media penyimpanan sekunder tidak akan hilang ketika sumber daya mati. Beberapa contoh media penyimpanan sekunder yaitu disket, CD, flashdisk,  dan harddisk. Media penyimpanan sekunder memiliki kecepatan akses yang lebih rendah dibandingkan media penyimpanan utama seperti RAM dan cache.

Cara Kerja B-tree

Dalam B-tree, simpul internal dapat memiliki sejumlah simpul anak dalam rentang yang ditentukan. Contohnya pada 2-3 B-tree, maka setiap simpul internalakan memiliki 2-3 simpul anak.  Ketika data dimasukkkan atau dihapus dari node, jumlah simpul anak akan berubah. Untuk mempertahankan rentang yang telah ditentukan, simpuldapat bergabung atau berpisah. Karena jumlah node anak bebas, maka B-tree tidak perlu menyeimbangkan kembali seperti struktur data pohon yang lain. Akan tetapi akan struktur data B-tree akan menyisakan ruang, karena simpul tidak sepenuhnya penuh. 

Untuk meningkatkan kecepatan pencarian data, sebuah B-tree menyimpan banyak kunci di setiap simpulnya. Dengan ini, maka media penyimpanan sekunder dapat mengakses banyak kunci dalam waktu bersamaan. Selain itu, cabang pada B-tree juga sangat banyak (dalam prakteknya lebih besar dari 1000) yang menyebabkan ketinggian B-tree rendah. Hal ini yang menyebabkan B-tree dapat menyimpan kunci dalam jumlah besar.

Referensi : 

1.http://en.wikipedia.org/wiki/B-tree
2.http://informatika.stei.itb.ac.id/~rinaldi.munir/Matdis/2011-2012/Makalah2011/Makalah-IF2091-2011-029.pdf