MANAJEMEN KOLISI & COLLISION RESOLUTION

* Kriteria Fungsi Hash Yang Baik

• Dapat mendistribusikan setiap rekaman secara merata, sehingga dapat meminimalkan terjadinya collision (tabrakan)
• Dapat dieksekusi secara efisien, sehingga waktu tidak habis hanya untuk menghitung home address saja

Collision (Tabrakan)

• Dengan menggunakan metode hashing, maka secara otomatis hubungan korespondensi satu-satu antara kunci rekaman dengan alamat rekaman menjadi hilang
• Selalu ada kemungkinan terjadinya peristiwa dimana terdapat dua buah kunci yang berbeda namun memiliki home address yang sama
• Kejadi seperti ini dinamakan Collision atau Tabrakan atau Tumbukan

Manajemen Kolisi

• Semakin sedikit jumlah kolisi, maka makin baik bagi fungsi hashing tersebut, karena makin sedikit jumlah waktu yang diperlukan untuk melihat tempat yang berbeda dalam menemukan rekaman yang diinginkan.
• Beberapa cara untuk mengantisipasi kolisi adalah dengan mengganti fungsi hashing, atau mengkombinasikan faktor packing. 
• Faktor packing suatu berkas adalah perbandingan (rasio) antara jumlah rekaman yang disimpan dalam berkas dengan kapasitas berkas, atau dapat dinyatakan sbb :

                         Factor Packing = Jumlah Rekaman Yang Disimpan

          Jumlah Total Lokasi Penyimpanan

Resolusi Kolisi

• Yang menjadi tujuan utama metode resolusi adalah menempatkan rekaman synonim pada suatu lokasi yang membutuhkan probes tambahan yang minimum pada home address rekaman tersebut.
• Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama
• Salah satu penyelesaian yang dapat dilakukan adalah dengan memberikan petunjuk pada lokasi rekaman sinonim
• 
  
• Karena collision dapat di pastikan akan selalu terjadi, maka dapat dikatan bahwa output dari fungsi hash (home-address) bukanlah merupakan alat yang unik yang pasti ditempati oleh rekaman yang diproses, namun hanya berupa kemungkinan alamat yang bisa ditempati
• Jika home-addrees dari suatu rekaman ternyata sudah ditempati rekaman lain, maka harus di carikan alamat lain untuk ditempati oleh rekaman tersebut
• Proses pencarian alamat lain ini dinamakan sebagai Collision Resolution
• Berikut beberapa Metode Untuk Mengatasi Kolisi / Tubrukan ->;

* Metode Open Addressing

• Alamat alternatif dicari pada alamat-alamat selanjutnya yang masih kosong, salah satu nya dengan cara Linier Probing
• Linier Probing
• Pencarian dilakukan dengan jararak pencarian yang fix (tetap), biasanya satu-satu
• 
  
• Linier Probing Contoh :
• Sesuai dengan namanya jika lokasi yang telah ditempati telah terisi, maka dilihat lokasi selanjutnya apakah masih belum terisi
• Fungsi Hash yang dipakai adalah :

             f(key) = key mod 10

• Ruang alamat yang tersedia : 10 alamat
• Metode collision resolution yang dipakai adalah open addressing dengan linier probing jarak 3

Urutan kunci yang masuk adalah 20, 31, 33, 40, 10, 12, 30, dan 15 

Jawaban Linier Probing

* Metode Coalesced Hashing

• Bila terjadi tumbukan dalam pemasukan kunci rekaman maka dapat dicari alamat yang paling besar / paling akhir
• Contoh : misalkan akan dilakukan penyisipan rekaman-rekaman dengan kunci 38, 51, 40, 61, 83, 24, dan 60
• Langkah 1 lakukan proses hashing semua kunci dengan kunci modulus 11 (11 adalah kapasitas berkas), maka dihasilkan :

Pile File

Pengertian Pile File

Pile file merupakan organisasi file yang strukturnya sangat sederhana dan jarang sekali digunakan dalam pengolahan data elektronik. Pile fie digunakan sebagai pembanding dalam mengevaluasi organisasi file lainnya yang strukturnya lebih baik. 

Data - data disusun berdasarkan urutan datangnya / masuknya data ke dalam file. Data - data yg masuk tidak dianalisa, dipilah-pilah atau dikategorikan mengikuti aturan panjang field.

Karakteristik Pile File

