organisasi berkas relatif -...
Post on 24-Jan-2021
41 Views
Preview:
TRANSCRIPT
Organisasi Berkas RelatifSistem Berkas
Rama Dian Syah
Materi
01 Organisasi Berkas Relatif
Pengertian Organisasi Berkas Relatif
02 Proses Berkas Relatif
Teknik Pemetaan Langsung, Teknik Pencarian Tabel, Teknik
Kalkulasi Alatam
03 Metode Hashing
Division Remainder, Mid Square Hasing, Hashing by Folding
Organisasi Berkas Relatif
• Suatu cara yang efektif dalam mengorganisasisekumpulan record yang membutuhkan akses sebuahrecord dengan cepat
• Dalam berkas relative ada hubungan antara key yangdipakai untuk mengidentifikasi record dengan lokasirecord dalam penyimpanan sekunder
• Hubungan yang akan menterjemahkan antara NILAI KEYdan ADDRESS dinyatakan sebagai R, yang menyatakanfungsi pemetaan
R(NILAI KEY) → ADDRESS
Proses Berkas Relatif
• Pada waktu sebuah record ditulis kedalam berkas relatif,fungsi pemetaan R digunakan untuk menerjemahkanNILAI KEY dari record menjadi ADDRESS, dimana recordtersebut disimpan.
• Organisasi berkas relatif harus disimpan dalam mediaDASD, seperti magnetic disk atau magnetic drum
• Organisasi berkas relatif memiliki kemampuan mengaksesrecord secara cepat sehingga sering digunakan dalamproses interactive.
Proses Berkas Relatif
• Akses pada berkas relatif tidak perlu mengakses semuarecord, cukup mengakses langsung record yangdikehendaki.
• Record dari berkas relative dapat diupdate langsungtanpa perlu merekam kembali semua record
• Keuntungan dari berkas relative adalah kemampuanmengakses record secara langsung. Sebuah record dapatdi retrive, insert, modifikasi atau di delete tanpamempengaruhi record lain dalam berkas yang sama.
Proses Berkas Relatif
Ada 3 Teknik dasar yang digunakan untuk menyatakan
fungsi R, dimana
R(NILAI KEY) → ADDRESS
yaitu:
1. Teknik Pemetaan Langsung (Direct Mapping)
2. Teknik Pencarian Tabel (Directory Look Up)
3. Teknik Kalkulasi Alamat
Teknik Pemetaan Langsung
1. Pengalamatan Mutlak
(Absolute Addresing)
R(NILAI KEY) → ADDRESS
NILAI KEY = ALAMAT MUTLAK
• Nilai key yang diberikan
oleh pemakai program
sama dengan Address
sebenarnya dari record
tersebut pada penyimpanan
sekunder.
Keuntungan Absolute Addresing:
• Fungsi Pemetaan R sangat Sederhana
• Tidak Membutuhkan waktu lama dalam
menentukan lokasi record pada
penyimpanan sekunder
Kelemahan Absolute Addresing:
• Pemakai harus mengetahui dengan pasti
record yang disimpan secara fisik
• Merupakan device dependent. Perbaikan
atau pengubahan device, dimana berkas
berada akan mengubah nilai key
• Merupakan address space dependent.
Reorganisasi berkas relative akan
menyebabkan nilai key berubah
Teknik Pemetaan Langsung
2. Pengalamatan Relatif
(Relative Addresing)
R(NILAI KEY) → ADDRESS
NILAI KEY = ALAMAT RELATIF
• Alamat relatif dari sebuah
record dalam sebuah berkas
adalah urutan record tersebut
dalam berkas
Keuntungan Relative Addresing:
• Fungsi Pemetaan R sangat Sederhana
• Nilai key dari sebuah record dapat
menentukan lokasi recordnya dalam
sebuah penyimpanan sekunder tanpa
memerlukan waktu proses yang berarti.
Kelemahan Relative Addresing:
• Alamat relatif adalah bukan device
dependent
• Alamat relative merupakan address
space dependent
• Terjadinya pemborosan ruang
Teknik Pencarian Tabel (Directoriy Look up)
• Teknik ini jauh lebih baik
dibanding dengan Teknik
pemetaan langsung.
• Teknik ini diimplementasikan
sebagai suatu array dari
nilai key dan alamat record.
• Keuntungan dari Teknik pencarian
tabel:
• Sebuah record dapat diakses
dengan cepat, setelah nilai key
dalam direktori ditentukan.
• Nilai key dapat berupa field yang
mudah dimengerti seperti No
Induk, NPM, karena nilai key
tersebut akan diterjemahkan
menjadi alamat
• Nilai key adalah address space
independent, dimana reorganisasi
berkas tidak akan mempengaruhi
nilai key, yang berubah alamat
dalam direktori
Teknik Pencarian Tabel (Directoriy Look up)
Berkas relatif dengan struktur tabel Berkas relatif dengan struktur pohon
Teknik Kalkulasi Alamat
• Teknik ini melakukan kalkulasi terhadap nilai key, hasilnya
adalah alamat relative
• Dasar dari kalkulasi alamat adalah mengubah jangkuan
nilai key yang mungkin menjadi sejumlah kecil alamat
relative
• Salah satu kelemahan dari teknik pengalamatan relative
adalah ruang harus disediakan sebanyak jangkauan nilai
key, terlepas dari berapa banyak nilai key.
Teknik Kalkulasi Alamat
• Masalah dari Teknik kalkulasi alamat adalah
ditemukannya alamat relative yang sama untuk nilai key
yang berbeda
• Keadaan benturan (collision) dimana:
R(K1) = R(K2)
K1 ≠ K2
Nilai K1 dan K2 disebut Synonim
• Synonim adalah dua atau lebih nilai key yang berbeda
pada hash ke home address yang sama
Teknik Kalkulasi Alamat
• Teknik-Teknik yang terdapat pada kalkulasi alamat:
1. Scatter Storage Techniques
2. Randomizing Techniques
3. Key-to-address transformation methods
4. Direct addressing techniques
5. Hash table methods
6. Hashing
Metode Hashing
• Hasing merupakan kalkulasi terhadap nilai key untuk
mendapatkan sebuah alamat (address)
• Keuntungan pemakaian Hashing:
• Nilai key yang sebenarnya dapat dipakai karena diterjemahkan ke dalam
sebuah alamat
• Nilai key adalah address space independent bila berkas direorganisasi,
fungsi hash berubah tetapi nilai key tetap
• Kelemahan pemakaian Hashing:
• Membutuhkan waktu proses dalam mengimplementasikan fungsi hash
• Membutuhkan waktu proses dan akses i/o dalam mengatasi benturan
(Collision)
Metode Hashing• Hasing dapat digunakan bersama-
sama dengan pencarian table
• Penampilan fungsi hash
bergantung pada:
1. Distribusi nilai key yang dipakai
2. Banyaknya nilai key dipakai
relative terhadap ukuran dari
ruangan alamat.
3. Banyak record yang dapat
disimpan pada alamat tertentu
tanpa menyebabkan benturan
4. Teknik yang dipakai untuk
mengatasi benturan
Metode Hashing
• Fungsi hash yang umum digunakan:
1. Division remainder
2. Mid square
3. Folding
Division Remainder• Jumlah lokasi memori yang dihitung, kemudian jumlah tersebut
digunakan sebagai pembagi untuk membagi nilai asli dan
menghasilkan sisa. Sisa tersebut adalah nilai hashnya.
• Rumus:
f(kunci) = kunci mod N
dengan:
N: Jumlah lokasi memori
Mod: sisa bagi pembagian
Keterangan:
• Fungsi hash tersebut akan menempatkan record dengan kunci pada suatu lokasi
memori yang beralamat f(kunci).
• Alamat relatif didapat dari sisa pembagian + 1
Division Remainder• Contoh:
Jumlah lokasi memori yang tersedia ada 11 dan satu file dengan 8 record menggunakan
nilai kunci sbb: 12, 21, 68, 38,52, 70, 44, 18.
Tentukan alamat relatif menggunakan division remainder!
• (12 mod 11) + 1 = 1 + 1 = 2 ; simpan 12 di lokasi 2 Jumlah lokasi memori :11
• (21 mod 11) + 1 = 10 + 1 = 11 ; simpan 21 dilokasi 11 Jumlah record: 8
• (68 mod 11) + 1 = 2 + 1 = 3 ; simpan 68 dilokasi 3
• (38 mod 11) + 1 = 5 + 1 = 6 ; simpan 38 dilokasi 6
• (52 mod 11) + 1 = 9 + 1 = 10 ; simpan 52 dilokasi 10
• (70 mod 11) + 1 = 4 + 1 = 5 ; simpan 70 dilokasi 5
• (44 mod 11) + 1 = 0 + 1 = 1 ; simpan 44 dilokasi 1
• (18 mod 11) + 1 = 7 + 1 = 8 ; simpan 18 dilokasi 8
Sehingga:
Index 1 2 3 4 5 6 7 8 9 10 11
Nilai key 44 12 68 - 70 38 - 18 - 52 21
Mid Square Hashing• Mid square hashing adalah teknik dimana kunci unik
dihasilkan.
• Nilai kunci diambil dan dikuadratkan, kemudian beberapa
digit diekstraksi.
• Angka-angka yang diekstrak ini membentuk angka yang
diambil sebagai alamat relatif.
• Teknik ini dapat menghasilkan kunci dengan keacakan
tinggi jika nilai kunci yang cukup besar diambil.
Mid Square Hashing• Contoh:
Digit mulai posisi 7 sampai 10 (dari kanan) membentuk alamat relative
Keterangan:
• Dari perhitungan terjadi benturan (Collision) untuk nomor 000000472 dan
117400000
Nilai Kunci Kunci DIkuadratkan Alamat Relatif
345237459 119188903096777000 3096
000000472 00000000000222784 0000
890765345 793462899852969000 9852
117400000 13782760000000000 0000
Hashing by folding• Untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa
bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah
digit yang sama dengan alamat relative.
• Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah.
Hasilnya, digit yang tertinggi dibuang (bila diperlukan).
• Contoh:
Kunci 123456, 234351, 222456, 321654, dilipat menjadi 2 bagian, setiap 3 digit.
Maka :
123+654 = 777 ; simpan 123456 dilokasi 777
234+153 = 387 ; simpan 234351 dilokasi 387
222+654 = 876 ; simpan 222456 dilokasi 876
321+456 = 777; simpan 321654 dilokasi 777
Dari perhitungan terjadi Benturan (Collision) untuk nomor 123456 dan 321654.
top related