ORGANISASI ORGANISASI BERKAS RELATIFBERKAS RELATIF

ORGANISASI ORGANISASI BERKAS RELATIFBERKAS RELATIF

By:Syaharullah Disa, S.Kom., By:Syaharullah Disa, S.Kom., M.TM.T

• PENGERTIAN BERKAS RELATIFPENGERTIAN BERKAS RELATIF– Suatu cara yang efektif dalam mengorganisasi sekumpulan record

yang membutuhkan akses sebuah record dengan cepat.

– Dalam berkas relatif ada hungungan antara KEY YANG DIPAKAI untuk mengidentifikasi record dalam penyimpan sekunder

– Record tidak perlu tersortir secara fisik menurut nilai key

• Bagaimana record yang ke-N ditemukan? Dalam hal ini, perlu kita buat hubungan yang akan menerjemahkan NILAI KEY dan ADDRESS, hubungan ini dinyatakan sebagai R, yang menyatakan fungsi pemetaan

R(NILAI KEY) ADDRESS

• Dari nilai key ke address dalam penyimpanan sekunder. Pada waktu sebuah record ditulis kedalam berkas Pada waktu sebuah record ditulis kedalam berkas relatif, fungsi pemetaan R digunakan untuk relatif, fungsi pemetaan R digunakan untuk menerjemahkan NILAI KEY DARI RECORD menjadi menerjemahkan NILAI KEY DARI RECORD menjadi ADDRESS, dimana record tersebut disimpan.ADDRESS, dimana record tersebut disimpan.

• Berkas relatif harus disimpan dalam media DASD, Berkas relatif harus disimpan dalam media DASD, seperti magnetic disk atau drum.seperti magnetic disk atau drum.

Catatan :Catatan :• Kita tidak perlu mengakses semua record master file, Kita tidak perlu mengakses semua record master file,

cukup mengakses langsung record yang dikehendaki.cukup mengakses langsung record yang dikehendaki.• Record dari berkas relatif dapat di update langsung Record dari berkas relatif dapat di update langsung

tanpa perlu merekam kembali semua record.tanpa perlu merekam kembali semua record.• Keuntungan dari berkas relatif ini adalah kemampuan Keuntungan dari berkas relatif ini adalah kemampuan

mengakses record secara langsung. Sebuah record mengakses record secara langsung. Sebuah record dapat di retrieve, insert, modifikasi atau di delete; dapat di retrieve, insert, modifikasi atau di delete; tampa mempengaruhi record lain dalam berkas yang tampa mempengaruhi record lain dalam berkas yang sama.sama.

Karna Keamampuan mengakses record tertentu secara cepat, maka organisasi berkas relatif sering digunakan dalam proses interactive. Sebagai contoh, sebuah on-line sistem perbankan mempunyai berkas induk dengan struktur sebagai berikut:

Field ACCOUNT NUMBER dipakai sebagai nilai key untuk kedua berkas tersebut.

Pada saat nilai key ACCOUNT NUMBER dimasukkan ke dalam transaksi, nilai key tersebut akan me-retrieve secara langsung record yang ada pada berkas induk. Jika TRANS-TYPE = ‘T’, mana BALANCE akan ditampilkan di layar. Jika TRANS-TYPE = ‘C’ atau ‘D’, maka record-record dari berkas induk CUSTOMER-ACCOUND akan di modifikasi dengan AMOUNT data DATE yang ada di berkas transaksi, dimana ACCOUND NUMBER yang menentukan lokasi record dalam berkas tersebut.

Ada dua hal penting yg perlu dicatat; pertama, tidak perlu mengakses semua record berkas induk, cukup mengakses langsung record yg dikehendaki. Kedua, record dari berkas relatif dapat di-update langsung tanpa perlu merekam kembali semua record

Ada 3 teknik dasar yang digunakan untuk menyatakan fungsi Ada 3 teknik dasar yang digunakan untuk menyatakan fungsi pemetaan R, dimana R(NILAI KEY) ADDRESS, yaitu :pemetaan R, dimana R(NILAI KEY) ADDRESS, yaitu :

1.1. Teknik Pemetaan Langsung (Direct Mapping)Teknik Pemetaan Langsung (Direct Mapping)

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

a. Absolute Addressing (Pengalamatan Mutlak)a. Absolute Addressing (Pengalamatan Mutlak)

R(NILAI KEY) ADDRESSR(NILAI KEY) ADDRESS

NILAI KEY = ALAMAT MUTLAKNILAI KEY = ALAMAT MUTLAK

Nilai key yang diberikan oleh pemakai program Nilai key yang diberikan oleh pemakai program sama dengan ADDRESS SEBENARNYA dari sama dengan ADDRESS SEBENARNYA dari record tersebut pada penyimpanan sekunder.record tersebut pada penyimpanan sekunder.

