Organisasi Berkas Relatif

ORGANISASI BERKAS RELATIF

 

 

• Pengertian Berkas Relatif

 

·        Suatu berkas yang mengidentifikasikan record dengan key yang diperlukan.

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

 

• Proses

       Pada waktu sebuah record ditulis kedalam berkas relative. 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 relative harus disimpan didalam media SASD, seperti disk atau Drum. dimungkinkan untuk mengakses record-record dalam berkas relatif secara consecutive, tetati perlu diketahui bahwa nilai key tidak terurut secara logic.

 

Kemampuan Berkas Relatif

ü  Kemampuan mengakses record secara langsung.

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

 

Tiga teknik dasar fungsi Pemetaan R

1. Pemetaan langsung (Direct Mapping)
2. Pencarian Tabel (Directory Look-up)
3. Kalkulasi (Calculating)

 

 

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.

 

Pada teknik pencarian tabel kita harus menyediakan ruang memori untuk menyimpan tabel indexnya, tapi dalam teknik kalkulasi tidak diperlukan lagi hal itu. yang dilakukan adalah membuat hitungan sedemikian rupa sehingga dengan memasukkan kunci atribut recordnya, alamatnya sudah dapat diketahui, masalahnya bagaimana membuat hitungan dari kunci atribut itu sehingga hasilnya dapat lebih efisien dan tidak berbenturan dengan nilainya.

 

Ø  Cara mengatasi benturan, antara lain :

v  Scatter diagram techniques

v  Randomizing techniques

v  Key to address transformation methods

v  Direct addressing techniques

v  Hash tables methods

v  Hashing

 

Ø  Scatter DiagramTechnique

 

Sebuah metode baru untuk memasukkan dan mengambil informasi yang digambarkan dalam tabel hash. Metode ini bakal menjadi efisien jika lebih banyak bagian yang sering dilihat . Jumlah yang diharapkan dari kemungkinan untuk mencari entri, diperkirakan secara teoritis dan diverifikasi oleh percobaan Monte Carlo, adalah kurang dari untuk metode sebanding lain jika tabel hampir penuh.

 

Ø  Randomizing Teqhnique

 

Sebuah metode yang digunakan untuk pengambilan data dan informasi secara random (acak).

Ø  Key-To-Address Tranformation Methods

 

Teknik yang digunakan dalam teori mengkoreksi kesalahan kode. hal ini diterapkan untuk dapat menyelesaikan masalah dalam menangani file besar. dalam pendekatan baru, file menangani masalah yang digambarkan dengan desain khusus untuk menampilkan kelayakan.

 

Ø  Direct Addressing Technique

 

Semua instruksi lain yang diperlihatkan menggunakan pengalamatan langsung yang berarti, bahwa data yang telah direfensikan sebenarnay dan disimpan dalam struktur lain, baik sebuah register atau lokasi memori.

 

Ø  Hash Table Technique

 

Merupakan struktur yang menggunakan fungsi hash untuk efisien peta pengdentifikasi tertentu atau kunci/key (misalkan nama-nama orang) untuk dihubungkan nilai (misalkan nomor telepon mereka). funsi dari hash digunakan untuk mengubah kunci ke indeks (hash) dari array elemen (dalam slot/ember) dimana nilai yang sesuai akan dicari. dalam banyak situasi, hash table technique atau yang sering disebut teknik tabel hash ternyata lebih efisien daripada pohon pencarian atau struktur lookup. Biasanya banyak digunakan diberbagai jenis komputer perangkat lunak terutama untuk array asosiatif, pengideksan database, cache dan set.

 

Keuntungan menggunakan tenik tabel hash:

 

ü  Keuntungan utamanya dalah kecepatannya. keuntungan ini lebih jelas ketika jumlah entri yang besar (ribuan atau lebih). tabel hash dapat sangat efisien ketika jumlah maksimum entri dapat diprediksi dari sebelumnya, sehingga ember array dapat dialokasikan sekali dengan ukuran optimal dan tidak pernah diubah ukurannya.

