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 (sequential file)
3. File sekuen berindeks (indexed-sequenstial file)
4. File berindek majemuk (multiple-indexed file)
5. File ber-hash (hashed file)
6. File cincin (multiring 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. 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. Sequential file adalah record yang disimpan dalam media penyimpanan
sekunder komputer, yang dapat diakses secara berurutan mulai dari record
pertama sampai dengan record terakhir. Record per record searah. 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 merupakan suatu cara ataupun suatu metode penyimpanan
dan pembacaan data yang dilakukan 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 berikutnya sehingga data yang dimaksud
bisa diketemukan.
Keuntungan dari Sequential file
Keuntungan utama dari organisasi Sequential file adalah:
1. Mengarsipkan desain adalah sederhana.
2. Lokasi dari rekaman memerlukan hanyalah kunci rekaman.
3. Ketika laju ke aktifan adalah tinggi,kesederhanaan dari mengakses cara
membuat proses efisien.
4. Media file murah seperti pita magnet dapat dipergunakan untuk menyimpan
data.
Kelemahan dari Sequential file
Kelemahan utama dari organisasi Sequential file adalah:
1.Memperbaharui memerlukan bahwa semua transaksi rekaman diurutkan pada urutan
kunci rekaman.
2.Satu berkas menguasai baru,secara fisik pisahkan dan eksklusif, selalu
diciptakan sebagai hasil pembaharuan percontohan.
3.Tambahan dan penghapusan dari rekaman tidak sederhana.
PENGOLAHAN SEQUENTIAL FILE
File merupakan fasilitas penyimpanan data pada external storage yang bersifat
permanen, jika 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 :
1. SEQUENTIAL FILE
2. RANDOM FILE
3. BINARY FILE
Pada Sequential file (file urut) 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, 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 :
1. Tahap membuka file (OPEN)
2. Tahap memproses (INPUT/OUTPUT)
3. Dan yang terakhir adalah tahap menutup file (CLOSE)
Membuka File SEQUENTIAL
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.
Proses INPUT/OUTPUT
Perintah proses INPUT/OUTPUT pada sequential file sangat tergantung kepada
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 :
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
Catatan :
Anda dapat menggunakan fungsi bantu EOF(filenumber) untuk memeriksa apakah
berada diposisi akhir file.
Proses CLOSE
Untuk menutup file dapat digunakan perintah CLOSE.
Syntax
CLOSE #filenumber
Contoh:
CLOSE #1
menutup file nomor 1.
C. 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.
D. MULTIPLE INDEX FILE
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 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. Contoh :
Indeks Dinamis adalah Indeks B-tree.
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
Algoritma Penyisipan Btree
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
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
F. MULTIRING FILE
I. Pengertian Multiring File
Multiring File merupakan metode pengorganisasian file yang berorientasi pada
pemrosesan subset dari record secara efisien. Subset tersebut digambarkan
sebagai grup dari beberapa record yang terdiri dari nilai atribut yang biasa.
Contohnya “Semua pekerja yang berbicara bahasa Perancis”.
Subset dari record dihubungkan bersama secara eksplisit menggunakan pointer.
Rantai penghubung ini menentukan urutan anggota dari subset. Setiap subset
mempunyai record kepala yang merupakan record awal dari suatu rantai. Sebuah
record kepala berisi informasi yang berhubungan dengan seluruh record anggota
di bawahnya. Record-record kepala ini juga dapat dihubungkan menjadi sebuah
rantai.
Tipe rantai tertentu yang digunakan untuk menggambarkan hal ini dinamakan ring,
yang merupakan rantai di mana pointer anggota terakhir digunakan untuk menunkuk
record kepala dari rantai. Ring-ring dapat disarangkan dalam banyak level
kedalaman. Dalam hal ini record anggota dari ring level ke-i record kepala ring
bawahan pada level i-1. Ring level terbawah, yang berisi data terakhir, selalu
dianggap berada pada level 1.
Pencarian dalam Multiring File adalah dengan menelusuri rantai sampai atribut
nilai yang dicari ditemukan. Kemudian rantai baru dimasuki untuk menemukan
atribut recod bawahan. Proses ini diulang terus sampai record yang diinginkan
ditemukan.
II. Interlinked Rings
Untuk pertanyaan (query) yang lebih spesifik, yaitu pertanyaan anggota rantai
bawahan seperti “Daftar semua tukang patri di suatu perusahaan”, dara
sebelumnya kurang efisien karena memerlukan pencarian yang melelahkan. Untuk
keperluan ini digunakan struktur ring sebagai berikut.
Panah Bachman digunakan untuk menunjukkan bahwa pada kotak yang ditunjuk
memiliki banyak record.
Bila kita ekspansikan contoh di atas dengan memisahkan pekerja dalam berbagai
lokasi ke dalam departemen-departemen yang lebih spesifik, memungkinkan akses
dengan urutan senioritas, dan tambahkan warehouse pada setiap lokasi dan
biarkan informasi stock tersedia. Struktur diagramnya tampak sebagai berikut.
Hubungan di antara ring-ring tidak harus hirarkis. Hubungan dapat
diimplementasi dengan merelasikan anggota dalam ring-ring yang sama, yang
menyediakan banyak lintasan di antara record-record, atau menghubungkan
ring-ring pada level yang lebih rendah kembali ke ring-ring dengan level lebih
tinggi.
Efektivitas dari sebuah proses dalam melokasikan sebuah record sangat
bergantung pada kecocokan pasangan atribut yang membentuk argument pertanyaan
dengan struktur dari file. Bila file tidak diorganisasikan secara benar, maka
proses tidak dapat berjalan secara efisien, dan dibutuhkan intervensi dari
pengguna.
III. Struktur dari Multiring File
Semua record mempunyai struktur yang sama dalam Multiring File, tetapi isi dan
ukuran merupakan fungsi dari ring-ring di mana mereka berada. Sebuah Multiring
File dapat mempunyai sejumlah kategori record yang berbeda. Di sini definisi
file telah menyimpang dari definisi awal. Di sini record-record tidak sama
formatnya, dan keanggotaan ring serta keanggotaan file harus diketahui sebelum
pemrosesan.
Format record yang sebenarnya bergantung pada kombinasi dari tipe-tipe ring di
mana record tersebut menjadi anggota. Pasangan nilai atrinbut mengidentifikasi
dirinya seperti pada pile. Tetapi biasanya tidak seperti itu, dan tiap record
akan mempunyai pengidentifikasi tipe record.
Pada contoh berikut, field t mengidentifikasi record ini sebagai record
pekerja. Tiap record dengan tipe t akan mempunyai field data yang sama dan 7
field pointer. Pengidentifikasi ini akan memungkinkan referensi ke sebuah
deskripsi format recod yang tepat, disimpan dengan deskripsi umum dari file.
Untuk menghubungkan record-record ke dalam ring-ring mereka, pointer-pointer
akan muncul dalam sebuah record yang umum. Sebuah record dapat dimiliki oleh
ring-ring sebanyak jumlah pointer yang dimilikinya.
Dapat juga terdapat field-field data NULL, tetapi karena terdapat bayak tipe
record dengan tujuan spesifik, file secara keseluruhan relative padat.
Setiap ring pasti memiliki kepala. Kepala ini dapat berupa poin masukan,
anggota dari ring lain, atau keduanya. Ketika sebuah ring dimasuki dalam sebuah
pencarian, poin masukan dicatat sehingga ring ini tidak dimasuki 2 kali.
IV. Manipulasi Ring
Umumnya organisasi Multiring File menghindari penggandaan data dengan
menempatkan data biasa kepada semua anggota ring ke dalam record kepala dari
ring. Efek negatifnya adalah dalam desain dasar ring, ketika sebuah record
diambil berdasarkan kombinasi kata kunci pencarian, hasilnya yang dapat
diaplikasikan dengan record tidak selalu dapat dilakukan dengan hanya atribut
yang disimpan dalam anggota atau record kepala yang diakses selama pencarian
sepanjang 1 lintasan. 2 alternatif yang digunakan, yaitu:
Pencarian Paralel melalui semua ring yang diidentifikasi dalam kata kunci
pencarian dapat dilakukan, dengan menghilangkan pada record-record pada
persimpangan ring-ring tersebut.
Pencarian Inisial dapat dilakukan berdasarkan atribut dengan efektivitas
mempartisi terbaik. Record-record yang dikumpulkan kemudian dicek untuk
ketepatan dengan menempatkan record kepala untuk tipe atribut lain yang
diperlukan dan menolak record dengan nilai data yang tidak tepat.
Proses yang kedua di atas diaplikasikan dengan langkah-langkah sebagai berikut.
Query:
Find an Employee with Location =”Thule” and Profession=”Welder”.
Enter Location chain;
For each member record determine if key = Thule;
When found followEmplo yee chain;
For every Employee record the profession must be determined
Follow the profession chain;
When its header record is reached,
then inspect profession header for key = Welder
If the field matches the search key
then Employee member record becomes output;
Continue with the next Employee record;
When its header record, the Location = Thule is reached,
then the result is complete.
V. Keputusan Desain Ring File
Lama penelusuran rantai berbanding lurus dengan ukuran rantai. Ukuran
rantai-rantai individu dapat dikurangi dengan menambah jumlah rantai-rantai dan
jumlah level dalam struktur file.
Hal ini digambarkan dengan rumus sebagai berikut.
y = x√n dengan x = level
y = panjang rantai
n = record count
Waktu pencarian untuk record dengan level terendah
berkurang secara proporsional sampai akar ke-x dari record count, n, dan
bertambah secara proporsional sampai level x. Sebuah atribut yang tidak
mempartisi file ke dalam banyak level tidak sangat berguna seperti elemen ring.
Peng-Cluster-an Ring
Record yang sering diakses bersama paling baik disimpan dengan derajat
lokalitas yang tinggi. Satu ring umumnya dapat diletakkan seluruhnya dalam 1
silinder, seingga semua pencarian dihindari saat penelusuran cluster ring ini.
Ketika referensi berulang-ulang kepada record kepala ring dibutuhkan, kepala
record itu dapat berpartisipasi dalam cluster. Ring berikutnya dengan level
lebih tinggi akan sulit untuk berpartisipasi, kecuali jika ruangan total yang
dibutuhkan semua anggota record dan pendahulunya cukup kecil untuk disimpan
dalam satu atau beberapa silinder. Dalam perubahan database yang dinamis, peng-cluster-an
yang optimal sulit untu dijaga dan keuntungannya sedikit. Sebuah reorganisasi
diperlukan untuk mengembalikan cluster-cluster.
Pengkategorian Atribut Real
Atribut yang merepresentasikan data real atau kontinyu tidak menyediakan
partisi yang efektif kecuali jika dikategorikan secara artificial.
VI. Penggunaan Multiring File
Struktur Multiring merupakan dasar untuk beberapa database terbesar yang
digunakan saat ini. Sistem informasi manajemen di mana banyak melibatkan
tabulasi, penjumlahan, dan laporan pengecualian telah diimplementasikan
menggunakan daftar Multiring ini.
Beberapa masalah dalam representasi ruang geografis dan arsitektur juga telah
diselesaikan dengan pendekatan Multiring. Perkembangan saat ini dalam system
multifile terintegrasi bergantung pada kapabilitas yang disediakan oleh
struktur ring. Masalahnya adalah desain yang cermat berdasarkan pengetahuan
tentang data dan pola penggunaan diperlukan sebelum Multiring File dapat
diimplementasikan.
VII. Kinerja Multiring
Kinerja system Multiring sangat bergantung pada kecocokan dari penandaan
atribut ke ring-ring tertentu.
Ukuran record dalam Multiring File
Karena banyak tipe record yang berbeda dalam Multiring File, estimasi akurat
didapatkan hanya dengan mendaftar semua tipe, dengan frekuensi dan ukuran
masing-masing.
Pengambilan record dalam Multiring File
Waktu untuk mengambil sebuah record adalah fungsi dari jumlah dan panjang
rantai yang dicari. Panjang daripada ring bergantung pada ukuran file, jumlah
level, dan seberapa baik file dipartisi ke dalam ring-ring.
Pengambilan record berikutnya dari Multiring File
Record berikutnya untuk urutan yang berhubungan dapat ditemukan dengan
menelusuri rantai tersebut.
Pemasukan ke dalam Multiring File
Penambahan record ke dalam Multiring File dilakukan dengan menentukan spasi
kosong yang cocok untuk record, menempatkan semua pendahulu untuk record baru,
mengambil nilai dari link yang tepat dari pendahulu, menetapkannya ke dalam
record baru, dan menempatkan nilai dari posisi record baru ke dalam area-area
link pendahulu.
Meng-Update record dalam Multiring File
Jika hanya field data yang akan dirubah, update hanya memerlukan penemuan
record dan penulisan ulang.
Membaca seluruh Multiring File
Pembacaan menurut rantai memerlukan bahwa sebuah record kepala diakses untuk
setiap ring tambahan. Baik record kepala baru maupun lama diperlukan untuk
bergerak di antara 2 ring.
Reorganisasi Mutiring File
Reorganisasi sebenarnya tidak diperukan sebagau bagian dari prosedur operasi
normal. Hanya saat pemformatan ulang tipe record diperlukan, record-record
seperti itu harus ditulis ulang, Ini hanya memerlukan reorganisasi parsial dari
file, karena perubahan terbatas pada ring-ring pada level-level yang
menggunakan tipe-tipe record itu.
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.
2. 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.
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.
4. 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.
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.
6. File cincin (multiring file)
Multiring File merupakan metode pengorganisasian file yang berorientasi pada
pemrosesan subset dari record secara efisien. Subset tersebut digambarkan
sebagai grup dari beberapa record yang terdiri dari nilai atribut yang biasa.
Contohnya “Semua pekerja yang berbicara bahasa Perancis”
