Apa yang dimaksud dengan organisasi berkas relatif jelaskan

Full PDF PackageDownload Full PDF Package

This Paper

A short summary of this paper

37 Full PDFs related to this paper

Download

PDF Pack

ORGANISASI BERKAS RELATIFSalah satu cara yang efektif dalam mengorganisasikan sekumpulan record yangmembutuhkan akses sebuah record dengan cepat adalah ORGANISASI BERKASRELATIF. Dalam berkas relatif ada hubungan antara KEY YANG DIPAKAI untukmengidentifikasi record dengan LOKASI RECORD dalam penyimpan sekunder.Perlu diperhatikan bahwa URUTAN RECORD SECARA LOGIC tak adahubungannya dengan URUTAN SECARA FISIK. Record tidak perlu tersotir secara

fisik menurut nilai key.

Ada 3 teknik dasar yang
digunakan untuk menyatakan fungsi pemetaan R, dimana R (NILAI KEY) -> ADRESS.

Pemetaan Langsung (Direct Mapping)
Pencarian Tabel (Directory Look-up)
Kalkulasi (Calculating)

A. TEKNIK PEMETAKAN LANGSUNGTeknik ini merupakan yang sederhana untuk menerjemahkan nilai record keymenjadi address. Ada dua cara dalam pemetaan langsung:1) Pengalamatan mutlak (absolute addressing)

2) Pengalamatan relatif (relative addressing)

Pengalamatan MutlakFungsi pemetaan R (NILAI KEY) ADDRESS, di mana NILAI KEY = ALAMATMUTLAK. Fungsi pemetaan ini disebut PENGALAMATAN MUTLAK. Nilai keydiberikan oleh pemakai program yang sama dengan ADDRESS SEBENARNYAdari record tersebut disimpan pada penyimpanan sekunder. Pada waktu recordtersebut disimpan, lokasi penyimpanan record (nomor silinder, nomor surface,nomor record) bila dipakai CYLINDER ADDRESSING atau (nomor sector, nomorrecord) bila dipakai SECTOR ADDRESSING harus ditentukan oleh pemakai.Begitu pula pada waktu record tersebut di retrieve, lokasi mutlak itu harusdiketahui dan diberikan pemakai. Ada 2 keuntungan dari pengalamatanmutlak:Fungsi pemetaan R sangat sederhanaTidak membutuhkan sekunder (retrieve lebih cepat)Kelemahannya :Pemakai harus mengetahui dengan pasti record-record yang disimpansecara fisik.
Pemakai tidak dapat menggunakan nilai key seperti ACCOUNT.

Alamat mutlak adalah device dependent. Perbaikan atau perubahan alat,dimana berkas berada, akan mengubah nilai key.Alamat mutlak adalah address space dependent. Reorganisasi berkasrelatif akan menyebabkan nilai key berubah. Reorganisasi bertujuanmemperbesar ruang alamat di mana sampah (garbage) akan dibuang

atau dapat juga memperkecil ruang alamat.

Pengalamatan RelatifFungsi pemetaan R (NILAI KEY) ADDRESS, dimana NILAI KEY = ALAMATRELATIF. Fungsi pemetaan ini disebut PENGALAMATAN RELATIF. Alamat relatifdari sebuah record dalam sebuah berkas adalah urutan record tersebut dalamberkas. Sebuah berkas dengan N record mempunyai record dengan alamatrelatif dari himpunan (1, 2, 3, …, N-2, N, N-1) Record yang ke-I mempunyaialamat relatif I dan I-1.Keuntungan dari pengalamatan relatif:Fungsi pemetaan R sangat sederhanaNilai key dari sebuah record dapat ditentukan lokasi recordnya dalamsebuah penyimpanan sekunder tanpa memerlukan waktu proses berarti.Alamat relatif tidak tepat dikatakan sebagai device dependent seperti padaalamat multak, karena itu kelemahan tersebut dapat dihilangkan padapengalamatan relatif. Namun seperti pada pengalamatan mutlak,pengalamatan relatif juga address space dependent. Nilai key dari sebuah fielddapat dipakai sebagai alamat relatif. Misal dari 2000 jenis barang yang
mempunyai nilai key PART NUMBER dipakai sebagai alamat relatif. Part number 1001 mempunyai alamat relatif 1001. Kelemahan nilai key dari sebuah field dipakai sebagai alamat relatif adalah terjadinya pemborosan ruangan dimana berkas relatif menyediakan ruang (alamat relatif) untuk 9999 jenis barang dari sebenarnya 2000 jenis barang, terjadi pemborosan kurang lebih 80%. Untuk nilai key NIP yang terdiri dari 9 digit dari berkas pegawai yang berjumlah 2000 record akan terjadi pemborosan 99,99998% ruang dimana berkas relatif menyediakan alamat relatif untuk 999.999.999 pegawai. Untuk mengatasi pemborosan ruang adalah dengan cara mendapatkan sebuah key yang nilai jangkauannya mempunyai populasi tinggi. Sebagai contoh 8200 jenis barang akan lebih efisien mempunyai PART NUMBER sebanyak 4 digit sebagai nilai key-nya yang juga merupakan alamat relatif. Ruang kosong sebesar 20% dipakai untuk penambahan record.

