Pembahasan makalah Sistem berkas

BAB II

PEMBAHASAN

A.        Organisasi Berkas Relatif

            1. Pengertian Berkas Relatif

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

            2. Proses Berkas Relatif

Pada waktu sebuah record ditulis kedalam berkas relatif, fungsi pemetaan R digunakan untuk meterjemahkan NILAI KEY dari record menjadi ADDRESS, dimana record tersebut disimpan. Berkas relatif disimpan dalam media DASD(Direct Access Storage Device) seperti magnetic disk.

A.      Teknik Dasar Fungsi Pemetaaan R

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

1.    Teknik Pemetaan Langsung (Direct Mapping)

Ada 2 cara dalam pemetaan langsung, yaitu :

Ø  Pengalamatan Mutlak

R(NILAI KEY         ADDRESS

NILAI KEY = ALAMAT MUTLAK

Pengalamatan mutlak ini memiliki kelebihan dan kekurangannya.

Ø  Pengalamatan Relatif

R(NILAI KEY         ADDRESS

NILAI KEY = ALAMAT MUTLAK

Pengalamatan relatif ini memiliki kelebihan dan kekurangannya.

2.    Teknik Pencarian Tabel (Directory Look Up)

3.    Teknik Kalkulasi (Calculation)

Keadaan dimana :

R(K1) = R(K2) Disebut benturan atau Collision.

Ada 6 cara  untuk mengatasi benturan antara lain :

-       Scatter Strage Techniques

-       Randomizing Technigques

-       Key-to-address transformation methods

-       Direc addressing Techniques

-       Hash Table Methods

-       Hashing.

B.       Hashing  

       Teknik yang fungsinya untuk menentukan lokais record pada file data dengan melakukan perhitungan pada nilai key dari record tersebut.

Ada 5 fungsi hashing yang umum digunakan yaitu :

1.      Sisa Pembagian (Division-Remainder)

Dalam teknik ini membagi nilai key dengan ukuran tabel. Alamat tempat penyimpanan record didapat dari sisa pembagian + 1.

            Contoh :

            Asumsikan ukuran tabel = 11 dan satu file dengan 8 record menggunakan nilai key sebagai berikut : 12,21,68,38,52,70,44,18.

Maka :

(12 mod 11) + 1 = 1 + 1 = 2; simpan 12 di lokasi 2

(21 mod 11 ) + 1 = 10 + 1 = 11; simpan 21 d lokasi 11

(68 mod 11) + 1 = 2 + 1 = 3; simpan 68 di lokasi 3

(38 mod 11) + 1 = 5 + 1 = 6; simpan 38 di lokasi 6

(52 mod 11) + 1 = 9 + 1 = 10; simpan 52 di lokasi 10

(70 mod 11) + 1 = 4 + 1 = 5; simpan 70 di lokasi 5

(44 mod 11) + 1 = 0 + 1 = 1; simpan 44 di lokasi 1

(18 mod 11) + 1 = 7 + 1 = 8; simpan 18 di lokasi 8

Sehingga :

Alamat             1      2      3    4     5     6     7    8     9    10   11

Nilai kunci       44    12    68   –   70    38   –    18    –    52   21

2.      Pemenggalan (Truncation)

Dalam teknik ini melakukan penghilangan digit k yang pertama atau terakhir dari sejumlah n digit.

Hasil dari pemenggalan merupakan alamat relatif dimana kunci

Contoh 1 :

Jika nilai kunci menghapus 6 digit terakhir dari 9 digit nomor sebagai berikut:

(123456789) = 123; simpan 123456789 di lokasi 123

(222345654) = 222; simpan 222345654 di lokasi 222

(301657434) = 301; simpan 301657434 di lokasi 301

(123882345) = 123; simpan 123882345 d ilokasi 123

Pemenggalan di atas mengakibatkan terjadinya tubrukan (kolisi) pada lokasi penyimpanan, maka pemenggalan dilakukan dengan melihat nomor kunci yang diberikan supaya tidak terjadinya kolisi.

Maka dilakukan pemenggalan menghapus 6 digit awal nomor kunci, sehingga :

(123456789) = 789; simpan 123456789 di lokasi 789

(222345654) = 654; simpan 222345654 di lokasi 654

(301657434) = 434; simpan 301657434 di lokasi 434

(123882345) = 345; simpan 123882345 di  lokasi 345

3.      Lipatan (Folding)

Dalam teknik ini nilai key dibagi (dilipat) menjadi beberapa bagian. Masing-masing bagian memiliki jumlah digit yang sama, dimana nilai kunci pada bagian terakhir di balik dari sebelah kanan. Lokasi penyimpanan merupakan hasil dari penjumlahan.

Contoh :

Diberikan nilai kunci 123456, 234351, 222456. Nilai kunci dibagi menjadi 2 bagian setiap 3 digit. Bagian terakhir nilai kuncinya dibalik dari sebelah kanan.

Maka :

123 + 654 = 777; simpan 123456 dilokasi 777

234 + 153 = 387; simpan 234351 dilokasi 387

222 + 654 = 876; simpan 222456 dilokasi 876

4.      Perkalian (Multiplication)

Teknik ini dilakukan dengan cara membagi-bagi satu kunci dan bagian dari salah satu kunci bisa dipilih untuk kemudian dikalikan. Hasilnya merupakan alamat relatif dari record yang akan dilokasikan dimana kunci tersebut akan disimpan.

Contoh :

Nomor identitas pegawai digunakan sebagai kunci.

Kalikan 3 digit yang pertama dengan 3 digit yang terakhir dari kunci.

Diberikan nomor identitas pegawai = 123456789

3 digit yang pertama = 123

3 digit yang terakhir = 789

(123456789)= 123 * 789 = 97047

Penggal hasil perkalian pada digit yang terakhir sehingga menjadi 9704, jadi nomor identitas pegawai 123456789 disimpan dilokasi 9704.

5.       Pengkuadratan (Mid-Square)

Dalam teknik ini nilai kuncinya dikuadratkan, kemudian menentukan digit yang akan dikutip dari tengah, hasilnya merupakan alamat relatif. Jika alamat relatif yang dinginkan sejumlah n digit, maka digit dipenggal atau dihilangkan diantara kedua ujung hasil pengkuadratan nilai kunci, menyisakan n digit dari tengah. 

            Contoh :

Pada contoh dibawah ini, digit ke-7 samapi 10 (dihitung dari kanan), diambil untuk mendapatkan 4 digit sebagai alamat relatif.

    Nilai kunci        Nilai kunci dikuadratkan       Alamat relatif

    123456789             15241578750190521                  8750

     123456790             15241578997104100                  8997

     345237459           119188903096777000                  3096

     987654321           975461055789911041                  5789