MAKALAH ORGANISASI BERKAS RELATIF

BAB I

PENDAHULUAN

1.      Pengertian 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.

Urutan record secara logika tidak ada hubungannya dengan urutan secara fisik karena record sendiri tidak perlu tersortir secara fisik menurut nilai key.

Contoh :

Direct Organisasi

8

7

5

4

2

                                                                                                                                               

                                                                                   

                                   Input Record                                                                   

                                                                         

                                                                                          

                                                                               

                                                                               

File Load Program

                                                                 

 

Direct File

	2		4	5		7	8
1	2	3	4	5	6	7	8	9

Gambar  1 :  Organisasi Berkas Relatif

Bagaimana record yang ke-N dapat ditemukan ?? .  Dalam hal ini perlu kita buat hubungan yang akan menerjemahkan antara NILAI KEY dan ADDRESS.

Hubungan ini dinyatakan sebagai R, yang merupakan fungsi pemetaan.

R (NILAI KEY)                     ADDRESS

Dari nilai key ke address dalam penyimpanan sekunder.

Prosesnya :

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.

Organisasi berkas relatif ini tidak menguntungkan bila penyimpanan sekundernya berupa media SASD seperti magnetic tape.  Berkas relatif harus disimpan dalam media DASD (Direct Access Storage Device) seperti magnetic disk atau drum.  Juga dimungkinkan untuk mengakses record-record dalam berkas relatif secara consecutive, tetapi perlu diketahui bahwa nilai key tidak terurut secara logika.

Contoh :

    Key Value                       Physical position

1

2

I – 1

I

I + 1

N – 1

N

Cow
Zebra
- - -
Ape
Eel
Dog
- - -
Cat
Bat

  Beginning of file à

           

End of File à

                                                                                                Figure I3-1 Basic

Organisasi Berkas Relatif

Record dalam gambar,  diretrieve secara consecutive;

COW, ZEBRA, … , APE, EEL, DOG, … , CAT, BAT

Karena kemampuan mengakses record tertentu secara cepat, maka organisasi berkas relatif paling sering digunakan dalam proses interactive.

Adapun Kemampuan dari Organisasi Berkas Relatif :

1.      Bisa mengakses record secara langsung.

2.      Record dapat di retrieve, insert, modifikasi dan delete tanpa mempengaruhi record – record lain dalam berkas yang sama.

BAB II

PEMBAHASAN

1.      Pendekatan Terhadap Masalah Collision

Ada 2 pendekatan dasar untuk menetapkan dimana K2 harus disimpan, yaitu :

1.      Open Addressing

2.      Separate Overflow

v  Open Addressing

Menemukan address yang bukan home address untuk  K2  dalam berkas relatif.

Contoh :

K1 = 1      K2 = 1

R1      R2

K1

K2

                        

                

v  Separate Overflow

Menemukan address untuk K2 diluar dari primary area  dalam  berkas relatif, yaitu di overflow area yang dipakai hanya untuk menyimpan record-record yang tidak dapat disimpan di home addressnya.

Contoh :

  

                                                            K1 = 1          K2 = 1

                                                            R1

K1

Overflow area

K2

                   

Teknik Untuk Mengatasi Collision Linier Probing Dan Double Hashing

1.      Linier Probing, yang merupakan teknik open addresing.

2.      Double Hashing, yang dapat dipakai selain open addressing atau separate overflow.

v  Linear Probing

Salah satu cara menemukan lokasi record yang tidak dapat disimpan di home addressnya adalah dengan  menggunakan  Linear  Probing,  yang merupakan sebuah proses pencarian  secara  sequential/linear dari home addressnya sampai lokasi yang kosong.

v  Double hashing

Pendekatan lain dalam menemukan lokasi sebuah record pada waktu record tersebut tidak dapat disimpan dalam home addressnya adalah dengan menggunakan Double Hashing, yang akan memakai  fungsi  hash kedua terhadap hasil dari fungsi hash pertama. Address dari  record  yang  dihash  kembali  dapat  terletak  pada primary area atau di separate overflow area.

Keuntungan  dari  metode  separate  overflow  adalah   menghindari keadaan dimana dapat terjadi metode open addressing  untuk  sebuah record yang tak disimpan dalam home addressnya menggantikan  record lain yang terakhir di hash ke home addressnya.

Masalah ini  dapat  dihindari  dengan  open  addressing  sederhana dengan memindahkan record yang sebelumnya ke lokasi lain dengan probing atau hashing  kembali dan  menyimpan  record  yang  baru ketempat yang kosong. Metode ini membutuhkan  pengeluaran  tambahan  untuk  pemeliharaan dalam suatu berkas.

