Organisai File Secara Sequensial Beserta Contoh dan Persyaratannya

1. Organisasi File Sequential

     1.1 Pengertian File Sequential

Organisasi berkas sequential adalah merupakan cara yang paling dasar untuk mengorganisasikan kumpulan record-record dalam sebuah berkas. Dalam organisasi berkas  sequential, pada waktu record ini dibuat, record-record direkam secara berurutan.

     1.2 Proses
           Karena record-record dalam organisasi berkas sequential harus diakses secara berurutan, maka berkas sekuensial lebih sering menggunakan batch processing dari pada interactive processing.

      1.3  Keuntungan dari Sequential File
          Merupakan organisasi file yang sederhana. Jarak setiap aplikasi yang tersimpan sangat jelas. Metode penyimpanan didalam memory sangat sederhana, sehingga efisien untuk menyimpan  record yang besar. Sangat murah untuk digunakan, sebab medianya cukup menggunakan magnetic tape.

      1.4  Kerugian Dari Sequential File

         Seandainya diperlukan perubahan data, maka seluruh record yang tersimpan didalam master file, harus semuanya diproses. Data yang tersimpan harus sudah urut (sorted). Posisi data yang tersimpan sangat susah untuk up-to-date, sebab master file hanya bisa berubah saat proses selesai dilakukan. Tidak bisa dilkukan pembacaan secara langsung.

       1.5  Pola Akses
         Pola Akses adalah penentuan akses berdasarkan field tertentu. Selama pola akses, berkas sequential dapat dipasangkan dengan record-record yang sudah diurut pada berkas, maka waktu aksesnya sangat baik.

      Jadi kita harus menentukan pola akses terlebih dahulu, kemudian baru menentukan organisasi berkas sequential berdasarkan urutan yang sesuai dengan pola aksesnya, jangan sebaliknya.

Contoh:
Berkas gaji yang disusun secara sequential berdasarkan NIP, hendak diakses berdasarkan NAMA, maka program tidak baik. Juga tidak baik mengakses record dengan urutan sebagai berikut:
NIP = 15024508, NIP = 15024607
NIP = 15024115, NIP = 1502800
Dimana NIP tersebut belum tersortir.

       1.6  Media Penyimpanan Berkas Sequential
         Berkas sequential dapat disimpan dalam SASD, seperti magnetic tape atau pada DASD, seperti magnetic disk.

Beberapa alasan untuk menyimpan berkas sequential pada DASD :
Pada umumnya komputer dihubungkan dengan sedikit tape drive, sehingga tidak cukup untuk menunjang program aplikasi yang banyak membutuhkan berkas sekuensial.
Contoh :
Jika 3 berkas sequential, seperti master file, transaction file dan update master file yang digunakan oleh sebuah program. Karena hanya ada 2 tape drive, maka salah satu dari ketiga berkas tersebut disimpan dalam disk.

Sistem yang dikonfigurasikan untuk fungsi berkas tertentu, selalu disimpan dalam disk.
Contoh :
Printer hanya dapat menerima semua berkas yang akan dicetak, bila terlebih dahulu berkas tersebut disimpan dalam disk. Jadi bila kita ingin membuat sebuah berkas laporan, maka harus ditentukan dari disk ke printer.

       1.7  Pembuatan Berkas Sequential
        Pembuatan berkas sequential meliputi penulisan record-record dalam serangkaian yang diinginkan pada media penyimpanan.

Pembuatan berkas transaksi sequential meliputi tugas-tugas:
Pengumpulan data
Perubahan data dalam bentuk bahasa yang dapat dibaca oleh mesin
Pengeditan data
Pemeriksaan transaksi yang ditolak
Penyortiran edit data 

3 Teknik Organisasi Berkas Relatif

Organisasi Berkas Relatif 

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

Ada 3 teknik dasar yang digunakan untuk menyatakan fungsi pemetaan R, dimana R (nilai key)  address

1.       Direct mapping (pemetaan langsung)

2.       Directory look up (pencarian tabel)

3.       Calculation (kalkulasi)

Direct mapping (pemetaan langsung)

Teknik ini merupakan teknik yang sederhana untuk menerjemahkan nilai record key menjadi address.  Ada 2 cara dalam pemetaan langsung :

1.      Absolute Addressing (Pengalamatan Mutlak)