1. Penyusunan urutan record-recordnya, dilakukan berdasarkan kronologis masuknya data
2. Panjang setiap field & recordnya bervariasi
3. Elemen data yg disimpan pd masing-masing record kemungkinan bervariasi
4. Bentuk / struktur organisasinya sederhana
5. Data / informasi yg masuk ke dlm file, disimpan tanpa diproses terlebih dulu
6. Pembentukan Pile File dpt dilakukan dgn mudah & cepat
7. Pencarian record data di dalam Pile File sangat sulit

Strukture dan Menipulasi

Struktur record pd pile file, harus terdiri dari elemen-elemen data yg saling berhub., dimana pd setiap elemen data diberikan Identitas, sehingga mempunyai Arti. Identitas dari elemen data tersebut, bisa berupa nama secara eksplisit, seperti : Umur, ataupun berupa kode , attribute.

Struktur di atas disebut : “ Self Describing Fields “. Cth : Umur = 40  ( Attribute_name, Value)

Attribute_name pd pile file dpt menjadi Complex-attribute, bila attribute tsb terbagi-bagi lagi dlm sejumlah attribute_name,  Value pairs.

Pencarian record-record pada pile file dilakukan dengan cara menentukan beberapa attribute di dlm search-argumentnya. Attribute-attribute yg ditulis pada search argument disebut  “Key Attribute“, sedangkan attribute-attribute lainnya disebut “Goal Data“. Key menentukan record-record yg akan dicari sedangkan Goal Data merupakan elemen-elemen data.

Pengunaan Pile File

Pile File merupakan struktur dasar dan tidak terstruktur.

Penggunaannya dapat digunakan pada:

1. File-file system
2. File Log (mencatat kegiatan)
3. File-file Penelitian / medis
4. File teks
5.  config.sys

Performance Dari Pile File

      
      1. Record Size (R)
      File density dari pile file dipengaruhi oleh 2 faktor, yaitu :

1. Kebutuhan utk menyimpan attribute_name bersama-sama dengan datanya.
2. Data yang tidak dibutuhkan / data yangg tidak ada tidak perlu disiapkan (disediakan tempat / lokasinya)

                                                R= a’ (A+V+2)

                        dimana:

                        a’         =          Rata2x jumlah field pada satu rekord

                        A         =          Panjang rata2x nama (deskripsi)atribut

                        V         =          Panjang rata2x nilai atributSeparator untuk pemisah antar field dan

                                                antar rekord

                   

Berdasarkan kedua faktor di atas, maka :

1. Bila data yang disimpan heterogen maka pile file menjadi High Density
2. Bila banyak terdapat kerangkapan / duplikasi : attribute_name; maka pile file menjadi “ Low Density “

         2. Fetch Record (T_F)
     Waktu yg dibutuhkan utk menemukan lokasi sebuah record sangat lama. Hal ini disebabkan karena semua record harus ditelusuri utk mencari elemen yg menjadi Key-attribute.

         3. Get Next Record (T_N)

         Record-record tdk disusun berdasarkan urutan tertentu, maka record berikutnya yg akan diakses bisa berada dimana saja.

         4. Insert Record (T_I)

         Menyisipkan sebuah record baru dpt dilakukan dgn cepat dan mudah, hal ini disebabkan karena  pd pile file tdk terdpt struktur record maupun urutan penyusunan record.

         5. Update Record(T_U)

              a. Mencari lokasi yg akan diupdate

              b. Merubah status record lama menjadi invalid

              c. Kemudian tulis record baru pd akhir file

         6. Read entire (T_X)

             Proses membaca seluruh record pada pile, dilakukan dgn cara membaca record dari awal                      sampai akhir pile.

         7. Reorganization (T_Y)

             Record-record yg sudah di update / didelete memiliki Tombstone Mark yg menyatakan                        record tsb sudah tdk valid lagi.

             

             Kemudian record-record invalid yg sudah tdk dibutuhkan tsb secara periodik dihilangkan dgn              cara, mengcopy pile file yg lama menjadi pile file yg baru. Dimana record yg invalid tdk                      dicopy.

TUGAS PENYISIPAN NILAI SESUAI DENGAN NIM

Berkas Sekuensial Berindeks

Sistem Berkas Sekuensial Berindeks