Berkas relatif dibagi menjadi 2 berkas , yaitu :          

1.      Primary area

2.      Overflow area

Perbandingan Linear Probing dan Double Hashing

Berkas dengan load factor kurang dari 0.5 pada linear probing akan menghasilkan synonim yang mengelompok,  sedangkan  double  hashing synonimnya berpencar.

Load Factor < 0.5  :  Double Hashing  =  Linear Probing.

Load Factor > 0.8  :  Double Hashing  >  Linear Probing.

2.   Synonim Chaining

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

Contoh :

Key	Home Address	Actual Address
Adams	20	20
Bates	21	21
Coll	20	22
Dean	21	23
Evans	24	24
Flint	20	25

                         R20              R21              R22             R23            R24            R25

Adams

Bates

Coll

Dean

Evans

Flint

Gambar 2 : Hashing Dengan Synonim Chaining

Home Address	Primary Data Area	Area	Overflow Area
20	Adams	0	Coll
21	Bates	1	Dean
22		2	Flint
23		3
24	Evans

3.      Bucket Addressing

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

Contoh :

Sebuah berkas relatif  mempunyai  relatif  address  space  dari  0 sampai M dan sebuah bucket berukuran B record , address space akan terdiri dari B(M+1) record.  Jika file terdiri dari N record, maka :     

                                                     Factor Muat        =              

B record dapat semuanya di hash kedalam relatif address yang  sama tanpa menyebabkan collision.

Pada  saat  sebuah  bucket  penuh,  beberapa  tempat  baru   harus ditemukan untuk record record tersebut. Pendekatan  dari  masalah  bucket penuh  pada  dasarnya  sama  dengan  pendekatan  untuk   mengatasi collision dengan record addressing. Jika open addressing dipakai, space dicari untuk bucket berikutnya misalkan dengan linear probing atau dalam  bucket  lainnya  misal dengan double hashing. Jika  teknik  separate  overflow   yang   dipakai,   record   baru ditempatkan dalam suatu  himpunan  bucket  yang  dirancang  khusus untuk tempat record yang tidak dapat ditampung pada bucket primer. Bucket ini disebut bucket overflow.

Record-record yang disimpan dalam  sebuah  bucket  dapat  dikelola dalam :

1.      Dapat  disisipkan  dalam  urutan  berdasarkan  penempatannya  di bucket.

2.      Dapat dipertahankan urutan nilai key-nya.

Bucket addressing ini umum dipakai, Ukuran dari sebuah bucket dapat ditentukan oleh ukuran track  atau sektor dalam DASD. Ukuran bucket umumnya sama dengan ukuran block untuk file. Satu  keuntungan  penting  dari  penggunaan  bucket   yang   dapat menampung banyak record - record  dengan  panjang  yang berbeda dapat kita pakai.

Contoh :

Key	Home Address
Green	30
Hall	30
Jenk	32
King	33
Land	33
Mark	33
Nutt	33

Bucket Address	Bucket Contents
30	Green	Hall
31
32	Jenk
33	King	Land	Mark

   Overflow

Nut

BAB III

PENUTUP

1.      Kesimpulan

Suatu cara yang efektif dalam mengorganisasi sekumpulan record yang membutuhkan akses sebuah record dengan cepat disebut organisasi berkas relatif. Organisasi berkas relatif paling sering digunakan dalam proses interakti Tidak perlu mengakses record secara berurutan (consecutive).

2.      Saran

Semoga dengan adanya tugas ini kami harapkan kepada rekan rekan mahasiswa/i sekalian khususnya kami, sudah memahami tentang organisasi berkas relatif serta dapat menerapkan ilmu yang sudah kami dapat dalam kehidupan sehari hari terutama dalam dunia belajar.

DAFTAR PUSTAKA

http://www.joule37.co.cc/2009/04/organisasi-berkas-teknik-atau-cara.html
http://one.indoskripsi.com/judul-skripsi-makalah-tentang/organisasi-berkas
http://webdosen.bl.ac.id/dosen/010015/download/sistem_basis_data_1.pdf

http://www.scribd.com/doc/33014517/sistem-berkas

• Tweet
• Share
• Share
• Share
• Share

About Admin MC3

This is dummy text. It is not meant to be read. Accordingly, it is difficult to figure out when to end it. But then, this is dummy text. It is not meant to be read. Period.

Related Post