>Klik DISINI< untuk mengunduh Artikel ini (Format Word).
Pesatnya perkembangan dan kemajuan Teknologi Informasi (TI) saat ini yang selalu di tuntut untuk dapat memenuhi kebutuhan manusia, salah satunya akses mendapatkan informasi dengan efisien. Informasi ini diakses serta diproses menggunakan komputer. Komputer saat ini adalah alat yang amat penting dalam kebutuhan mengakses informasi, yang juga sebagai akar dalam dunia TI. Pada suatu komputer, informasi yang diakses diimplememtasikan pada data yang tersusun dengan aturan tersendiri dalam bentuk file. Banyak metode dalam menyusun atau mengorganisasikan file. Metode tersebut diantaranya metode Sequential File, Indexed-Sequential File, Indexed File, Direct File, dan Multiring File.Elemen penting pada perancangan sistem akses adalah bagaimana cara record-record di organisasikan atau di strukturkan. Kriteria umum untuk pemilihan suatu organisasi file yaitu :
a. Redundansi yang kecil
b. Pengaksesan yang cepat
c. kemudahan dalam memperbarui
d. pemeliharaan yang sederhana
e. keandalan yang tinggi.
Ada 6 organisasi dasar, kebanyakan organisasi file system adalah salah satu atau kombinasi dari kategori-kategori di bawah ini. Enam organisasi pengaksesan file dasar adalah seperti dibawah ini :
a. File pile (pile file)
b. File sekuen (sequential file)
c. File sekuen berindeks (indexed-sequenstial file)
d. File berindek majemuk (multiple-indexed file)
e. File ber-hash (hashed file)
f. File multiring (multiring file)
Enam organisasi dasar ini dirinci pada buku A Gio Wiederhold [WIE-87]. Disini saya akan menjelaskan dari ke enam jenis organisasi pengaksesan dasar diatas, tapi disini saya hanya akan mejelaskan 3 poin saja yaitu b,d,e untuk melihat penjelasan a,c,f bisa klik disini pada postingan teman saya.
A. SEQUENTIAL FILE
Squential file adalah file dengan organisasi urut. Data yang disimpan diurutkan sesuai dengan urutan pemasukan data (urut sesuai nomor record). Data yang ditambahkan selalu memnempati urutan berikutnya. Sequential file yaitu record yang disimpan pada media penyimpanan sekunder komputer, yang dapat diakses secara berurutan mulai dari record pertama sampai dengan recordterakhir. Record per record satu arah. Record terakhir adalah rekaman fiktif yang menandai akhir dari arsip. Sequential adalah sekumpulan record yang disimpan dalam media penyimpanan sekunder computer, yang dapat diakses secara berurutan mulai dari record pertama sampai record terakhir.
Sequential file ini adalah suatu metode penyimpanan dan pembacaan data yang dikerjakan secara berurutan. Dalam hal ini, data yang ada akan disimpan sesuai dengan urutan masuknya. Data pertama dengan nomor berapapun, akan disimpan ditempat pertama, demikian pula
dengan data berikutnya yang juga akan disimpan ditempat berikutnya. Dalam melakukan pembacaan data, juga akan dilakukan secara berurutan, artinya, pembacaan akan dimulai dari data paling awal dan dilanjutkan dengan data selanjutnya sehingga, data yang dimaksud bisa diketemukan.
1. Kelebihan dari Sequential file
Kelebihan utam dari organisasi Sequential file ini adalah:
a. Mengarsipkan desain yang sederhana.
b. Lokasi dari rekaman yang diperlukan hanyalah kunci rekaman.
c. Ketika laju ke aktifan sedang tinggi,kesederhanaan dari mengakses cara membuat sehingga proses efisien.
d. Media file murah seperti pita magnet dapat dipergunakan untuk menyimpan data.
2. Kelemahan dari Sequential file
Kelemahan utama dari organisasi Sequential file adalah:
a. Dalam memperbaharui data memerlukan semua transaksi rekaman yang diurutkan pada urutan kunci rekaman.
b. Satu berkas menguasai baru,secara fisik pisahkan dan eksklusif, selalu diciptakan sebagai hasil pembaharuan percontohan.
c. Penambahan dan penghapusan dari rekaman tidak sederhana.
3. Pengolahan Squential File
File adalah fasilitas untuk menyimpan data pada external storage yang bersifat permanen, apabila dibandingkan dengan penyimpanan ke RAM yang sifatnya sementara. Dengan pemakaian file kita dapat menghemat pemakaian RAM komputer yang memiliki jumlah yang terbatas serta dapat melakukan dokumentasi untuk jangka waktu yang panjang.
Pada QBasic pengolahan file dapat dibagi atas tiga jenis,
yaitu :
- Squential File
- Random File
- Binary File
Dalam Sequential file proses pengolahannya dilakukan secara linier dari awal sampai akhir, tanpa bisa kembali kebagian sebelumnya, kecuali proses dimulai lagi dari awal. Jadi dalam pengolahan datanya bersifat first in first out, yang artinya pembacaan data dari file ini harus dimulai dari data yang paling awal.
Pada umumnya pengolahan data yang menggunakan file sebagai media INPUT maupun OUTPUT memiliki tiga tahap,
yaitu :
- Tahap membuka file (OPEN)
- Tahap memproses (INPUT/OUTPUT)
- Dan yang terakhir adalah tahap menutup file (CLOSE)
a. Membuka file squential
Untuk membuka file sequential yang akan diproses dapat digunakan penulisan sebagai berikut :
Syntax :
Open filename [FOR mode] AS [#]filenum
dimana mode terdiri dari :
INPUT, membuka file untuk proses INPUT
OUTPUT, membuka file baru untuk proses OUTPUT
APPEND, membuka file untuk untuk proses OUTPUT dimana data baru ditambahkan pada bagian akhir.
Contoh :
Open “Siswa.Dat” For Append AS #1
Akan membuka Siswa.Dat sebagai OUPUT dimana data baru ditambahkan pada bagian akhir. Jika file Siswa.Dat belum ada, maka akan dibuat yang baru.
b. Proses Input/Output
Perintah proses INPUT/OUTPUT pada sequential file tergantung sekali pada bentuk perlakuan terhadap data. Untuk penulisan yang berorientasi pada baris, anda dapat menggunakan perintah PRINT, dan pembacaanya dapat menggunakan LINEINPUT. Penulisan yang berorientasi kepada data, anda dapat menggunakan perintah WRITE dan INPUT untuk proses pembacaannya.
Syntax :Catatan :
PRINT #filenumber,[USING stringexpressin;]expression list
WRITE #filenumber[,expressionlist]
INPUT #filenumber, variablelist
LINEINPUT #filenumber, variable-string
Contoh :
Write #1, “920403024?,”Hendra”,80,90
menulis ke file nomor 1, dan data dapat dibaca kembali dengan perintah :
Input #1,Nim$,Nama$,Teori,Praktek
Anda dapat menggunakan fungsi bantu EOF(filenumber) untuk memeriksa apakah berada diposisi akhir file.
c. Proses Close
Untuk menutup file dapat digunakan perintah CLOSE.
Syntax
CLOSE #filenumber
Contoh:
CLOSE #1
menutup file nomor 1.
B. MULTIPLE INDEX FILE
Multiple Index File atau sering disebut File berindex majemuk adalah organisasi pengaksesan file yang memiliki ciri seperti dibawah ini :
-Terdiri dari main file dan file-file index (file berindex majemuk).
-Tidak ada rantai overflow.
-Tidak dikenal konsep atribut kunci (tidak ada keterurutan berdasarkan atribut kunci).
-Pengubahan data langsung dilakukan terhadap main file.
-Format record dapat berupa name-value pair atau dapat berupa structured record.
-Index bersifat multiple index, dinamis, record anchored.
-Entri index terdiri dari atribut dan TID.
-Entri index terurut berdasarkan nilai atributnya.
-Next record diakses berdasarkan keterurutan entri pada index-nya.
-Tiap index dapat bersifat multilevel.
-TID pada index berisi alamat block dan posisi record.
-Exhaustive vs partial index.
Pada organisasi ini, pembaharuan dilakukan terhadap file utama bukan file overflow, ini karena record dicari lewat indeks, sehingga indeks harus dinamis. Begitu terjadi pembaharuan ( insert, update, delete) mka indeks-indeks diperbaharui mengikuti perubahan di file utama.
Contoh :
Indeks Dinamis adalah Indeks B-tree.Algoritma Penyisipan Btree
-B-Tree
BTree = Balanced Tree
Perubahan pada main file berimplikasi terhadap index-nya.
Struktur index menggunakan BTree.
Blok – blok BTree harus dijaga agar memuat setengah dari fan out ratio-nya (effective fan out antara y/2 – y).
Order Capacity = d
Kapasitas minimum = d, dan maximum = 2d
Khusus untuk root, kapasitas minimum = 1
Cari posisi yang sesuai bagi record baru, mulai dari root BTree.
Jika tersedia space, sisipkan record baru sesuai urutan, jika tidak terjadi, overflow.
Jika terjadi overflow :
1. Split menjadi 2 node
2. Pilih node tengah untuk naik ke level berikutnya
3. Set pointer dari parent node ke child node
Algoritma Penghapusan Btree
Menghapus node pada leaf dan tidak melanggar kapasitas minimum, maka record langsung dihapus tanpa mengubah struktur BTree.
Menghapus node pada root dan tidak melanggar kapasitas minimum, maka ganti dengan 1 record dari leaf node kanan terkecil.
Menghapus node (leaf dan root), dan melanggar kapasitas minimum, maka perbaiki dengan redistribusi record. Apabila redistribusi record mengakibatkan pelanggaran kapasitas minimum pada node lain, maka lakukan coalescing node.
Contoh :
BTree dengan order capacity d = 2
C. HASHED FILE
Hashed File adalah 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.
Pada konsepnya modern ini, selain digunakan pada penyimpanan data, fungsi Hash yaitu sebuah fungsi matematika, yang menerima masukan string yang panjangnya sembarang, mengambil sebuah
panjang variable dari string masukan tersebut, 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 disi
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 THEN4. Fungsi Hashed Satu Arah
Sisip record pada home address.
ELSE
WHILE new address tidak kosong dan tabel belum penuh DO
Generate binary tree untuk mendapatkan new address :
Fungsi Hashed satu arah yaitu fungsi Hash yang bekerja dalam satu arah. Maksud dari satu arah disini yaitu 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
Dari uraian yang super panjang lebar diatas bisa disimpulkan bahwa :
A. File sekuen (sequential file)
Sequential File adalah file dengan organisasi urut. Data yang disimpan diurutkan berdasarkan urutan pemasukan data (urut berdasarkan nomor record). Data yang ditambahkan selalu menempati urutan berikutnya.
B. File berindek majemuk (multiple-indexed file)
Pada Multiple Index File (file berindex majemuk), pembaharuan dilakukan terhadap file utama bukan file overflow, karena record dicari lewat indeks, maka indeks harus dinamis. Begitu terjadi pembaharuan ( insert, update, delete) mka indeks-indeks diperbaharui mengikuti perubahan di file utama.
C. 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.
Sekian postingan tentang organisasi file atau metode pengaksesan dasar file, untuk melihat postingan 3 poin organisasi lainya (poin a,c,f) Bisa klik disini. Terima kasih semoga bermanfaat.
Oleh: Slamet//17130004
Post a Comment