Berkas Sekuensial berindeks dirancang dengan tujuan untuk menanggulangi permasalahan pengaksesan yang dimiliki oleh organisasi berkas sekuensial tanpa mengurangi keuntungan dan tradisi yang dimiliki oleh berkas sekuensial.

1. Keunggulan sifat berkas sekuensial Berindeks :Indeks terhadap berkas sehingga menghasilkan pengaksesan random yang lebih baik
2. Area overflow untuk menyediakan ruang bila dilakukan penambahan rekaman kedalam berkas.

Komponen Dalam berkas Sekuesial Berindeks

Struktur Dasar

Pada sistem komputer, pada umumnya rekaman yang disimpan memiliki volume yang terlalu besar untuk ditempatkan semuanya pada penyimpanan primer, sehingga diperlukan adalanya media penyimpanan sekunder seperti disk untuk menyimpan rekaman. Bila yang digunakan adalah komputer dengan disk yang dapat diberi alamat melalui bloknya, maka digunakan track sebagai unit terkecil dalam mengelompokan informasi. Unit selanjutnya adalah slinder, dan kemudian unit lainnya disebut indeks.

Sebagai contoh adalah berkas sekuensial berindeks dengan format blok yang dapat diberi alamat. Untuk memperjelas pemahaman dipilih rekaman-rekaman dalam sebuah silinder tetapi indeks silinder tersebut berisi petunjuk ke berbagai silinder lainnya.

Sepasang masukan yang berisi informasi untuk masing-masing silinder dalam indeks silinder adalah sebagai berikut :

Kunci merupakan kunci rekaman tertinggi dari rekaman-rekaman yang berada pada slinder tersebut dan penunjuk merupakan penunjuk yang mengarah pada indeks track untuk silinder tersebut.

Satu pasang berisi informasi yang berada pada area penyimpanan primer dan sebuah lagi memiliki informasi pada rekaman overflow yang diasosiasikan dengan track tresebut. Untuk masing-masing track masukan-masukan tersebut memiliki bentuk sebagai berikut :

Kunci pada pasangan pertama menunjukan kunci tertinggi pada track yang berada pada area penyimpanan primer, dan kunci yang berada padfa pasangan kedua menunjukan kunci tertinggi yang berada pada overflow yang diasosiasikan pada track tersebut.

Penunjuk primer memberikan indikasi bahwa track berisi rekaman primer dan penunjuk overflow menunjukan rekaman pertama yang berada pada area overflow (jika ada) yang diasosiasikan dengan track tersebut.

Contoh Struktur Awal Berkas Sekuensial Berindeks

 Menyisipkan Rekaman

1. Sisipkan rekaman dengan kunci 13 pada berkas

• data berkas awal yang harus kita sisipkan dengan kunci 13                 

• kunci 13 adalah kunci yang lebih kecil dari 25, dimana pada penyimpanan primer yang lebih kecil dari 25 terlihat pada peyimpanan primer pertama. Maka kunci 13 kita sisipkan pada penyimpanan primer pertama. Sehingga kunci yang paling besar pada penyimpana berubah menjadi 22 dan 25 pindah ke kotak overflow.

2. Sisipkan rekaman dengan kunci 27 pada berkas

• data berkas awal yang harus kita sisipkan dengan kunci 27

• kunci 26 adalah kunci yang lebih kecil dari 70 dan lebih besar dari 22, dimana pada penyimpanan primer yang lebih kecil dari 70 dan lebih besar dari 22 terlihat pada peyimpanan primer kedua. Maka kunci 13 kita sisipkan pada penyimpanan primer kedua. Sehingga kunci yang paling besar pada penyimpana berubah menjadi 65 dan 70 pindah ke kotak overflow yang ke dua.

Menghapus Rekaman

1. Menghapus rekaman dengan kunci 15

• data berkas awal yang harus kita hapus kunci 15, 

         

• karena kunci 15 teretak pada peyimpanan primer maka langsung dihapus dari penyimpanan dan di ganti dengan simbol *.

2. Menghapus Rekaman dengan kunci 65

                                             

Kesimpulan

Berkas sekuensial berindeks bertujuan untuk menanggulangi permasalahan pengaksesan yang dimiliki oleh organisasi berkas sekuensial tanpa mengurangi kelebihan dan tradisi yang dimiliki berkas sekuensial.

Berkas sekuensial berindeks memiliki kelebihan di bandingkan dengan berkas sekuensial yaitu :

