Kamis, 10 Oktober 2013
Rabu, 09 Oktober 2013
Organisasi File
15.51
No comments
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)
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”
Minggu, 06 Oktober 2013
Ilustrasi Sejarah OS
05.58
2 comments
SISTEM OPERASI adalah :
“ Sekumpulan program kontrol atau alat pengendali yang secara terpadu bertindak sebagai penghubung antara komputer dengan pemakainya”.
SISTEM OPERASI adalah :
“ Sebagai program pengendali, yaitu program yang digunakan untuk mengontrol program yang lain”
“ Sekumpulan program kontrol atau alat pengendali yang secara terpadu bertindak sebagai penghubung antara komputer dengan pemakainya”.
SISTEM OPERASI adalah :
“ Sebagai program pengendali, yaitu program yang digunakan untuk mengontrol program yang lain”
Langganan:
Postingan (Atom)