Organisasi File
Organisasi file
Element pokok perancangan system akses adalah cara record-record diorganisasikan atau distrukturkan.
Beberapa criteria umum untuk pemilihan organisasi file adalah [WIE-87]
• Redudansi yang kecil
• Pengaksesan yang cepat
• Kemudahan dalam memperbaharui
• Pemeliharaan yang sederhana
• Kehandalan yang tinggi
Terdapat enam organisasi dasar, kebanyakan organisasi file system termasuk salah satu atau kombinasi kategori-kategori ini. Enam organisasi pengaksesan file secara dasar adalah sebagai berikut :
1. File pile (pile file)
2. File sekuen berindeks (indexed-sequenstial file)
3. File ber-hash (hashed file)
A. PILE FILE
Pembahasan struktur file diketahui bahwa struktur dasar paling dasar sebuah file adalah pile dan file sekuensial. File pile atau file tumpukan merupakan struktur paling sederhana. Struktur ini jarang digunakan secara praktis tapi merupakan basis evaluasi struktur-struktur lain. Properti struktur pile Data tidak dianalisis, dikategorikan, atau harus memenuhi definisi atau ukuran field tertentu Panjang rekord dapat bervariasi dan elemen-elemen data tidak perlu serupa. Karakteristik struktur pile Biasanya data ditumpuk secara kronologis Tak ada keterkaitan antara ukuran file, record, dan blok Elemen data dapat beragam, dapat berbeda untuk tiap record ( berisi attribut lain ). Data harus disimpan secara lengkap beserta nama attributnya, tidak Cuma nilai atributnya.
‘Komponen file pile hanya berisi data’
Struktur dan pengaksesan Rekord berelasi dengan suatu objek atau kejadian di dunia nyata. Rekord berisi elemen-elemen ( field-field) data dan tiap elemen data perlu mempunyai identifikasi. Identifikasi pada pile adalah berupa nama atribut secara ekplisit. Misalnya: Tinggi = 163, Dimana, nilai elemen data adalah 163 dan nama deskripsi adalah tinggi. Tiap elemen data di pile berbentuk tuple dua komponen disebut pasanagn nama atribut – nilai atribut ( atribute name – value atribute ).
Format record
Sejumlah pasangan untuk mendefinisikan objek dan mengasosiasikan data dengan objek. Contoh :
|nama=Nurman,jurusan=IF,alamat=Sadang Serang 64, umur=24, tinggi=163.
ketika informasi akan diambil, pemilihan record dengan menspesifikasikan di argumen pencarian.
Penggunaan file pile
File pile merupakan struktur dasar dan tak berstruktur. Struktur ini memberikan fleksibilitas penuh. Struktur ini menggunakan ruang penyimpanan dengan baik saat data berukuran dan berstruktur beragam. Struktur ini sangat jelek untuk pencarian record tertentu. Berbagai penggunaan dari file pile, diantaranya :
File-file sistem
File log ( mencatat kegiatan )
File-file penelitian / medis
Config.sys
.
B. INDEX SEQUENTIAL FILE
Index Sequential File merupakan perpaduan terbaik dari teknik sequential dan random file. Teknik penyimpanan yang dilakukan, menggunakan suatu index yang isinya berupa bagian dari data yang sudah tersortir. Index ini diakhiri denga adanya suatu pointer (penunjuk) yang bisa menunjukkan secara jelas posisi data yang selengkapnya. Index yang ada juga merupakan record-key (kunci record), sehingga kalau record key ini dipanggil, maka seluruh data juga akan ikut terpanggil. Untuk membayangkan penyimpanan dan pembacaan data secara sequential, kita bisa melihat rekaman lagu yang tersimpan pada kaset. Untuk mendengarkan lagu kelima, kita harus melalui lagu kesatu, dua, tiga dan empat terlebih dahulu.Pembacaan seperti inilah yang disebut sebagai sequential atau berurutan. Apabila lagu-lagu yang ada kemudian disimpan didalam compack-disk, maka untuk mendengar kan lagu yang kelima bisa langsung dilakukan (dibaca secara random). Disamping itu, dengan compack-disk juga bias dilakukan pembacaan secara berurutan atau sequential. Compack disk menyimpan lagu secara random. Untuk membayangkan penyimpanan data dengan menggunakan teknik index sequential ini, kita bisa melihat daftar isi pada sebuah buku. Pada bagian atas disebut sebagai index data yang berisi bagian dari data yang ada. Index data kemudian diakhiri dengan pointer yang menunjukkan posisi keseluruhan isi data.
Keuntungan dari Index Sequential file
Sangat cocok untuk digunakan menyimpan batch data ataupun individual data. Dibanding sequential file, pemanggilan data menjadi lebih cepat.
Kelemahan dari Sequential file
Access (pemanggilan) data tidak bisa disamakan dengan random (direct access file). Memerlukan adanya ruangan extra didalam memory untuk menyimpan index data. Memerlukan adanya hardware dan software yang lebih kompleks.
E. HASHED FILE
Metode penempatan dan pencarian yang memanfaatkan metode Hash disebut hashing atau ‘Hash addressing’ dan fungsi yang digunakan disebut fungsi hashing / fungsi Hash. Fungsi hashing atau fungsi Hash inilah yang dapat menjadi salah satu alternatif dalam menyimpan atau mengorganisasi File dengan metode akses langsung. Fungsi Hash berupaya menciptakan “fingerprint” dari berbagai data masukan. Fungsi Hash akan mengganti atau mentransposekan data tersebut untuk menciptakan fingerprint, yang biasa disebut Hashvalue (nilai Hash). Hash value biasanya akan digambarkan sebagai suatu string pendek yang terdiri atas huruf dan angka yang terlihat random (data biner yang ditulis dalam notasiheksadesimal). Berkaitan dengan upayanya untuk menciptakan “fingerprint”, fungsi Hash digunakan juga pada algoritma enkripsi untuk menjaga integritas sebuah data.
Dalam konsepnya modern ini –selain digunakan pada penyimpanan data-, fungsi Hash adalah sebuah fungsi matematika, yang menerima masukan string yangpanjangnya sebarang, mengambil sebuah panjang variable dari string masukantersebut –yang disebut pre-image, lalu mekonversinkannya ke sebuah stringkeluaran dengan ukuran tetap (fixed), dan umumnya lebih pendek dari ukuran string semula, yang disebut message digest.
Pada penggunaan fungsi Hash, saat keadaan tertentu dapat terjadi tabrakan (coallision) pada home address yang dihasilkan. Yaitu saat munculnya nilai Hash yang sama dari beberapa data yang berbeda. Untuk mengantisipasi keadaan ini ada beberapa metode yang dapat digunakan, seperti perubahan fungsi Hash atau mengurangi perbandingan antara jumlah data yang tersimpan denganslot address yang tersedia. Hal-hal tersebut dapat meminimalisir tabrakan, tetapi tidak menghilangkannya. Kita tetap memerlukan collision resolution –sebuah prosedur untuk menempatkan data yang memiliki address yang sama.
1. Konsep-Konsep File Hashed
1.Organisasi file dengan metode akses langsung (direct acsess ), yang menggunakan suatu fungsi untuk memetakan key menjadi address
2. fungsi yang digunakan disebut fungsi hash/KAT (key to address transformation)
3. Address yang dihasilkan dari hasil perhitungan fungsi hash disebut dengan istilah home address
4. Jadi, terdapat dua komponen file hash :
Ruang rekord, yang terdiri atas m slot address
Fungsi hash, yang mentransformasi key menjadi address
5. Transfomasi key akan mudah jika key telah berupa nilai integer, untuk key berupa karakter alphanumerik terdapat proses prakondisi untuk mengubahnya menjadi suatu nilai integer.
2. Macam- Macam Fungsi Hashed
Fungsi Hash diimplementasi untuk mengkonversi himpunan kunci rekaman (K) menjadi himpunan alamat memori (L). Bisa dinotasikan dengan H : K -> L
Aspek yang perlu dipertimbangkan dalam pemilihan fungsi Hash adalah :
• fungsi Hash harus mudah dan cepat dihitung
• fungsi Hash sebisa mungkin mendistribusikan
posisi yang dimaksud secara uniform sepanjang himpunan L sehingga collision yang mungkin terjadi dapat diminimalkan.
3. Tabrakan
Dengan menggunakan hashing, maka hubungan korespondensi satu-satu antara record key dengan alamat record akan hilang. Selalu timbul kemungkinan dimana terdapat dua buah record dengan kunci yang berbeda namun memiliki home address yang sama, dan terjadi tabrakan (collision). Tabrakan dapat diminimalisir dengan melakukan penggantian pada fungsi Hash yang digunakan, atau mengurangi packing factor.
a. Packing Factor
Packing factor, bisa disebut juga dengan packing density ataupun load factor adalah perbandingan antara jumlah data yang tersimpan terhadap jumlah slot address yang tersedia. Location Storage of Number Total Stored cord of Number Factor. Penggantian fungsi Hash dan pengurangan packing factor hanya meminimasisasi tabrakan, tetap dibutuhkan collision resolution.
b. Collision Resolution
Pada hashing untuk penempatan data, output dari fungsi Hash tidak selalu unik, namun hanya berupa kemungkinan suaru alamat yang dapat ditempati. Jika suatu home address sudah ditempati oleh record lain, maka harus dicarikan alamat lain. Proses pencarian Packing Re = alamat lain inilah yang disebut sebagai prosedur collision resolution.
1. Metode Collision Resolution
a. Open addressing
Metode dengan pencarian alamat alternative di alamat-alamat selanjutnya yang masih kosong.
Cara :
• Linear probing Pencarian dilakukan dengan jarak pencarian tetap
• Quardratic probing Pencarian dilakukan dengan jarak pencarian berubah dengan perubahan tetap.
• Double hashing
Pencarian dilakukan menggunakan dua fungsi Hash, yaitu fungsi H1 untuk menentukan home address dan fungsi H2 untuk menentukan increment jika terjadi tabrakan. Syarat metode ini adalah ukuran table merupakan bilangan prima sehingga kemungkinan terjadinya siklus pencarian pada slot yang sama dapat dihindari.
Algoritma : Tentukan home address dari key dengan fungsi H1.
IF home address kosong THEN
Sisip record pada home address.
ELSE
Hitung increment dengan fungsi H2 misalnya H2 (key) = x
Temukan slot kosong dengan cara increment sejauh x dari home address.
IF slot kosong ditemukan THEN
Sisip record pada slot kosong.
ELSE
Tabel telah penuh.
b. Computed chaining
Menggunakan “pseudolink” untuk menemukan next address jika terjadi collision. Tidak menyimpan actual address pada pseudolink, tapi address ditemukan dengan menghitung apa yang tersimpan pada pseudolink. Kinerja pseudolink lebih baik dibandingkan non-link karena menghilangkan penebakan lokasi (address).
Algoritma : Temukan home address dari key.
IF home address kosong THEN
Sisip record baru ke home address.
ELSE
Set 3 prioritas increment untuk mencari new address :
1 : Tentukan increment (new key).
2 : Tentukan increment (key pada current address).
3 : Penjumlahan hasil prioritas 1 dan 2.
WHILE new address belum kosong dan tabel belum penuh DO
Cek posisi mulai dari home address untuk ke – 3 prioritas untuk mencari new address yang kosong.
IF new address belum kosong THEN
Set ke – 3 nilai prioritas dengan kelipatannya.
END
WHILE
IF tabel penuh THEN
Proses sisip tidak dilakukan, keluarkan pesan “Tabel Penuh”.
ELSE
Sisip record baru pada new address.
Set field pseudolink pada home address dengan kode urut prioritas yang digunakan.
c. Coalesced hashing
Algoritma : Tentukan home address dari key.
IF home address kosong THEN
Sisip record pada home address.
ELSE
Temukan record terakhir dari data yang telah menempati home address, dengan mengikuti link. Temukan slot kosong mulai dari yang terletak pada address paling bawah.
IF slot kosong tidak ditemukan THEN
File telah penuh.
ELSE
Sisip record pada slot kosong.
Set link field dari record terakhir yang ber-home address sama ke alamat dari record yang baru disisip.
d. Chained progressive overflow
Algoritma : Tentukan home address dari key.
IF home address kosong THEN
Sisip record pada home address.
ELSE
Temukan slot kosong yang terletak setelah home address.
IF slot kosong ditemukan
THEN
Sisip record pada slot kosong.
ELSE
Tabel telah penuh.
e. Binary tree
Metode yang menggunakan struktur binary tree untuk pencarian address ketika erjadi tabrakan dengan memberikan dua pilihan langkah :
•Continue : melanjutkan pencarian address berikutnya yang mungkin ditempati oleh record yang akan disisipkan.
•Move : memindahkan record yang menempati address ke address berikutnya yang memungkinkan untuk ditempati record lama.
Algoritma : Tentukan home address dari key yang akan di-sisipkan (new key).
IF home address kosong THEN
Sisip record pada home address.
ELSE
WHILE new address tidak kosong dan tabel belum penuh DO Generate binary tree untuk mendapatkan new address :
4. Fungsi Hashed Satu Arah
Fungsi Hashed satu arah adalah fungsi Hash yang bekerja dalam satu arah. Maksud dari satu arah disini adalah bahwa pesan yang sudah diubah menjadi message digest tidak dapat dikembalikan lagi menjadi pesan semula (irreversible).
Sifat-sifat fungsi Hash satu-arah adalah sebagai berikut:
1. Fungsi H dapat diterapkan pada blok data berukuran berapa saja.
2. H menghasilkan nilai (h) dengan panjang tetap (fixed-length output).
3. H(x) mudah dihitung untuk setiap nilai x yang diberikan.
4. Untuk setiap h yang dihasilkan, tidak mungkin dikembalikan nilai x sedemikian sehingga H(x) =h. Itulah sebabnya fungsi H dikatakan fungsi Hash satu-arah (one-way Hash function).
5. Untuk setiap x yang diberikan, tidak mungkin mencari y ≠ x sedemikian sehingga H(y) = H(x).
6. Tidak mungkin mencari pasangan x dan y sedemikian sehingga H(x) = H(y).
Beberapa fungsi Hash satu-arah yang sudah dibuat, antara lain:
– MD2, MD4, MD5,
– Secure Hash Function (SHA),
– Snefru,
– N-Hash,
– RIPE-MD
KESIMPULAN
Terdapat enam organisasi dasar, kebanyakan organisasi file system termasuk salah satu atau kombinasi kategori-kategori ini. Enam organisasi pengaksesan file secara dasar adalah sebagai berikut :
1. File pile (pile file)
Pembahasan struktur file diketahui bahwa struktur dasar paling dasar sebuah file adalah pile dan file sekuensial. File pile atau file tumpukan merupakan struktur paling sederhana. Struktur ini jarang digunakan secara praktis tapi merupakan basis evaluasi struktur-struktur lain.
3. File sekuen berindeks (indexed-sequenstial file)
Index Sequential File merupakan perpaduan terbaik dari teknik sequential dan random file. Teknik penyimpanan yang dilakukan, menggunakan suatu index yang isinya berupa bagian dari data yang sudah tersortir. Index ini diakhiri denga adanya suatu pointer (penunjuk) yang bisa menunjukkan secara jelas posisi data yang selengkapnya. Index yang ada juga merupakan record-key (kunci record), sehingga kalau record key ini dipanggil, maka seluruh data juga akan ikut terpanggil.
5. File ber-hash (hashed file)
Metode penempatan dan pencarian yang memanfaatkan metode Hash disebut hashing atau ‘Hash addressing’ dan fungsi yang digunakan disebut fungsi hashing / fungsi Hash. Fungsi hashing atau fungsi Hash inilah yang dapat menjadi salah satu alternatif dalam menyimpan atau mengorganisasi File dengan metode akses langsung
Post a Comment