2.       Relative Addressing (Pengalamatan Relatif)

 Pengalamatan Mutlak

             R(nilai key)              Address

             Nilai key = alamat mutlak

Jika nilai key yang diberikan oleh pemakai program sama dengan address sebenarnya dari record tersebut pada penyimpanan sekunder.  Pada waktu record tersebut disimpan, lokasi penyimpanan record (nomor silinder, nomor permukaan, nomor record) bila dipakai cylinder addressing atau (nomor sektor, nomor record) bila dipakai sector addressing harus ditentukan oleh pamakai.

Keuntungan dari pengalamatan mutlak adalah sebagai berikut :

1.   Fungsi pemetaan R sangat sederhana

2. Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder

       Kelemahannya dari pengalaman mutlak adalah sebagai berikut :

3.   Pemakai harus mengetahui dengan pasti record-record yang disimpan secara fisik

4.  Alamat mutlak adalah device dependent, perbaikan atau pengubahan device,                     dimana berkas berada akan mengubah nilai key

5.  Alamat mutlak adalah address space dependent, reorganisasi berkas relatif akan               menyebabkan nilai key berubah.

·         Pengalamatan Relatif

R(nilai key)         Address

 Nilai key = alamat relative

Alamat relatif dari sebuah record dalam sebuah berkas adalah urutan record tersebut dalam berkas.  Sebuah berkas dengan N record mempunyai record dengan alamat relatif dari himpunan (1,2,3, …, N -2, N -1).  Record yang ke I mempunyai alamat relatif I atau I – 1 (bila mulai dihitung dari 0).

Keuntungan dari pengalamatan relatif adalah Sebagai berikut:

Ø  Fungsi pemetaan R sangat sederhana

Ø  Nilai key dari sebuah record dapat ditentukan lokasi recordnya dalam sebuah penyimpanan sekunder tanpa memerlukan waktu proses yang berarti.

       Kelemahannya adalah sebagai  berikut :

Ø  Alamat relatif adalah bukan device dependent

Ø  Alamat relatif adalah address space dependent

Ø   Terjadinya pemborosan ruangan.

2.    Teknik Pencarian Tabel.

Dasar pemikiran pendekatan pencarian tabel adalah sebuah tabel atau direktori dari nilai key dan address.  Untuk menemukan sebuah record dalam berkas relatif, pertama dicari dalam direktori nilai key dari record tersebut, yang akan menunjukan alamat dimana record tersebut berada dalam penyimpanan.

Gambar struktur tabel file relatif

	Directory
	Key	Address		File Relatif		Alamat Relatif
	APE	I – 1		COW		1
	BAT	N		ZEBRA		2
	CAT	N – 1		.
	.			APE		I – 1
	COW	1		EEL		I
	DOG	I + 1		DOG		I + 1
	EEL	I		.
	.			CAT		N – 1
	ZEBRA	2		BAT		N

DIRECTORY

                                                                                                                                 APE, I - 1

                                                                                BAT, N

                                                                                                                 CAT, N - 1

                                COW, 1

                                                                                                                                DOG, I + 1

                                                                                EEL, I

                                                                                                                ZEBRA, 2

Data dalam direktori tersebut disusun secara urut menurut nilai key, sehingga pencarian nilai key dalam direktori lebih cepat dengan binary search dibanding sequential search.  Alternatif lain, direktori dapat disusun dalam binary search tree, m-way search tree atau B-tree.

Keuntungan dari pencarian tabel

1.       Sebuah record dapat diakses dengan cepat, setelah nilai  key dalam direktori ditentukan.

2.       Nilai key dapat berupa field yang mudah  dimengerti  seperti PART  NUMBER,   NPM, karena  nilai   key   tersebut   akan diterjemahkan menjadi alamat.

3.       Nilai  key  adalah  address   space   independent,   dimana reorganisasi berkas tak akan memepengaruhi nilai  key,  yang berubah adalah alamat dalam direktori.

3.     Teknik Kalkulasi Alamat

          R (NILAI KEY) ADDRESS

Adalah dengan melakukan kalkulasi terhadap  nilai key, hasilnya adalah alamat relatif. Ide dasar dari kalkulasi alamat adalah mengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil alamat relatif. Salah satu kelemahan dari teknik  pengalamatan  relatif  adalah ruang harus disediakan sebanyak jangkauan nilai  key,  terlepas dari berapa banyak nilai key Salah satu masalah dari teknik ini adalah  ditemukannya  alamat relatif yang sama untuk nilai key yang berbeda.