KEUNTUNGANKEUNTUNGAN KELEMAHANKELEMAHAN

Fungsi pemetaan R sangat Fungsi pemetaan R sangat sederhanasederhana

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

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

Merupakan device dependent.Merupakan device dependent.Perbaikan atau pengubahan device, Perbaikan atau pengubahan device, dimana berkas berada akan dimana berkas berada akan mengubah nilai key.mengubah nilai key.

Merupakan address space dependent.Merupakan address space dependent.Reorganisasi berkas relatif akan Reorganisasi berkas relatif akan menyebabkan nilai key berubah.menyebabkan nilai key berubah.

b. Pengalamatan Relatifb. Pengalamatan Relatif R(NILAI KEY) ADDRESS R(NILAI KEY) ADDRESS NILAI KEY = ALAMAT RELATIF NILAI KEY = ALAMAT RELATIF

KEUNTUNGANKEUNTUNGAN KELEMAHANKELEMAHAN

Fungsi pemetaan R sangat Fungsi pemetaan R sangat sederhana.sederhana.

bukan device dependentbukan device dependent

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

Merupakan address space Merupakan address space dependentdependent

Terjadinya pemborosan Terjadinya pemborosan ruanganruangan

2. Teknik Pencarian Tabel (Directory Look Up)2. Teknik Pencarian Tabel (Directory Look Up)

Teknik ini jauh lebih baik dibanding dengan teknik pemetaan langsung. Dalam bentuk yg sederhana, direktori diimplementasikan sebagai suatu array dari nilai key; record alamat, digambarkan sebagai berikut:

• Di sini data dalam direktori disusun secara urut menurut nilai key, sehingga pencarian nilai key dalam direktori lebih cepat dengan binary search dibanding sequentian search.

• Alternatif lain, direktori dapat disusun dalam binary search tree, M-way search tree, atau B-tree.

Keuntungan dari Pencarian Tabel :Keuntungan dari Pencarian Tabel :

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

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

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

3. Teknik Kalkulasi Alamat3. Teknik Kalkulasi Alamat

• Salah satu masalah dari teknik ini adalah ditemukannya Salah satu masalah dari teknik ini adalah ditemukannya alamat relatif yang sama untuk nilai key yang berbeda.alamat relatif yang sama untuk nilai key yang berbeda.

Keadaan dimana :Keadaan dimana : R(K1) = R(K2) disebut benturanR(K1) = R(K2) disebut benturan

K1 K1 K2 atau collision K2 atau collision

• Ada banyak cara untuk mengatasi benturan, antara lain,Ada banyak cara untuk mengatasi benturan, antara lain,

1.1. Scatter storage techniquesScatter storage techniques2.2. Randomizing techniquesRandomizing techniques3.3. Key-to-address transformation Key-to-address transformation

methodsmethods4.4. Direct addressing techniquesDirect addressing techniques5.5. Hash table methodsHash table methods6.6. HashingHashing

Hasing

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

• Keuntungan:Keuntungan:– Nilai key yang sebenarnya dapat dipakai karena diterjemahkan Nilai key yang sebenarnya dapat dipakai karena diterjemahkan

kedalam sebuah alamat.kedalam sebuah alamat.– Nilai key adalah address space independent bila berkas Nilai key adalah address space independent bila berkas

direorganisasi, fungsi hash berubah tetapi nilai key tetap.direorganisasi, fungsi hash berubah tetapi nilai key tetap.• Kelemahan :Kelemahan :

– Membutuhkan waktu proses dalam mengimplementasikan fungsi Membutuhkan waktu proses dalam mengimplementasikan fungsi hash.hash.

– Membutuhkan waktu proses dan akses I/O dalam mengatasi Membutuhkan waktu proses dan akses I/O dalam mengatasi benturan.benturan.

• Jelaslah bahwa tujuan utama dari fungsi hash adalah mengurangi Jelaslah bahwa tujuan utama dari fungsi hash adalah mengurangi benturan. Kumpulan dari synonim kadang disebut KELAS EKIVALEN. benturan. Kumpulan dari synonim kadang disebut KELAS EKIVALEN. Fungsi hash yg baik adalah mempunyai kelas ekivalen yg kecil dan Fungsi hash yg baik adalah mempunyai kelas ekivalen yg kecil dan mempunyai kalkulasi sederhanamempunyai kalkulasi sederhana

• Penampilan fungsi hash bergantung pada :Penampilan fungsi hash bergantung pada :– Distribusi nilai key yang dipakaiDistribusi nilai key yang dipakai– Banyaknya nilai key yang dipakai relatif terhadap ukuran dari Banyaknya nilai key yang dipakai relatif terhadap ukuran dari

