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”