Organisasi Berkas Langsung

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.

Dalam hal ini akan dibahas berbagai teknik yang dapat digunakan sebagai alternatif dalam merancang system. Khususnya dalam menentukan lokasi rekaman yang akan disimpan serta pembacaan rekaman tersebut.

Hal tersebut hanya mungkin terjadi bila bila kunci rekaman juga merupakan alamat lokasi rekaman. Dengan demikian waktu pencarian akan sangat baik, yaitu 1 probe untuk setiap rekaman yang dicari. Harus dimengerti harus tersedia 1 lokasi untuk setiap kemungkinan kunci rekaman.

Cara Untuk mengorganisasi berkas untuk pengaksesan langsung, yaitu :

1. Kunci Sebagai Alamat Rekaman Yang Unik

Untuk mendapatkan rekaman yang diasosiasikan dengan suatu kunci primer, sangat diharapkan agar proses langsung menuju ke alamat tempat rekaman dengan kunci tertentu disimpan. Hal tersebut hanya mungkin terjadi apabila kunci rekaman juga merupakan alamat lokasi rekaman. Untuk suatu aplikasi dengan rekaman berisi informasi mahasiswa, untuk tigabelas digit nomor identitas mahasiswa (atau kunci utama rekaman yang merupakan gabungan dari 4 digit kode fakultas + jurusan, 4 digit tahun angkatan + 5 digit nomor urut), maka diperlukan 9.000.000.000.000 lokasi sebagaimana diperlihatkan pada gambar dibawah ini.

 

  Dengan demikian waktu pencarian akan sangat baik, yaitu probe 1 untuk setiap rekaman yang dicari. Namun teknik tersebut memiliki kerugian, karena diperlukan ruang yang sangat besar untuk menampung semua rekaman. Namun, pasti ada beberapa nomor yang kosong karena beberapa alasan, misalnya sudah lulus, mengundurkan diri, drop-out, cuti, dan sebagainya. Sehingga tidak semua ruang dimanfaatkan.

2. Konversi kunci rekaman menjadi satu alamat yang unik

Dilakukan untuk mengantisipasi kerugian dengan korespondensi 1-1. Terdapat beberapa formula, beberapa diantaranya.

Contoh Sistem reservasi penerbangan. Jika suatu maskapai penerbangan memiliki nomor penerbangan dari 1 sampai 999, ingin memantau reservasi pesawat selama setahun yang jumlah harinya 1 sampai 366 (1 tahun), maka nomor penerbangan dan hari-ke dapat dihubungkan untuk mendapatkan lokasi rekaman yang berisi data reservasi penerbangan pada hari tertentu.

  

Dengan simbol + menandakan hubungan, maka untuk menyediakan semua kemungkinan penerbangan diperlukan ruang alamat sebesar 999366 unit. Jumlah tersebut dapat direduksi sampai dengan 30% bila digunakan kombinasi.

 

Karena kecil kemungkinan dalam satu maskapai terdapat lebih dari 100 penerbangan, maka ruang alamat maksimum yang diperlukan adalah 36699.

3. Menentukan alamat dengan konversi kunci

Karena tidak sebanding antara kunci yang aktual dengan jumlah ruang kunci yang harus disediakan, maka korespondensi 1-1 tidak efisien. Jika ruang-ruang kosong bisa dieliminasi, maka akan diperoleh ruang kunci yang lebih besar dibanding ruang alamat.

Sebagai konsekuensinya, diperlukan suatu fungsi untuk memetakan cakupan nilai kunci yang lebih luas ke dalam cakupan yang lebih sempit nilai alamat. Fungsi ini dikenal dengan fungsi hash. Berikut ini adalah beberapa fungsi hash.

a)      Hashing dengan kunci modulus N

Home address dicari dengan cara mencari sisa hasil bagi nilai kunci dengan suatu nilai tertentu.

      f(kunci) = kunci mod N

Dengan nilai N dapat berupa 2 kemungkinan, yaitu :

–        Banyaknya ruang alamat yang tersedia

–        Bilangan prima terdekat yang berada di atas nilai banyaknya data, setelah itu banyaknya ruang alamat disesuaikan dengan N.

contoh soal :

                 N = 12 maka :

                 f(30) = 30 mod 12

                          = 5

Keuntungan fungsi ini adalah hanya menghasilkan nilai dalam rentang ruang alamat (0) sampai dengan (N-1).

b)     Hashing dengan kunci modulus P

Fungsi hashing kunci mod P merupakan variasi fungsi kunci modulus N, rumusnya adalah :

  f(kunci)  =  kunci mod P

dengan P sebagai bilangan prima terkecil yang lebih besar atau sama dengan N, dan N adalah ukuran tabel. P ini kemudian menjadi ukuran tabel baru yang menggantikan N.

Contoh soal :

                 N = 12;   P=13

30 mod P = 4, diperoleh dari 30 dibagi 13 menghasilkan 2 dan menghasilkan sisa 4.

c)      Hashing dengan pemotongan

Home address dicari dengan memotong nilai kunci ke jumlah digit tertentu yang lebih pendek.

Contoh soal :

Nilai NIP yang tadinya 9 digit dipotong menjadi hanya 3 digit dengan mengambil 3 nomor terakhir. Misalnya : NIP 132312090 akan memiliki home address 090 atau 90

d)     Hashing dengan Lipatan

Fungsi ini akan melipat digit pada batasan yang ditentukan berdasarkan kondisi digit awal dan digit yang akan dihasilkan.

Contoh soal :

Nilai NIP yang 9 digit dibagi ke dalam 3 bagian masing-masing 3 digit, terus dilipat pada bagian-bagian tersebut. NIP 132312090.

 

                                        

Penjumlahan dari susunan tersebut :

2 3 1

3 1 2

0 9 0

yang dijumlahkan dan menghasilkan 633 (dengan carrier tidak diabaikan) atau 533 (mengabaikan carrier).

a)      Hashing dengan pergeseran

Hashing dengan pergeseran memiliki proses yang serupa dengan hashing dengan lipatan, perbedaannya setelah ditentukan batasan, digit asli dipotong kemudian digeser dan dihitung hasil jumlahnya.

Contoh soal :

Untuk kunci yang memiliki 9 digit.

                                            

5 8 3

9 7 6

                     1 2 4

 

Yang akan menghasilkan alamat yang berbeda yaitu 572 (tanpa carry). Jika kedua hasil penjumlahan diatas diterapkan dengan menggunakan carry dan hanya tiga digit yang paling kanan saja yang digunakan maka diperoleh (1)782 dan (1)683.

a)      Hashing dengan pengkuadratan

Home address dicari dengan mengkuadratkan setiap digit pembentuk kunci, lalu semua hasilnya dijumlahkan.

Contoh soal :

NIP 132312090

memiliki home address = 1²+3²+2²+3²+1²+2²+0²+9²+0²

 = 1+9+4+9+1+4+0+81+0

 = 104

b)     Hashing dengan Konversi Radix

Dalam konversi radix, kunci dianggap dalam base selain 10 yang kemudian dikonversi ke dalam basis 10, misalnya kunci  5 6 7 8 dalam base 13 akan menghasilkan 12098 yang diperoleh dari :

   Posisi : 3          2          1          0

               5          6          7          8

(5 x 13³) + (6 x 13²) + (7 x 13¹) + (8 x 13⁰) = 10985 + 1014 + 91 + 8

Sehingga hasilnya 12098 ketika dikonversi ke basis 10. Hasil tersebut masih dapat dikombinasi dengan fungsi hash lain (pemotongan atau lipatan) untuk mendapatkan digit alamat yang diijinkan.