ruang alamat.ruang alamat.– Banyaknya record yang dapat disimpan pada alamat tertentu Banyaknya record yang dapat disimpan pada alamat tertentu

tanpa menyebabkan benturan.tanpa menyebabkan benturan.– Teknik yang dipakai untuk mengatasi benturanTeknik yang dipakai untuk mengatasi benturan

Beberapa fungsi hash yang umum digunakan :Beberapa fungsi hash yang umum digunakan :

1. Division Remainder1. Division Remainder

– Alamat relatif dari suatu nilai key merupakan sisa Alamat relatif dari suatu nilai key merupakan sisa dari hasil pembagian nilai key tersebut dengan suatu dari hasil pembagian nilai key tersebut dengan suatu bilangan yang disebut sebagai bilangan yang disebut sebagai bilangan pembagi.bilangan pembagi.

– Banyak faktor yang harus dipertimbangkan dalam Banyak faktor yang harus dipertimbangkan dalam pemilihan pembagi :pemilihan pembagi :

1.1. Jangkauan dari nilai key yang dihasilkan dari opersi KEY Jangkauan dari nilai key yang dihasilkan dari opersi KEY MOD DIV adalah 0 sampai DIV-1. MOD DIV adalah 0 sampai DIV-1.

2.2. Pembagi harus diseleksi untuk mengurangi benturan. Pembagi harus diseleksi untuk mengurangi benturan. 3.3. Menurut riset dari W.Buchholz, sebaiknya pembagi itu Menurut riset dari W.Buchholz, sebaiknya pembagi itu

merupakan bilangan prima. merupakan bilangan prima. 4.4. Bukan bilangan prima yang mempunyai faktor prima kurang Bukan bilangan prima yang mempunyai faktor prima kurang

dari 20 akan dapat memberikan jaminan penampilan yang dari 20 akan dapat memberikan jaminan penampilan yang lebih baik.lebih baik.

5.5. Walaupun telah ditentukan pembagi dengan baik untuk Walaupun telah ditentukan pembagi dengan baik untuk mengatasi benturan, bila ruang alamat dari berkas relatif mengatasi benturan, bila ruang alamat dari berkas relatif mendekati penuh, maka peluang terjadinya benturan akan mendekati penuh, maka peluang terjadinya benturan akan meningkat.meningkat.

• Untuk mengukur kepenuhan berkas relatif digunakan Load Untuk mengukur kepenuhan berkas relatif digunakan Load Factor (Faktor Muat).Factor (Faktor Muat).

Load Factor = banyak record dalam berkasLoad Factor = banyak record dalam berkas

max. banyak record dalam berkasmax. banyak record dalam berkas

• Semua fungsi Hash mulai bekerja buruk, bila berkas hampir penuh. Jika faktor muat lebih besar dari 0,7 atau 0,8, maka berkas tersebut harus diperbesar dan direorganisir. Karena itu, jika berkas berisi relatif N record, maka ruang alamat harus mempunyai paling sedikit 0,25 N record Untuk faktor muat 0,8)

• Contoh : Sebuah berkas relatif yang berisi 4000 record, paling sedikit harus mempunyai ruang alamat untuk 5000 record (faktor muat 0,8). Angka yang dekat dengan 5000 dan terdiri dari faktor prima kurang dari 20 adalah angka 5003. Angka ini dipakai sebagai pembagi.

• Alamat relatif didapat dari sisa pembagian + 1

Bilangan pembagi : 5003Bilangan pembagi : 5003

123456789123456789

5003 = 24676 sisa 2761 + 15003 = 24676 sisa 2761 + 1

alamat relatif alamat relatif

987654321 = 197412 sisa 2085 + 1987654321 = 197412 sisa 2085 + 1

5003 alamat relatif5003 alamat relatif

Mid Square HashingMid Square Hashing

• Dalam banyak teknk hasing ini, nilai key dikuadratkan kemudian beberapa digit diambil dari tengah untuk mendapatkan relatif address. Jika relatif address dari N digit dibutuhkan, maka N digit diambil dari tengah-tengah nilai key yang dikuadratkan.

• Pada tabel berikut, digit ke-7 sampai 10 dihitung dari kanan, diambil untuk mendapatkan 4 digit sebagai relatif address.

Hashing by foldingHashing by folding• Untuk mendapatkan alamat relatif, nilai key dibagi menjadi Untuk mendapatkan alamat relatif, nilai key dibagi menjadi

beberapa bagian, setiap bagian (kecuali bagian terakhir) beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif.mempunyai jumlah digit yang sama dengan alamat relatif.

• Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).Hasilnya, digit yang tertinggi dibuang (bila diperlukan).

• Contoh :Contoh :Nilai key 123456789 dan alamat relatif sebanyak 4 digit.Nilai key 123456789 dan alamat relatif sebanyak 4 digit.