Indeks terhadap berkas sehingga menghasilkan pengaksesan random yang lebih baik

Area overflow untuk menyediakan ruang bila dilakukan penambahan rekaman kedalam berkas 

BLOCKING & BUFFERING

Blocking adalah Penempatan sejumlah record pada suatu block. Block adalah unit data yang ditransfer. Block berukuran tetap berisi sekumpulan karakter yang dipindah dari penyimpan ke memori atau sebaliknya. 

Ada 3 metode blocking :

1. Fixed Blocking
2. Variable-Length Spanned Blocking
3. Variable-Length UnSpanned Blocking

Record adalah unit untuk penyimpanan data di level logik atau file. Ukuran rekord :

1. Berukuran tetap (fixed record)
2. Berukuran variabel (variable record)

A. Fixed Blocking

Fixed Blocking adalah Jumlah record pada suatu block sama dengan jumlah record pada block yang lainnya.

Batasan dalam penggunaan metode ini :

1. Fixed length record
2. Record length <= Block Size
3. Blocking Factor (Bfr) = [B/R]

Blocking factor adalah jumlah record yang dapat ditampung didalam satu block.

B. Variable - Lenght Spanned Blocking

Block berisi record-record dengan panjang tidak tetap.

Jika satu record tidak dapat dimuat disatu block, sebagian record disimpan di block lain.

B = Block Size

P = Block Pointer

R = Panjang Record rata-rata

M = Record Mark

C. Variable – Lenght Unspanned Blocking

Block berisi record-record dengan panjang tidak tetap. Setiap record harus dimuat di satu block.

B = Block Size

R = Panjang Record rata-rata

ORGANISASI BERKAS - BERKAS SEKUENSIAL

ORGANISASI BERKAS

Organisasi berkas diatas memiliki kemampuan untuk diproses dengan metode pemprosesan & pengaksesan yang berbeda.

Dalam menggorganisasi berkas secara Sekuensial, Langsung, maupun Sekuensial Berindeks memiliki cara yang berbeda dalam penyusunan rekaman-rekaman yang membentuk berkas / file tersebut. Rekaman-rekaman data tersebut tersusun atas sejumlah medan Data.

Medan Data : Nilai Dasar yang membentuk sebuah rekaman Data

Rekaman Data : Koleksi Berbagai Medan yang berisi beberapa item data elementer

Berkas Data : koleksi dari rekaman-rekaman yang sama, yang diletakan dalam peralatan penyimpanan data komputer.

Rekaman Data

Contoh rekaman data mahasiswa

Contoh berkas mahasiswa sebuah universitas

BERKAS SEKUENSIAL

Dalam berkas Sekuensial, rekaman ke i+1 akan diletakan tepat sesudah rekaman ke-i,  sebagai contoh :

Pencarian berkas sekuensial

Pencarian berkas secara sekuensial dilakukan dengan memproses rekaman-rekaman dalam berkas sesuai dengan urutan keberadaan rekaman-rekaman tersebut sampai ditemukan rekaman-rekaman yang diinginkan atau semua rekaman akan terbaca.

Contoh “nama mahasiswa” merupakan subskrip dalam pencarian pembacaan rekaman dengan “nama mahasiswa” = “Dewi Sartika”

Untuk mencari nama “Dewi Sartika”, diperlukan probe sejumlah 5 kali

Permasalahan yang muncul bila rekaman berada pada urutan belakang, maka pembacaan akan semakin lama. Dan apabila nama yang dicari tidak ada dalam rekaman, maka aplikasi harus membaca semua rekaman & berakshir denganm pesan “Rekaman tidak ditemukan”

Agar kinerja pembacaan rekaman lebih baik maka salah satu alternatif yang dapat dilakukan adalah rekaman-rekaman dalam berkas tersebut DIURUTKAN untuk mendapatkan pengurutan yang linier berdasar pada nilai kunci rekaman tersebut (bisa alfabetis maupun numeris)

Kolom “Nama Mahasiswa” menunjukan nilai yang urut dari kecil ke besar

Setelah data tersebut diurutkan maka pembacaan secara sekunsial dalam pemprosesan pencarian nama “Dewi Sartika” hanya diperlukan 2 probe lebih kecil dibandingkan sebelum berkas diurutkan.

PENCARIAN BINER (BINARY SEARCH)