Keadaan dimana :

             R(K1)  =  R(K2)       disebut benturan

                 K1   ¹   K2            atau collision

Sedangkan nilai key K1 dan K2 disebut synomin.

Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.

Teknik-teknik yang terdapat pada kalkulasi alamat :

·         Scatter storage techniques

·         Randomizing techniques

·         Key-to-address transformation methods

·         Direct addressing techniques

·         Hash table methods

·         Hashing

Disini yang akan kita bahas mengenai teknik hashing.

Kalkulasi terhadap nilai key untuk mendapatkan sebuah alamat disebut fungsi hash.

B.  PROSES

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.

C. Kelebihan

•         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

D.  Kelemahan

Dengan menerjemahkan langsung dari kunci rekaman ke alamat rekaman, maka akan berlaku suatu hubungan korespondensi satu-satu antara kunci dengan alamat rekaman .Hal ini menyebabkan harus disediakannya ruang yang sangat besar untuk menampung setiap kemungkinan nilai kunci yang ada

Contohnya : untuk menyimpan data PNS yang kuncinya adalah NIP (terdiri dari 9 digit) dibutuhkan sebanyak satu milyar alamat, karena kemungkinan yang dapat muncul dari kode 9 digit adalah mulai dari angka 000000000 hingga 999999999)

Penjelasan Mengenai Metode-Metode Teknik Hashing

Berikut beberapa penjelasan metode teknik hashing:

Pengertian Hashing

Hash adalah suatu teknik "klasik" dalam Ilmu Komputer yang banyak digunakan dalam praktek secara mendalam. Hash merupakan suatu metode yang secara langsung mengakses record-record dalam suatu tabel dengan melakukan transformasi aritmatik pada key yang menjadi alamat dalam tabel tersebut. Key merupakan suatu input dari pemakai di mana pada umumnya berupa nilai atau string karakter.

Pelacakan dengan menggunakan Hash terdiri dari dua langkah utama, yaitu:

1. Menghitung Fungsi Hash

 Fungsi Hash adalah suatu fungsi yang mengubah key menjadi alamat dalam tabel. Fungsi Hash memetakan sebuah key ke suatu alamat dalam tabel. Idealnya, key-key yang berbeda seharusnya dipetakan ke alamat-alamat yang berbeda juga. Pada kenyataannya, tidak ada fungsi Hash yang sempurna. Kemungkinan besar yang terjadi adalah dua atau lebih key yang berbeda dipetakan ke alamat yang sama dalam tabel. Peristiwa ini disebut dengan collision (tabrakan). Karena itulah diperlukan langkah berikutnya, yaitu collision resolution (pemecahan tabrakan).

2. Collision Resolution

 Collision resolution merupakan proses untuk menangani kejadian dua atau lebih key di-hash ke alamat yang sama. Cara yang dilakukan jika terjadi collision adalah mencari lokasi yang kosong dalam tabel Hash secara terurut. Cara lainnya adalah dengan menggunakan fungsi Hash yang lain untuk mencari lokasi kosong tersebut.

 Fungsi Hash (dilambangkan dengan h(key)) bertugas untuk mengubah key menjadi suatu nilai dalam interval [0....LEVELSIZE-1], dimana "LEVELSIZE" adalah jumlah maksimum dari record-record yang dapat ditampung dalam tabel. Jumlah maksimum ini bergantung pada ruang memori yang tersedia. 

 Fungsi Hash yang ideal adalah mudah dihitung dan bersifat random, agar dapat menyebarkan semua key. Dengan key yang tersebar, berarti data dapat terdistribusi secara seragam dan collision dapat dicegah. Sehingga kompleksitas kinerja model Hash dapat mencapai O(1), di mana kompleksitas tersebut tidak ditemukan pada struktur model lain. 

