BAB II
PEMBAHASAN
A. Organisasi Berkas Relatif
1. Pengertian Berkas Relatif
Berkas relatif yaitu suatu
cara yang efektif dalam mengorganisasi sekumpulan record yang membutuhkan akses
sebuah record dengan cepat. Dalam berkas relatif ada hubungan antara key yang
dipakai untuk mengidentifikasi record dengan lokasi record dalam penyimpanan
sekunder.
2. Proses Berkas Relatif
Pada waktu sebuah record ditulis kedalam berkas relatif, fungsi pemetaan R digunakan untuk meterjemahkan NILAI KEY dari record menjadi ADDRESS, dimana record tersebut disimpan. Berkas relatif disimpan dalam media DASD(Direct Access Storage Device) seperti magnetic disk.A. Teknik Dasar Fungsi Pemetaaan R
Ada 3 teknik dasar yang digunakan untuk menyatakan fungsi
pemetaan R, dimana R(NILAI KEY
ADDRESS, yaitu :
1. Teknik Pemetaan Langsung (Direct Mapping)
Ada 2 cara dalam pemetaan langsung,
yaitu :
Ø Pengalamatan Mutlak
R(NILAI KEY ADDRESS
NILAI
KEY = ALAMAT MUTLAK
Pengalamatan
mutlak ini memiliki kelebihan dan kekurangannya.
Ø Pengalamatan Relatif
R(NILAI KEY
ADDRESS
NILAI
KEY = ALAMAT MUTLAK
Pengalamatan
relatif ini memiliki kelebihan dan kekurangannya.
2. Teknik Pencarian Tabel (Directory Look Up)
3. Teknik Kalkulasi (Calculation)
Keadaan
dimana :
R(K1)
= R(K2) Disebut benturan atau Collision.
Ada
6 cara untuk mengatasi benturan antara
lain :
- Scatter Strage Techniques
- Randomizing Technigques
- Key-to-address transformation methods
- Direc addressing Techniques
- Hash Table Methods
- Hashing.
B. Hashing
Teknik yang fungsinya untuk menentukan
lokais record pada file data dengan melakukan perhitungan pada nilai key dari
record tersebut.
Ada 5 fungsi hashing yang umum digunakan yaitu :
1. Sisa Pembagian (Division-Remainder)
Dalam teknik ini membagi nilai key dengan ukuran tabel. Alamat
tempat penyimpanan record didapat dari sisa pembagian + 1.
Contoh :
Asumsikan
ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai key sebagai
berikut : 12,21,68,38,52,70,44,18.
Maka :
(12 mod 11) + 1 = 1 + 1 = 2; simpan 12 di lokasi 2
(21 mod 11 ) + 1 = 10 + 1 = 11; simpan 21 d lokasi 11
(68 mod 11) + 1 = 2 + 1 = 3; simpan 68 di lokasi 3
(38 mod 11) + 1 = 5 + 1 = 6; simpan 38 di lokasi 6
(52 mod 11) + 1 = 9 + 1 = 10; simpan 52 di lokasi 10
(70 mod 11) + 1 = 4 + 1 = 5; simpan 70 di lokasi 5
(44 mod 11) + 1 = 0 + 1 = 1; simpan 44 di lokasi 1
(18 mod 11) + 1 = 7 + 1 = 8; simpan 18 di lokasi 8
Sehingga :
Alamat 1 2 3 4 5 6 7 8 9 10 11
Nilai kunci 44 12 68 – 70 38 – 18 – 52 21
2. Pemenggalan (Truncation)
Hasil
dari pemenggalan merupakan alamat relatif dimana kunci
Contoh 1 :
Jika nilai kunci menghapus 6 digit terakhir dari 9 digit
nomor sebagai berikut:
(123456789) = 123; simpan 123456789 di lokasi 123
(222345654) = 222; simpan 222345654 di lokasi 222
(301657434) = 301; simpan 301657434 di lokasi 301
(123882345) = 123; simpan 123882345 d ilokasi 123
Pemenggalan di atas mengakibatkan terjadinya tubrukan
(kolisi) pada lokasi penyimpanan, maka pemenggalan dilakukan dengan melihat
nomor kunci yang diberikan supaya tidak terjadinya kolisi.
Maka dilakukan pemenggalan menghapus 6 digit awal nomor kunci,
sehingga :
(123456789) = 789; simpan 123456789 di lokasi 789
(222345654) = 654; simpan 222345654 di lokasi 654
(301657434) = 434; simpan 301657434 di lokasi 434
(123882345) = 345; simpan 123882345 di lokasi 345
3. Lipatan (Folding)
Dalam teknik ini nilai key dibagi (dilipat) menjadi beberapa
bagian. Masing-masing bagian memiliki jumlah digit yang sama, dimana nilai
kunci pada bagian terakhir di balik dari sebelah kanan. Lokasi penyimpanan
merupakan hasil dari penjumlahan.
Contoh :
Diberikan
nilai kunci 123456, 234351, 222456. Nilai kunci dibagi menjadi 2 bagian setiap
3 digit. Bagian terakhir nilai kuncinya dibalik dari sebelah kanan.
Maka
:
123
+ 654 = 777; simpan 123456 dilokasi 777
234
+ 153 = 387; simpan 234351 dilokasi 387
222
+ 654 = 876; simpan 222456 dilokasi 876
4. Perkalian (Multiplication)
Teknik ini dilakukan dengan cara membagi-bagi satu kunci dan
bagian dari salah satu kunci bisa dipilih untuk kemudian dikalikan. Hasilnya merupakan
alamat relatif dari record yang akan dilokasikan dimana kunci tersebut akan
disimpan.
Contoh
:
Nomor identitas pegawai digunakan sebagai kunci.
Kalikan 3 digit yang pertama dengan 3 digit yang terakhir
dari kunci.
Diberikan nomor identitas pegawai = 123456789
3 digit yang pertama = 123
3 digit yang terakhir = 789
(123456789)= 123 * 789 = 97047
Penggal hasil perkalian pada digit yang terakhir sehingga
menjadi 9704, jadi nomor identitas pegawai 123456789 disimpan dilokasi 9704.
5. Pengkuadratan (Mid-Square)
Dalam teknik ini nilai kuncinya dikuadratkan, kemudian
menentukan digit yang akan dikutip dari tengah, hasilnya merupakan alamat
relatif. Jika alamat relatif yang dinginkan sejumlah n digit, maka digit dipenggal atau dihilangkan diantara kedua ujung
hasil pengkuadratan nilai kunci, menyisakan n digit dari tengah.
Contoh :
Pada
contoh dibawah ini, digit ke-7 samapi 10 (dihitung dari kanan), diambil untuk
mendapatkan 4 digit sebagai alamat relatif.
Nilai kunci Nilai
kunci dikuadratkan Alamat
relatif
123456789 15241578750190521 8750
123456790 15241578997104100 8997
345237459 119188903096777000 3096
987654321 975461055789911041 5789