Untuk sebuah berkas yang sudah di urutkan, jumlah probe yang diperlukan untuk membaca sejumlah rekaman dapat di usahakan untuk diperkecil lagi dengan menggunakan teknik pencarian biner.

Jika Kuncicari < Kuncitengah, maka bagian berkas mulai dari Kuncitengah sampai akhir berkas dielaminiansi.

Contoh 1

Cari rekaman dengan kunci 49 .... ?

                 1     2    3   4    5   6     7   8    9

Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]

Iterasi 2 :  21, 25, 28, 33, 38, [39, 48, 49, 69]

Iterasi 3 :  21, 25, 28, 33, 38, 39, 48, [49, 69]

Perhitungan :

Iterasi 1           : TENGAH1 = [1+9)/2] = 5

            Kuncicari : Kuncitengah à 49 > 38

            AWAL = TENGAH1  + 1 = 5+1 = 6

        1     2    3    4    5    6     7   8    9

 Iterasi 1 : [21, 25, 28, 33, 38, 39, 48, 49, 69]                                                                                                                                               

Iterasi 2           : TENGAH2 = [6+9)/2] = 7

            Kuncicari : Kuncitengah à 49 > 48

           AWAL = TENGAH2  + 1 = 7+1 = 8

                  1    2    3    4    5    6     7   8    9

Iterasi 2 :  21, 25, 28, 33, 38, [39, 48, 49,69]                                                                                                                                   

Iterasi 3           : TENGAH3 = [8+9)/2] = 8

            Kuncicari : Kuncitengah à 49 = 49

            Ketemu, Probe = 3

                  1    2    3    4    5    6     7   8    9

Iterasi 3 :  21, 25, 28, 33, 38, 39, 48, [49, 69]

PENCARIAN INTERPOLASI

Pencarian Interpolasi menentukan posisi yang akan diperbandingkan berikutnya berdasarkan posisi yang diestimasi dari sisa rekaman yang belum diperiksa. Syarat dalam pencarian berkas dalam pencarian interpolasi adalah kunci rekaman adalah bilangan numeris, karena dalam proses pencarian interpolasi posisi rekaman yang akan dibandingkan dihitung dengan melibatkan proses aritmatik tehadap kunci awal, kunci akhir, dan kunci yang di cari. Kunci awal adalah kunci awal pada posisi pencarian terakhir, bukan kunci awal berkas.

Untuk mencari kunci berikutnya pada metode Interpolasi dapat menggunakan :

Jika Kunci (dicari) = Kunci (berikut), maka pencarian berakhir

Jika Kunci (dicari) > kunci (berikut), maka AWAL = BERIKUT + 1

Jika Kunci (dicari) < kunci (berikut), maka AKHIR = BERIKUT - 1

CONTOH 1

Untuk rekaman dengan susunan sebagai berikut :

               1   2    3    4     5    6    7    8    9

            [21, 25, 28, 33, 38, 39, 48, 49, 69]

Berapa probe untuk menentukan rekaman dengan kunci 49 bila menggunakan pencarian interpolasi ?

            1      2    3     4    5    6    7   8     9

Iterasi 1 :         [21, 25, 28, 33, 38, 39, 48, 49, 69]

Iterasi 2 :         21, 25, 28, 33, 38, 39, [48, 49, 69]

Perhitungan :

Iterasi 1           Berikut1 = 1 + ((49-21)/(69-21)) (9-1) = 5.66666 ≈ 5

Kcari banding Kberikut = 49 > 38, Maka AWAL = Berikut1 + 1 = 5+1 =6

 1     2    3    4    5     6   7    8     9

Iterasi 1 :        [21, 25, 28, 33, 38, 39, 48, 49, 69]

Iterasi 2           Berikut2 = 6 + ((49-39)/(69-39)) (9-6) = 7

Kcari banding Kberikut = 49 > 48, Maka AWAL = Berikut2 + 1 = 7+1 =8

                         1    2   3    4     5    6    7    8     9

Iterasi 2 :        21, 25, 28, 33, 38, [39, 48, 49, 69]

Iterasi 3           Berikut3 = 8 + ((49-49)/(69-49)) (9-7) = 8

Kcari banding  Kberikut = 49 = 49, Maka Ketemu, Probe = 3

                         1    2   3    4    5    6    7     8     9

Iterasi 3 :        21, 25, 28, 33, 38, 39, 48, [49, 69]