[Postingan kali ini agak berbeda dari postingan sebelum-sebelumnya. Lebih (sedikit) serius dan tidak 'macem-macem'. Tentu saja hal ini dikarenakan postingan kali ini adalah sebuah tugas. Tugas kuliah Analisis dan Desain Algoritma II tentang hubungan antara B-tree dan disk. Semoga bermanfaat. -- Maaf pak, saya pembukaan dulu.. ]
Sudah menjadi hal biasa, entah itu file tugas, file program, atau bahkan file hiburan yang kita miliki pasti sudah mencapai "sekian" GB. Tentu saja hal ini terlalu besar apabila akan kita simpan dalam memori (primary storage), sehingga diperlukan suatu disk (secondary storage) untuk tempat penyimpanannya.
Apabila kita menggunakan disk untuk menyimpannya, akan terjadi banyak hal mekanis yang dapat memperlambat suatu proses. Kita harus menggunakan struktur blok pada disk untuk menyimpannya - misal suatu basis data. Disk akan dibagi menjadi beberapa blok yang ukurannya sama, dimana blok itu adalah satuan unit transfer antara disk dengan memori.
Perlu kita ketahui. sebuah akses ke disk diperkirakan 10.000 kali lebih lambat daripada akses ke main memory yang bisa disetarakan dengan 200.000 instruksi. Jadi, jumlah akses ke disk akan mendominasi running time. Oleh karena itu, dalam hal ini akan dibutuhkan sebuah teknik pencarian yang dapat meminimalkan jumlah akses ke disk dan dapat me-manage data (yang biasanya berukuran besar) dari harddisk.
Dan teknik yang dibutuhkan dalam hal di atas adalah B-tree, pohon yang bersifat multiway (tiap simpul dapat memiliki lebih dari dua anak). B-tree adalah sebuah balanched search tree yang dapat menyimpan data secara berurutan dan biasa digunakan dalam basis data karena strukturnya yang memungkinkan untuk pencarian, akses sekuensial, penambahan, serta penghapusan dalam waktu yang relatif singkat, yang setiap simpulnya terdiri dari (m/2) sampai m buah simpul anak.
Sebuah B-Tree didesain untuk digunakan pada disk. Disk hanya dapat membaca dan menulis blok data yang berukuran tetap dan besar sekaligus. Sebuah B-tree dapat menyimpan banyak key di setiap simpulnya, sehingga sebuah disk dapat mengakses banyak key dan branching factors pohon sangat tinggi, sehingga pohon yang kecil akan dapat menyimpan key dalam jumlah yang sangat besar yang dapat diakses hanya dengan beberapa operasi.
Jumlah akses disk diukur dari jumlah page informasi yang dibutuhkan untuk 'dibaca dari' atau 'ditulis ke' disk. Kita ketahui bahwa waktu akses disk itu tidak konstan - bergantung pada jarak antara track sekarang dan track yang diinginkan dan rotasi awal disk juga.
Karena data yang tangani begitu besar, semua data tidak masuk ke main memory secara serentak. Algoritma B-tree akan menyalin page yang dipilih dari disk ke main memory yang diperlukan dan menulis kembali ke page disk yang telah berubah. Dan karena algoritma B-tree hanya membutuhkan sejumlah page yang konstan dalam main memory setiap saat, maka ukuran main memory tidak membatasi ukuran B-tree yang dapat ditangani.
Berikut adalah model operasi disk dalam bentuk pseudocode :
x kita jadikan pointer ke objek. jika objek sudah di main memory komputer, maka kita dapat mengarahkan field ke objek seperti biasa : key[x] misalnya. Jika objek menunjuk pada x yang terletak dalam disk, bagaimanapun, maka kita harus melakukan operasi DISK-READ(x) untuk membaca objek x ke dalam main memory sebelum field-nya dapat dirujuk. (Kita asumsikan bahwa jika x sudah di main memory, maka DISK-READ(x) tidak memerlukan akses disk). Demikian pula, operasi DISK-WRITE(x) digunakan untuk menyimpan berbagai perubahan yang akan telah dibuat ke field objek x.
Karena kebanyakan running time sistem algoritma B-tree ditentukan terutama oleh jumlah operasi DISK-READ dan DISK-WRITE yang dilakukan. Sehingga layak untuk menggunakan operasi ini secara intensif dengan memintanya untuk membaca dan menulis informasi sebanyak mungkin. Jadi, sebuah simpul B-tree biasanya sebesar keseluruhan disk page.
Untuk B-tree besar yang disimpan pada disk, branching factors antara 50 dan 2000 sering kalli digunakan, tergantung ukuran relatif key ke ukuran sebuah page. Sebuah branching factors yang besar mengurangi height dari pohon dan jumlah akses disk yang diperlukan untuk menemukan beberapa key.
Sumber Referensi :
