} Dalam mengorganisasikan sekumpulan record dibutuhkan akses kesebuah record dengan cepat.
} Hubungan ini dinyatakan sebagai R, yang merupakan fungsi pemetaan :
R(NILAI KEY) ADDRESS
Jika pada organisasi file sequential digambarkan sebagai sebuah kaset, maka organisasi file relatif digambarkan sebagai sebuah compac disk (CD). Kita bisa langsung memilih lagu mana yang akan kita dengarkan tanpa harus didahului (mendengarkan) lagu sebelumnya. Relatif dapat diartikan langsung.
Pengorganisasian relatif memungkinkan kita memproses record yang mana saja secara langsung tanpa harus melalui (membaca) record-record yang lainnya.
Proses Berkas Relatif
Proses Berkas Relatif
} Pada waktu sebuah record ditulis kedalam berkas relatif, fungsi pemetaan R digunakan untuk menerjemahkan NILAI KEY DARI RECORD menjadi ADDRESS, dimana record tersebut disimpan.
} Berkas relatif harus disimpan dalam media DASD, seperti magnetic disk atau drum.
(SASD, seperti magnetic tape atau pada DASD, seperti magnetic disk)
B. PENDEKATAN TERHADAP MASALAH COLLISION
Satu lokasi memori hanya dapat digunakan untuk menyimpan satu satuan data saja. Bila hasil perhitungan atas key field untuk menentukan alamat memori antara satu key field dengan key field lainnya sama, maka hanya satu yang akan ditempatkan di alamat hasil perhitungan itu, yang lainnya harus dicarikan alamat lainnya.
Empat pendekatan untuk mencarikan alamat lainnya itu, yaitu (1) open addressing, (2) addressing overflow/ separate overflow, (3) synonim chaining, dan (4) bucket addressing. Adapun teknik yang digunakan adalah (1) linear probing, dan (2) addressing overflow/ separate overflow.
Open Addressing ;
Menemukan address yang bukan home address untuk K2.
Separate Overflow ;
Menemukan address untuuk K2 di luar primary area yakni di overflow area.
Ada 2 teknik yang digunakan untuk mengatasi collision yaitu:
1. Liear Probing yang merupakan teknik open addressing Agar linear probing dapat dilaksanakan, harus ada penentu apakah address kosong. Ini dapat dilakukan dengan memberi panji (flag) bahwa lokasi tersebut telah penuh setelah record disimpan. Lokasi dasar penyimpanan dengan teknik linear probing dapat dilihat pada gambar berikut:
2. . Double Hasing
– Yang memakai fungsi hash kedua terhadap hasil dari fungsi hash pertama. Address dari record yang di-hash kembali dapat terletak di primary area atau di Separate Overflow Area
- Keuntungan dari metode Separate Overflow adalah menghindari keadan di mana dapat terjadi metode Open Addressing untuk sebuah record yang tidak dapat disimpan dalam home address-nya menggantikan record lain yang terakhir di hash oleh home address-nya.
C. SYNO CHAINING
Synomim chaining memberi tahu rangkaian alamat berikutnya dari record yang terjadi collision. Jadi, ada next pointer untuk menunjuk ke alamat lainnya yang pada perhitungan sebelumnya terjadi nilai yang sama. Dalam materi struktur data, hal ini dikenal dengan istllah linked list.
Jadi, komputer tidak perlu mencari alamat record yang terjadi collision karena sudah ada di penunjuknya (pointer).
• Pendekatan pemecahan collision yang mengakses synonim dengan fasilitas link list untuk record-recordnya dalam kelas ekivalen. Adapun link list record-record dengan home address yang sama tak akan mengurangi jumlah collision, tetapi akan mengurangi waktu akses untuk me-retrieve record-record yang tak ada di home addressnya.
Contoh :
KEY HOME ADDRESS ACTUAL ADDRESS
Adams 20 20
Bates 21 21
Coll 20 22
Dean 21 23
Evans 24 24
Flint 20 25
R20 R21 R22 R23 R24 R25
.. Adams .. Bates .. Coll .. Dean .. Evans .. Flint .. ...
gambar hashing dengan synonim chaining
HOME PRIMARY DATA OVERFLOW ADDRESS AREA
20 Adams .. 0 Coll ..
21 Bates .. 1 Dean ..
22 2 Flint ..
23 3
24 Evans ..
D. BUCKET ADDRESSING
Data yang terjadi collision diletakkan dalam satu blok (bucket), baik di primary area maupun di overflow areanya. Bila satu blok sudah penuh, maka akan ada penunjuk (pointer) untuk menunjuk blok berikutnya. Penempatan data di blok bisa diurut sesuai key fieldnya atau sesuai urutan datangnya data.
Contoh :
Sebuah berkas relatif mempunyai relatif address space dari 0 sampai M dan sebuah bucket berukuran B record , address space akan terdiri dari B(M+1) record. Jika file terdiri dari N record, maka :
Factor Muat = N
B(M + 1)
Record-record yang disimpan dalam sebuah bucket dapat dikelola dalam :
1. Dapat disisipkan dalam urutan berdasarkan penempatannya di bucket.
Dapat dipertahankan urutan nilai key-nya
Contoh :
KEY HOME ADDRESS
Green 30
Hall 30
Jenk 32
King 33
Land 33
Mark 33
Nutt 33
BUCKET BUCKET CONTENTS
ADDRES
30 Green.. Hall
31 Overflow
32 Jenks..
33 King.. Land.. Marks..
Tidak ada komentar:
Posting Komentar