Pengertian
· Suatu cara yang efektif dalam mengorganisasi sekumpulan record yang membutuhkan akses sebuah record dengan cepat.
· Record tidak perlu tersortir secara fisik menurut nilai key.
· Organisasi berkas relatif paling sering digunakan dalam proses interaktif.
· Tidak perlu mengakses record secara berurutan (consecutive).
· Sebaiknya disimpan dalam Direct Access Storage Device (DASD) seperti magnetic disk/drum.
· Hubungan ini dinyatakan sebagai R, yang merupakan fungsi pemetaan :
R(NILAI KEY) → ADDRESS
dari nilai key ke address dalam penyimpanan sekunder.
Kemampuan Berkas Relatif
· Kemampuan mengakses record secara langsung.
· Record dapat di retrieve, insert, modifikasi dan delete tanpa mempengaruhi record lain dalam berkas yang sama.
Teknik Pencarian Tabel
· Dasar pemikirannya adalah direktori dari nilai key dan address.
· Lebih cepat menggunakan binary search dibanding dengan sequential search.
Keuntungan :
1. Dapat meng-akses record dengan cepat bila diketahui nilai key.
2. Nilai key berupa field, dapat diterjemahkan menjadi alamat.
3. Nilai key adalah address space indepedent.
Teknik Kalkulasi Alamat
· R (Nilai key) ◊ address
Nilai key = dengan melakukan kalkulasi terhadap nilai key.
· Benturan (collision) dapat terjadi apabila terdapat alamat relatif yang sama untuk nilai key yang berbeda.
· Cara mengatasi benturan, antara lain :
- Scatter diagram techniques
- Randomizing techniques
- Key to address transformation methods
- Direct addressing techniques
- Hash tables methods
- Hashing
o Tujuan Utama Hashing :
Agar dua buah kunci yang berbeda tidak mempunyai nilai relative address yang sama.
o Perbandingan fungsi hash :
Division Remainder ;
Menggunakan metode pembagian.
Untuk distribusi nilai key yang tidak diketahui.
Mid Square ;
Menggunakan metode perpangkatan.
Untuk file denganfaktor cukup rendah.
Folding ;
Menggunakan metode penjumlahan.
Mudah dalam perhitungan, baik bila panjang nilai key = panjang address.
o Keuntungan Hashing :
· Nilai key dapat digunakan langsung.
· Nilai key adalah address space berubah.
o Kelemahan Hashing :
· Membutuhkan waktu proses untuk implementasi dan mengatasi benturan.
Pendekatan masalah Collision :
Open Addressing ;
Menemukan address yang bukan home address untuk
Separate Overflow ;
Menemukan address untuuk
Teknik Mengatasi Collision :
a. Linier Probing (Pendekatan Open Addressing) ;
Proses pencarian secara sequential dari home address sampai lokasi yang kosong.
Harus ada penentuan apakah address kosong.
b. Addressing (Pendekatan Separate Overflow) ;
Menggunakan double hashing.
Memakai fungsi hash kedua terhadap hasil dari fungsi hash pertama.
Hasilnya bisa di primary area atau separate overflow area.
Fungsi hash yang umum digunakan :
1. Division Remainder
R(nilai key) ◊ address
Nomor relatif dari suatu nilai key merupakan sisa dari hasil pembagian nilai key tersebut denga suatu bilangan.
Perhitungan alamat relatif :
Faktor muat = jumlah record dalam berkas
max. Jumlah record dalam berkas
Mencari hasil bagi = nilai key
max + (faktor prima <>
Alamat relatif = sisa pembagian + 1
Contoh :
Berkas berisi 4000 record
Load factor 0,8
Nilai key 987654321
v 0,8 = 4000
max record
max = 4000
0,8
= 5000
v = 987654321
5000 + 3
= 197412 sisa 2085
v Alamat relatif = 2085 + 1
= 2086
2. Mid Square
Nilai key dikuadratkan kemudian beberapa digit diambil dari tengah. Alamt relatif, diambil mulai dari digit .........
∑ digit dari nilai key kuadrat
2
Contoh soal:
untuk berkas 4000 record, dibutuhkan 4 digit.
1 2 3 4 5 6 7 8 9 1524157875019052 8 7 5 0
^^^^^^^^
16 / 2 = 8
9 8 7 6 5 4 3 2 1 975461055789911041 5 7 8 9
^^^^^^^^^
18 / 2 = 9
3. Folding
Nilai key dibagi menjadi beberapa bagian.
Setiap bagian (kecuali bagian terakhir) mempunyai digit sama dengan digit alamat relative.
Bagian-bagian ini dilipat dan dijumlah.
Hasil penjumlahan adalah alamat relatif (digit tertinggi dibuang bila diperlukan).
Contoh :
4 digit untuk alamat relatif.
1 2 3 4 5 6 7 8 9 (nilai key)
^ ^
1 2 3 4 5
9 8 7 6 +
1 3 2 2 1 3 2 2 1
Tiga teknik dasar fungsi Pemetaan R
1. Pemetaan langsung (Direct Mapping)
Teknik ini merupakan teknik yang sederhana untuk menerjemahkan nilai record key menjadi address.
Dua cara Pemetaan Langsung :
a. Pengalamatan Mutlak (Absolut Addressing)
R (Nilai key) → Address
Nilai key = alamat mutlak
Nilai key = alamat sebenarnya dimana record tersimpan. Pada saat penyimpanan dan pemakaian record, harus diketahui dan diberikan pemakai.
b. Pengalamatan Relatif (Relative Addressing) ;
R (Nilai key) → Address
Nilai key = alamat relatif.
Nilai key = urutan record tersebut dalam berkas.
Contoh :
4 digit untuk jenis barang (9999).
Padahal hanya ada 2000 jenis barang.
Pemborosan 80% ruang penyimpanan.
Teknik Pencarian Tabel (Directory Look Up)
· Dasar pemikiran pendekatan pencarian tabel adalah sebuah tabel atau direktori dari nilai key dan address.
· Keuntungan dari Pencarian Tabel :
- Sebuah record dapat diakses dengan cepat, setelah nilai key dalam direktori ditentukan.
- Nilai key dapat berupa field yang mudah dimengerti seperti PART NUMBER, NPM, karena nilai key tersebut akan diterjemahkan menjadi alamat.
- Nilai key adalah address space independent, dimana reorganisasi berkas tak akan memepengaruhi nilai key, yang berubah adalah alamat dalam direktori.
Teknik Kalkulasi Alamat
· Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif.
· Salah satu kelemahan dari teknik pengalamatan relatif adalah ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key.
· Salah satu masalah dari teknik ini adalah ditemukannya alamat relatif yang sama untuk nilai key yang berbeda.
· Keadaan dimana :
R(K1) = R(K2) ,disebut benturan
K1 ¹ K2 ,atau collision
· Sedangkan nilai key K1 dan
· Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.
Teknik-teknik yang terdapat pada kalkulasi alamat :
- Scatter storage techniques
- Randomizing techniques
- Key-to-address transformation methods
- Direct addressing techniques
- Hash table methods
- Hashing
Tidak ada komentar:
Posting Komentar