KELEBIHAN DAN KELEMAHAN MODEL HASHING 

 Model Hash memiliki kelemahan pada saat penambahan dan penghapusan record. Diperlukan waktu untuk menstrukturisasi tabel Hash. Pada tabel Hash terdapat suatu daerah (akibat collision) kelebihan data (overflow). Untuk mencapai daerah tersebut, memerlukan waktu. Lamanya waktu disebabkan jika data diletakkan dalam disk atau tape. 

 Hal ini bisa diatasi dengan meletakkan keseluruhan data sampel secara utuh ke dalam memori. Namun ruang memori yang terbatas merupakan kendala tersendiri, karena data yang tersedia dalam kamus kata ini sangat besar (46.010 buah).

 Penghapusan suatu unsur dari tabel Hash dapat menimbulkan masalah. Penghapusan suatu key dapat menyebabkan key-key yang berikutnya tidak dapat diakses, karena stuktur tabel yang sudah ada menjadi berubah. Namun dalam pembuatan kamus kata, hal tersebut tidak perlu dikhawatirkan, karena program ini tidak membutuhkan suatu penghapusan. Semua data yang terdapat dalam "Basis Data Kamus Kata" (yang berarti berada dalam tabel Hash), bersifat permanen, sehingga tidak perlu penghapusan. 

PENANGGULANGAN COLLISION 

 Masalah yang biasanya terjadi adalah, data yang ada begitu besar dibandingkan dengan jumlah lokasi dalam tabel. Sangatlah sukar, bahkan tidak mungkin untuk menemukan fungsi Hash yang dapat mencegah collision. Oleh karena itu penanggulangan collision yang baik sangat penting dalam Hash agar bisa meminimalkan jumlah collision.

 Jika tabel Hash yang dimiliki berukuran T[0...LEVELSIZE-1], collision terjadi apabila lokasi T[h(key)] telah terisi pada saat ingin menyisipkan key. Oleh karena itu, harus ada suatu cara untuk menentukan lokasi lain dalam tabel Hash tersebut untuk menyimpan key. Collison resolution bertujuan untuk menentukan lokasi kosong tersebut.

Teknik-teknik collision yang ada diantaranya adalah:

è Separate Chaining

Teknik Separate Chaining merupakan suatu teknik untuk mengatasi collision dengan cara menggunakan daerah di luar tabel Hash dalam bentuk linier. Bentuk linier ini bisa berupa linked-list atau array. Urutan data pada daerah overflow bisa terurut atau random, tergantung cara penyisipan yang dilakukan.

è Open Addressing

Teknik Open Addressing adalah suatu teknik penyimpanan dalam tabel Hash yang membutuhkan ruang memori sangat besar. Open Addressing Hash menyimpan N data dalam tabel Hash yang berukuran LEVELSIZE dengan menggunakan tempat-tempat kosong untuk menangani collision resolution.

è Double Hashing

Teknik Double Hashing adalah suatu teknik penyimpanan dalam tabel Hash dimana jika terjadi collision, lokasi selanjutnya adalah lokasi sekarang + h(k). h(k) adalah suatu fungsi Hash yang berbeda dengan fungsi Hash yang pertama

KESIMPULAN 

 Dari rangkaian eksperimen yang telah diujikan, kami mendapat kesimpulan bahwa kecepatan dari suatu algoritme pencarian kata dipengaruhi oleh:

1. Fungsi Hash

Fungsi Hash yang mendekati ideal sangat menentukan kemerataan penyebaran kata pada tabel Hash, sehingga dapat meminimalkan jumlah collision yang terjadi. Fungsi Hash yang ideal adalah mudah dikomputasikan dan bersifat random untuk meminimalkan jumlah collision. Hasil random tersebut dicapai dengan cara memanfaatkan seluruh unsur dalam key dan memperhatikan semua urutan dalam key tersebut. Namun dalam pemanfaatan seluruh unsur dalam key dapat berakibat pada sulitnya komputasi fungsi Hash. Fungsi Hash yang kompleks akan menambah kompleksitas (bisa menyebabkan fungsi Hash tidak lagi linier) yang mengakibatkan penambahan running time pada saat perhitungan terhadap fungsi Hash. Dengan demikian, perlu dicari suatu algoritme Hash yang bagus.

2. Pemakaian Informasi Frekwensi

Algoritme Hash dengan memanfaatkan informasi frekwensi kata ternyata memberikan kontribusi besar dalam kecepatan waktu pencarian kata. Waktu keseluruhan pencarian kata yang diperlukan oleh algoritme dengan memanfaatkan informasi frekwensi adalah 0,056 detik. Hasil ini 65% lebih cepat dibandingkan dengan algoritme Hash yang tidak memanfaatkan informasi frekwensi (0,086 detik).