B. TEKNIK PENCARIAN TABELTeknik pencarian tabel jauh lebih baik disbanding dengan teknik pemetaanlangsung.Hanya saja memerlukan biaya baru dalam pemeliharaannya. Kitaakan lihat bahwa pendekatan ini hamper serupa dengan teknik yang dipakaipada berkas indeks sekuensial. Dasar pemikiran pendekatan pencarian tabeladalah sebuah tabel atau direktori dari nilai key dan address. Untukmenemukan sebuah record dalam berkas relatif, pertama dicari dalamdirektori nilai key dari record tersebut, akan menunjukkan alamat dimana

record tersebut berada dalam penyimpanan.

Keuntungan dari pencarian tabel:Sebuah record dapat di akses dengan cepat, setelah nilai key dalamdirektori ditentukan .Nilai key dapat berupa field yang mudah dimengerti seperti PARTNUMBER, NMP, karena nilai key tersebut akan diterjemahkan menjadialamat.Nilai key adalah address space independent, dimana reorganisasi berkastak akan mempengaruhi nilai key, yang berubah adalah alamat dalamdirektori.Teknik ini banyak dipengaruhi oleh organisasi direktorinya. Apabila nilai keydisimpan secara urut pada direktori, akses secara binary jauh lebih cepat

dibanding secara sekuensial.

C. TEKNIK KALKULASI ALAMAT.Pendekatan lain yang umum dipakai untuk mengimplementasikan R (NILAIKEY) ADDRESS adalah dengan melakukan kalkulasi terhadap nilai key.Hasilnya adalah alamat alternatif. Teknik ini dapat dipakai sendiri ataubersama-sama dengan pencarian tabel. Ide dasar dari kalkulasi alamat adalahmengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil alamatalternatif. Salah satu kelemahan dari teknik pengalamatanrelatif adalah ruangharus disediakan sebanyak jangkauan nilai key, terlepas dari beberapa banyaknilai key. Sebagai contoh, dari 2000 jenis barang hendak dibuat alamat relatifsebanyak 2000 lebih sedikit. Cara ini dapat dilakukan dengan teknik kalkulasialamat. Salah satu masalah dari teknik ini adalah ditemukannya alamat relatifyang sama untuk nilai key yang berbeda. Keadaan di alamat relatif yang samauntuk nilai key yang berbeda. Keadaan dimana R (K1) = R (K2) dan K1 # K2disebut BENTURAN (COLLISION). Sedangkan nilai key K1 dan K2 disebutSYNONIM. Ada banyak cara untuk mengatasi benturan, antara lain:Scatter diagram techniquesRandomizing techniquesKey to address transformation methodsDirect addressingbtechniques

Hash tables methods

ORGANISASI BERKAS RELATIF

Suatu cara yang efektif dalam mengorganisasi sekumpulan record yang membutuhkan akses sebuah record dengan cepat adalah organisasi berkas relatif. Dalam berkas relatif ada hubungan antara key yang dipakai untuk mengidentifikasi record dengan lokasi record dalam penyimpanan sekunder.

Ada 3 teknik dasar yang digunakan untuk menyatakan fungsi pemetaan R, dimana R (nilai key) address

1. Direct mapping (pemetaan langsung)

2. Directory look up (pencarian tabel)

3. Calculation (kalkulasi)

Direct mapping (pemetaan langsung)

Teknik ini merupakan teknik yang sederhana untuk menerjemahkan nilai record key menjadi address. Ada 2 cara dalam pemetaan langsung :

1. Absolute Addressing (Pengalamatan Mutlak)

2. Relative Addressing (Pengalamatan Relatif)

Pengalamatan Mutlak

R(nilai key) Address

Nilai key = alamat mutlak

Jika nilai key yang diberikan oleh pemakai program sama dengan address sebenarnya dari record tersebut pada penyimpanan sekunder. Pada waktu record tersebut disimpan, lokasi penyimpanan record (nomor silinder, nomor permukaan, nomor record) bila dipakai cylinder addressing atau (nomor sektor, nomor record) bila dipakai sector addressing harus ditentukan oleh pamakai.

Keuntungan dari pengalamatan mutlak adalah sebagai berikut :

