Organisasi Berkas Relatif

Suatu cara pengorganisasian sekumpulan record yang membutuhkan akses sebuah record secara cepat disebut dengan organisasi berkas relative. Tidak ada hubungan secara fisik dengan urutan record karena tidak diperlukan penyortiran record berdasarkan pada nilai key. Dalam penyimpanan sekundernya sangat dianjurkan menggunakan DASD (Direct Access Storage Device) tidak pada SASD (Sekunder Access Storage Device), contoh media penyimpanannya adalah pada magnetic tape atau pada Drum.

Keuntungan dalam menggunakan berkas relative diantaranya adalah:
• Record dapat di update langsung tanpa harus meerekam kembali record tersebut.
• Akses record dapat dilakukan secara langsung
• Dapat meretrieve, delete, insert dan modifikasi tanpa mempenngaruhi record lain pada berkas yang sama.

Teknik dasar fungsi pemetaan:
1. Direct mapping (Pemetaan Langsung)
2. Directory Lookup (Pencarian Tabel)
3. Calculation (Kalkulasi)

Pada saat ini kita hanya akan membahas teknik kalkulasi pada fungsi pemetaan beserta cara mengatasi benturan pada teknik tersebut.

Teknik Kalkulasi Alamat

Dengan mengubah jangkauan nilai key menjadi sejumlah kecil alamat relative merupakan dasar pemikiran dari teknik kalkulasi.

Dalam penggunaan pengalamatan secara relative ini terdapat suatu kelemahan. Kelemahan itu adalah pada jumlah ruang yang disediakan untuk menyimpan nilai key harus sebanyak jangkauan nilai key, karena apabila tidak sesuai atau seimbang antara banyak ruang dengan jangkauan nilai key maka akan terjadi benturan. Benturan atau collusion ini adalah ditemukannya alamat relative yang sama pada nilai key yang berbeda.


R(k1) = R (k2) Disebut benturan atau
k1  k2 Collusion.

Teknik – teknik yang digunakan untuk mengatasi benturan pada teknik kalkulasi:

• Scatter storage techniques
• Randomizing technique
• Key-to-address transformation methods
• Direct addressing techniques
• Hash table methods
• Hashing




Scatter storage technique

Scatter storage technique adalah teknik dengan mengurangi lama waktu yang dibutuhkan untuk menemukan nilai key pada berkas atau memasukkan kembali nilai key pada berkas. Efisiensi dari scatter storage device teramat sangat bergantung pada metode yang digunakan dalam pemecahan masalah kalkulasi, metode yang biasa digunakan adalah search methods.

Randomizing technique

Berdasarkan teori Randomizing technique dilakukan secara manual contohnya seperti mengocok kartu bridge ataupun memutar roulette wheel, namun pada saat ini sudah banyak digunakan secara otomatis. Diinspirasi dari metode probabilistic sehingga menjadikan area bebas dari tubrukan atau benturan teknik ini dapat mempermudah dalam pencarian suatu solusi.

Key-to address transformation methods

Merupakan suatu Teknik yang digunakan dalam mengkoreksi kesalahan suatu kode. hal ini dilakukan untuk dapat menyelesaikan suatu masalah yang berupa suatu file besar, dalam pendekatan baru ke file menangani masalah digambarkan dengan suatu yang didesain khusus untuk menunjukan kelayakan dari Efektifitas merupakan suatu lebih lanjut diilustrasikan dengan membandingkan hasil ujian yang didapat dari simulasi peritungan,yang memakai data khas,terhadap nilai-nilai yang dihitung dari model ideal.

Direct addressing techniques

Dalam menangani langsung suatu instruksi yang memberitahukan dimana nilai tersebut dapat ditemukan, tetapi nilai itu sendiri dalam memori. Dalam sebuah bahasa tingkat tinggi, langsung menangani sering digunakan untuk hal-hal seperti variabel global.
Semua instruksi lain yang diperlihatkan menggunakan pengalamatan langsung, yang berarti bahwa data yang telah direferensikan sebenarnya dan disimpan dalam struktur lain, baik sebuah register atau lokasi memori.

Hash table methods

Tabel hash merupakan salah satu solusi yang tepat dalam menyelesaikan masalah pencarian.Dan yang saya tahu Tabel hash itu, seperti HashMap,digunakan untuk menyimpan pasangan kunci/nilai. Jika kita mengetahui kuncinya, maka kita bisa mencari nilainya dan menghubungkan suatu kunci-kunci di dalam table tersebut. Fungsi hash digunakan untuk mengubah kunci ke indeks (hash) dari array elemen (dalam slot) dimana nilai yang sesuai yang akan dicari.

Hashing

Terdapat beberapa keuntungan dalam penggunaan teknik hashing yang diantaranya adalah nilai key yang dapat digunakan langsung karena key tersebut diterjemahkan kedalam sebuah alamat dan bila berkas direorganisasi maka fungsi hashnya berubah tetapi key tetap. Selain memiliki keuntungan teknik ini juga memiliki kelemahan yaitu membutuhkan waktu yang lama untuk implementsi dan mengatasi benturan.

Beberapa fungsi hash yang biasa digunakan:

1. Division Remainder
Dalam menentukan alamat relatifnya fungsi ini menggunakan operasi pembagian modulo (MOD) dan DIV.
2. Mid Square
Pada fungsi ini penentuan alamat relative didapatkan dengan melakukan operasi pengkuadratan pada nilai key yang nantinya akan diambil nilai tengah dari hasil pengkuadratan.
3. Folding
Pada fungsi ini penentuan alamat relative didapatkan dengan membagi key menjadi beberapa bagian dan menjumlahkan bagian – bagian tersebut.

Hashing menggunakan beberapa metode dalam mengatasi benturan diantaranya:

• metode Open Addressing
• metode Chaining
• metode Coalesced Hasing
• metode Chained Progressive Overflow
• metode Bucket


sumber : Google