ü  Jika himpunan pasangan kunci-nilai adalah tetap dan dikenal lebih dulu sehingga insersi serta penghapusan tidak diijinkan. yang dapat mengurangi biaya rata-rata lookup pilihan hati-hati dari fungsi hash, ember ukuran meja dan struktur data internal. Secara khusus, ada kemungkinan dapat menyusun fungsi hash yang tabrakan (bebas ) atau bahkan sempurna.

 

Kelemahan menggunakan teknik tabel hash:

 

ü  Untuk aplikasi pengolahan string tertentu, seperti spell-checking. tebel hash mungkin kurang efisien. jika setiap tombol diwakili oleh sejumlah kecil bit yang cukup, maka bukan sebuah tabel hash yang dapat menggunakan tombol langsung sebagai indeks ke array nilai.

ü  Meskipun rata-rata biaya per operasi adalah konstan dan cukup kecil dengan biaya operasi tunggal dapat cukup tinggi. secara khusus, jiak tabel hash menggunakan ukuran dinamis, penyisipan atau penghapusan operasi yang memerlukan waktu sebanding dengan jumlah entri. hal ini dapat dilkatakan kelemahan yang serius secara realtime atau interaktif.

 

ü  Tabel hash biasanya, dalam pameran umumnya miskin pemukiman referensi artinya data yang akan deakses didistribusikan tampaknya secara acak di memori. hal ini dikarenakan tabel hash menyebabkan pola akses berupa lompat-lompatm ini dapat memicu cache mikroprosesor yang menyebabkan penundaan yang lama.

 

ü  Tabel hash menjadi sangat tidak efisien bila ada banyak tabrakan.

 

 

Ø  Hashing

 

Hashing merupakan teknik mengindeks pada menajemen database dimana nilai kunci (yang mengindentifikasikan record) dimanipulasi secara numerik untuk menghitung langsung lokasi record yang berkaitan atau titik tolak untuk mencari record yang terkait.
Teknik mengindeks pada menajemen database dimana nilai kunci (yang mengindentifikasikan record) dimanipulasi secara numerik untuk menghitung langsung lokasi record yang berkaitan atau titik tolak untuk mencari record yang terkait.

 

Keuntungan Hashing :

ü Nilai key dapat digunakan langsung.

ü Nilai key adalah address space berubah.

Kelemahan Hashing :

      Membutuhkan waktu proses untuk implementasi dan mengatasi benturan.

 

Teknik Pemetaan Langsung

Dua cara Peetaan Langsung :

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

 

Untuk teknik pengalamatan mutlak ini kita tidak perlu mempermasalahkan kunci atribut karena kita diminta lansung menuliskan dimana alamat record yang akan kita masukkan . jika kita menggunakan hard disk atau macnetic drum, ada dua cara dalam menentukan alamat memorinya, yaitu:
• Cylinder Addressing
• Sector Addressing

Jika kita menggunakan Cylinder Addressing , maka kita harus menetapkan nomor-nomor dari silinder (Sylinder), permukaan (Surface), dan Record. Sedangkan bila kita menggunakan Secto Addresing, maka kita harus menetapkan nomor-nomor dari sektor (Sector), lintasan (Track), dan permukaan (Surface). teknik ini mudah dalam pemetaan (pemberian alamat memorinya).

 

Keuntungan :

1)      Fungsi Pemetaan R sangat sederhana.

2)      Retrieve lebih cepat.

Kelemahan :

1)                  Harus diketahui penyimapanan record secara fisik.

2)                  Nilai key tidak boleh hasil perhitungan.

3)                  Alamat mutlak adalah device independent.

4)                  Alamat mutlak adalah address space dependent.

 

2.    Pengalamatan Relatif (Relative Addressing) ;

R (Nilai key) à Address

Nilai key = alamat relatif.