1. Fungsi pemetaan R sangat sederhana

2. Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder

Kelemahannya dari pengalaman mutlak adalah sebagai berikut :

3. Pemakai harus mengetahui dengan pasti record-record yang disimpan secara fisik

4. Alamat mutlak adalah device dependent, perbaikan atau pengubahan device, dimana berkas berada akan mengubah nilai key

5. Alamat mutlak adalah address space dependent, reorganisasi berkas relatif akan menyebabkan nilai key berubah.

· Pengalamatan Relatif

R(nilai key) Address

Nilai key = alamat relative

Alamat relatif dari sebuah record dalam sebuah berkas adalah urutan record tersebut dalam berkas. Sebuah berkas dengan N record mempunyai record dengan alamat relatif dari himpunan (1,2,3, …, N -2, N -1). Record yang ke I mempunyai alamat relatif I atau I – 1 (bila mulai dihitung dari 0).

Keuntungan dari pengalamatan relatif adalah Sebagai berikut:

Ø Fungsi pemetaan R sangat sederhana

Ø Nilai key dari sebuah record dapat ditentukan lokasi recordnya dalam sebuah penyimpanan sekunder tanpa memerlukan waktu proses yang berarti.

Kelemahannya adalah sebagai berikut :

Ø Alamat relatif adalah bukan device dependent

Ø Alamat relatif adalah address space dependent

Ø Terjadinya pemborosan ruangan.

2. Teknik Pencarian Tabel.

Dasar pemikiran pendekatan pencarian tabel adalah sebuah tabel atau direktori dari nilai key dan address. Untuk menemukan sebuah record dalam berkas relatif, pertama dicari dalam direktori nilai key dari record tersebut, yang akan menunjukan alamat dimana record tersebut berada dalam penyimpanan

Data dalam direktori tersebut disusun secara urut menurut nilai key, sehingga pencarian nilai key dalam direktori lebih cepat dengan binary search dibanding sequential search. Alternatif lain, direktori dapat disusun dalam binary search tree, m-way search tree atau B-tree.

Keuntungan dari pencarian tabel

1. Sebuah record dapat diakses dengan cepat, setelah nilai key dalam direktori ditentukan.

2. Nilai key dapat berupa field yang mudah dimengerti seperti PART NUMBER, NPM, karena nilai key tersebut akan diterjemahkan menjadi alamat.

3. Nilai key adalah address space independent, dimana reorganisasi berkas tak akan memepengaruhi nilai key, yang berubah adalah alamat dalam direktori.

3. Teknik Kalkulasi Alamat

R (NILAI KEY) ADDRESS

Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif. Ide dasar dari kalkulasi alamat adalah mengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil 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 K2 disebut synomin.

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

Disini yang akan kita bahas mengenai teknik hashing.

Kalkulasi terhadap nilai key untuk mendapatkan sebuah alamat disebut fungsi hash.

B. PROSES

Pada waktu sebuah record ditulis ke dalam berkas relatif, fungsi pemetaan R digunakan untuk menerjemahkan NILAI KEY dari record menjadi ADDRESS, dimana record tersebut disimpan.

Begitu pula pada waktu akan me-retrieve record dengan nilai key tertentu, fungsi pemetaan R digunakan terhadap nilai key tersebut, untuk menerjemahkan nilai key itu menjadi sebuah address dalam penyimpanan sekunder, dimana record tersebut ditemukan.

C. Kelebihan

• Dengan organisasi berkas langsung, untuk menemukan suatu rekaman tidak melalui proses pencarian, namun bisa langsung menuju alamat yang ditempati rekaman

• Pada awalnya, untuk tujuan tersebut maka digunakan cara dengan menyimpan rekaman pada alamat yang sama dengan nilai kunci rekaman tersebut

• Contohnya : rekaman dengan kunci 100 akan disimpan di alamat 100

• Sehingga untuk menemukan sebuah rekaman cukup melihat nilai kunci dan menuju ke alamat yang ditunjuk oleh kunci rekaman tersebut

• Contoh : untuk membaca rekaman dengan kunci 55 langsung saja menuju alamat 55

D. Kelemahan

Dengan menerjemahkan langsung dari kunci rekaman ke alamat rekaman, maka akan berlaku suatu hubungan korespondensi satu-satu antara kunci dengan alamat rekaman .Hal ini menyebabkan harus disediakannya ruang yang sangat besar untuk menampung setiap kemungkinan nilai kunci yang ada

Contohnya : untuk menyimpan data PNS yang kuncinya adalah NIP (terdiri dari 9 digit) dibutuhkan sebanyak satu milyar alamat, karena kemungkinan yang dapat muncul dari kode 9 digit adalah mulai dari angka 000000000 hingga 999999999)