3. Hardware yang dipakai untuk melakukan running terhadap program

Dengan pemakaian hardware yang memiliki kinerja tinggi, maka running time terhadap program juga semakin cepat

pengorganisasian berkas indeks sequensial

Organisasi Berkas Indeks Sequential

Ada 2 pendekatan dasar untuk mengimplementasikan konsep dari organisasi berkas indeks sequential :

Blok Indeks dan Data (Dinamik)

Prime dan Overflow Data Area (Statik)

Kedua pendekatan tersebut menggunakan sebuah bagian indeks dan sebuah bagian data, dimana masing-masing menempati berkas yang terpisah. Alasannya :

Karena mereka diimplementasikan pada organisasi inBEETLEal yang berbeda. Masing-masing berkas tersebut harus menempati pada alat penyimpan yang bersifat Direct Access Storage Device (DASD).

Blok Indeks Dan Data (DINAMIK)

Pada pendekatan ini berkas indeks dan berkas data diorganisasikan dalam blok. Berkas indeks mempunyai struktur tree, sedangkan berkas data mempunyai struktur sequential dengan ruang bebas yang didistribusikan antar populasi record.

Pada gambar tersebut ada N blok data dan 3 tingkat dari indeks. Setiap entry pada indeks mempunyai bentuk (nilai key terendah, pointer), dimana pointer menunjuk pada blok yang lain, dengan nilai key-nya sebagai nilai key terendah. Setiap tingkat dari blok indeks menunjuk seluruh blok, kecuali blok indeks pada tingkat terendah yang menunjuk ke blok data.

Jika sebuah permintaan untuk mengakses record tertentu, misal kita ingin mengakses dengan nilai key BAT, indeks dengan tingkat tertinggi (dalam hal ini blok indeks 3-1) yang pertama yang akan dicari pada contoh ini, pointer dari BIRD menunjuk blok indeks 2-1. Pointer yang ditunjuk pada kotak tersebut adalah pointer yang berisikan BIRD, yang akan menunjuk ke blok indeks 1-1. POinter berikutnya yang akan ditunjuk adalah pointer yang berisi PENGUIN, yang selanjutnya akan menunjuk blok data 2. Blok data ini akan mencari untuk record dengan key tujuan, yaitu BAT, dimana pada blok ini record tersebut ditemukan.

Permintaan untuk akses data dalam urutan sequential dilayani dengan mengakses blok data dalam urutan sequential. Sebagai catatan blok data merupakan consecutive secara logik dan bukan consecutive secara fisik. Dalam hal ini, blok data harus dihubungkan secara bersama dalam urutan secara logik, seperti terlihat pada gambar. Misal : Setiap blok data mempunyai ruang yang cukup untuk menampung 5 record dan setiap blok indeks mempunyai ruang yang cukup untuk menyimpan 4 pasang (nilai key, pointer). Parameter ini biasanya sudah dilengkapi dengan rutin dukungan sistem manajemen data, pada saat berkas binatang ini dibentuk. Jika kita menginginkan penyisipan maupun penghapusan terhadap isi berkas, maka blok indeks dan blok data akan dibuat dengan sejumlah ruang bebas, yang biasanya disebut sebagai padding dan pada gambar ditunjukkan sebagai irisan. Prime dan Overflow Data Area (STATIK) Pendekatan lain untuk mengimplementasikan berkas indeks sequential adalah berdasarkan struktur indeks dimana struktur indeks ini lebih ditekankan pada karakteristik fisik dari penyimpanan, dibandingkan dengan distribusi secara logik dari nilai key. Indeksnya ada beberapa tingkat, misalnya tingkat cylinder indeks dan tingkat track indeks. Berkas datanya secara umum diimplementasikan sebagai 2 berkas, yaitu prime area dan overflow area. Misalnya setiap cylinder dari alat penyimpanan mempunyai 4 track. Pada berkas binatang ada 6 cylinder yang dialokasikan pada prime data area. Track pertama (nomor 0) dari setiap cylinder berisi sebuah indeks pada record key dalam cylinder tersebut. Entry pada indeks ini adalah dalam bentuk