Nilai key = urutan record tersebut dalam berkas.

Keuntungan :

1)      Fungsi Pemetaan R sangat sederhana.

2)      Penetuan nilai key tidak perlu waktu proses yang lama.

3)      Nilai key adalah Address Space Independent, dimana reorganisasi berkas tak akan mempengaruhi nilai key, yang berubah adalah alamat direktori.

 

Kelemahan :

1)      Alamat relatif adalah address space dependent.

2)      Terjadinya pemborosan ruangan.

3)      Directory Lookup (Pencarian Tabel)

-          Dalam pencarian tabel adalah sebuah table atau direktori dari nilai key dan address. Teknik ini dilakukan dengan cara, mengambil seluruh kunci atribut dan alamat memori yang ada dan dimasukkan ke dalam tabel tersendiri. jadi tabel misalnya disebut dengan tabel index hanya berisi kunci atribut misalkan NIM yang telah disorting/urut dan alamat memorinya. Sewaktu dilakukan pencarian data, tabel yang pertama dibaca adalah tabel yang diberi nama tabel index. setelah ditemukan atribur kuncinya, maka data alamat yang ada disana digunakan untuk meraih alamat record dari data(berkas,file atau tabel) yang sebenarnya. pencarian yang dilakukan di tabel index akan lebih cepat dilakukan dengan teknik pencarian melaui binary search daripada dilakukan dengan cara sequential.

Contoh :

      4 digit untuk jenis barang (9999).

      Padahal hanya ada 2000 jenis barang.

      Pemborosan 80% ruang penyimpanan.

 

 

Tujuan Utama Hashing :

Agar dua buah kunci yang berbeda tidak mempunyai nilai relative address yang sama.

 

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.

 

 

Pendekatan masalah Collision :

Open Addressing ;

Menemukan address yang bukan home address untuk K2.

Separate Overflow ;

Menemukan address untuuk K2 di luar primary area yakni di overflow area.

 

Teknik Mengatasi Collision :

1. Linier Probing (Pendekatan Open Addressing) ;

Proses pencarian secara sequential dari home address sampai lokasi yang kosong.

Harus ada penentuan apakah address kosong.

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

 

Perbandingan kedua teknik :

Linier Probing	Double hashing
* menghasilkan synonim berkelompok * cocok untuk faktor muat rendah	* menghasilkan synonim berpencar * cocok untuk faktor muat tinggi

 

Fungsi hash yang umum digunakan :

1. Division Remainder
2. Mid Square
3. Folding

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 < 20)

 

            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

 

Mid Square

·        R (Nilai key) à Address

Nilai key dikuadratkan kemudian beberapa digit diambil dari tengah. Alamt relatif, diambil mulai dari digit .........

                  ∑ digit dari nilai key kuadrat

                                          2

·        Contoh untuk berkas 4000 record, dibutuhkan 4 digit.

Nilai Key                          Nilai Key Kuadrat                  Relatif Address

      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

 

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

 

 

Synonim Chaining (Penggandengan)

·        Menggabung synonim bersama-sama.

·        Tidak mengurangi jumlah collision tetapi mengurangi waktu akses untuk meretrieve.

 

Bucket Addressing

Hash ke dalam blok yang memberikan tempat bagi sejumlah record.

 

Contoh :

      Reltatif address space          0 – m

      Bucket berukuran               B record

      File terdiri dari                    N record

 

v  Faktor muat =     N

             

                  B (m + 1)

 

Contoh linier probing

rekaman	A	B	C	K	P	Q	R	Y	Z
nilai key	5	6	7	5	0	1	2	9	0

 

rekaman	P	Q	R	Z	-	A	B	C	K	Y
nilai key	0	1	2	3	4	5	6	7	8	9

 

Contoh Chaining

Rekaman

          34       56      123     78     93    70      100     21     11    77     28

 

Fungsi Hash

          K  mod  10

 

Alamat relatif