1 2345 6789

Menghasilkan :Menghasilkan : 11 2 3 4 52 3 4 5 9 8 7 6 +9 8 7 6 +

1 3 2 2 11 3 2 2 1

Hasil penjumlahan adalah 13221. Digit tertinggi dibuang, sehingga hasil akhir adalah 3221.

3

Perbandingan fungsi HashPerbandingan fungsi Hash

• Teknik Division Remainder memberikan penampilan Teknik Division Remainder memberikan penampilan yang terbaik secara keseluruhan.yang terbaik secara keseluruhan.

• Teknik Mid Square dapat dipakai untuk file dengan Teknik Mid Square dapat dipakai untuk file dengan load factor cukup rendah akan memberikan load factor cukup rendah akan memberikan penampilan baik tetapi kadang-kadang dapat penampilan baik tetapi kadang-kadang dapat menghasilkan penampilan yang buruk dengan menghasilkan penampilan yang buruk dengan beberapa collision.beberapa collision.

• Teknik folding adalah teknik yang paling mudah dalam Teknik folding adalah teknik yang paling mudah dalam perhitungan tetapi dapat memberikan hasil yang salah, perhitungan tetapi dapat memberikan hasil yang salah, kecuali panjang nilai key = panjang address.kecuali panjang nilai key = panjang address.

Pendekatan terhadap masalah CollisionPendekatan terhadap masalah Collision

• 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.

Synonim ChainingSynonim Chaining

• Pendekatan pemecahan collision yang mengakses synonim Pendekatan pemecahan collision yang mengakses synonim dengan fasilitas link list untuk record-recordnya dalam kelas dengan fasilitas link list untuk record-recordnya dalam kelas ekivalen. Adapun link list record-record dengan home address yang ekivalen. Adapun link list record-record dengan home address yang sama tak akan mengurangi jumlah collision, tetapi akan sama tak akan mengurangi jumlah collision, tetapi akan mengurangi waktu akses untuk me-retrieve record-record yang mengurangi waktu akses untuk me-retrieve record-record yang tak ada di home addressnya.tak ada di home addressnya.

Contoh :Contoh : KEY KEY HOME ADDRESS HOME ADDRESS ACTUAL ADDRESS ACTUAL ADDRESS

AdamsAdams 20 20 2020 BatesBates 21 21 2121 CollColl 20 20 2222 DeanDean 21 21 2323 EvansEvans 24 24 2424 FlintFlint 20 20 2525

R20 R21 R22 R23 R24 R25R20 R21 R22 R23 R24 R25 .. Adams .. Bates .. Coll .. Dean .. Evans .. Flint .. ..... Adams .. Bates .. Coll .. Dean .. Evans .. Flint .. ...

gambar hashing dengan synonim chaininggambar hashing dengan synonim chaining

HOME PRIMARY DATA OVERFLOWHOME PRIMARY DATA OVERFLOWADDRESS AREA AREAADDRESS AREA AREA

2020 Adams .. 0 Coll ..Adams .. 0 Coll ..

2121 Bates .. 1 Dean ..Bates .. 1 Dean ..

2222 2 Flint .. 2 Flint .. 2323 3 3 2424 Evans ..Evans ..

Bucket AddressingBucket Addressing

• Pendekatan lain dalam mengatasi collision adalah hash ke dalam Pendekatan lain dalam mengatasi collision adalah hash ke dalam block atau bucket yang dapat memberikan tempat sejumlah record.block atau bucket yang dapat memberikan tempat sejumlah record.

• Contoh :Contoh :Sebuah berkas relatif mempunyai relatif address space dari 0 sampai M Sebuah berkas relatif mempunyai relatif address space dari 0 sampai M

dan sebuah bucket berukuran B record , address space akan terdiri dari dan sebuah bucket berukuran B record , address space akan terdiri dari B(M+1) record. Jika file terdiri dari N record, maka :B(M+1) record. Jika file terdiri dari N record, maka :

Factor Muat = NFactor Muat = N B(M + 1)B(M + 1)

• Record-record yang disimpan dalam sebuah bucket dapat dikelola Record-record yang disimpan dalam sebuah bucket dapat dikelola dalam :dalam :1.1. Dapat disisipkan dalam urutan berdasarkan penempatannya di bucket.Dapat disisipkan dalam urutan berdasarkan penempatannya di bucket.2.2. Dapat dipertahankan urutan nilai key-nya.Dapat dipertahankan urutan nilai key-nya.

Contoh :Contoh : KEY HOME ADDRESSKEY HOME ADDRESS

Green Green 3030 Hall Hall 3030 Jenk Jenk 3232 King King 3333 Land Land 3333 Mark Mark 3333

NuttNutt 3333