Jumat, 05 Oktober 2018
ORGANISASI
BERKAS SEKUENSIAL
Dalam
organisasi ini, record-record direkam secara berurutan pada waktu berkas ini
dibuat dan harus diakses secara berurutanpada waktu berkas ini digunakan
sebagai input. Berkas sekuensial sangat cocok untuk akses yang sekuensial,
misalnya dalam aplikasi dimana sebagian besar atau semua rekaman akan diproses.
Sebagai contoh adalah membuat daftar mahasiswa dalam sebuah program studi.
Melakukan akses secara sekuensial berarti proses akan berpindah dari satu
rekaman ke rekaman berikutnya secara langsung.
Pencarian
secara sekuensial adalah memproses rekaman – rekaman dalam berkas sesuai urutan
keberadaan rekaman – rekaman tersebut sampai ditemukan rekaman yang diinginkan
atau semua rekaman terbaca. Berkas sekuensial juga dapat diproses secara
tunggal dan langsung, jika diketahui subskripnya. Tetapi bagaimana kalau
subskrip yang dimiliki bukan identitas utama rekaman, misal ‚Nama Mahasiswa‛
pada file berikut ini :
Pembacaan
harus dilakukan secara sekuensial.Rekaman demi rekaman, sampai ‚Nama Mahasiswa‛
yang sesuai ditemukan. Misalnya untuk pembacaaan rekaman dengan ‚Nama Mahasiswa‛
= Sunaryono, diperlukan probe (akses terhadap lokasi yang berbeda) sejumlah 4
kali. Yang harus dilakukan agar kinerja pembacaan rekaman lebih baik, maka
rekaman-rekaman dalam berkas mahasiswa tersebut diurutkan untuk mendapatkan
pengurutan yang linier berdasarkan nilai kunci rekaman.Baik secara alphabetis
maupun numeris. Hasil pengurutannya adalah sbb :
Berkas diatas
berisi rekaman mahasiswa urut berdasar ‚Nomor Induk Mahasiswa‛.Kolom ‚Nomor
Induk Mahasiswa‛ menunjukkan nilai yang urut dari kecil ke besar. Dengan
demikian , hanya n/2 rekaman yang perlu diperiksa rekaman-demi-rekaman untuk
menemukan rekaman yang diinginkan. Kalau pembacaan diteruskan melewati posisi
dimana rekaman seharusnya berada (mengingat berkas sudah diurutkan), maka
proses pencarian dihentikan. Untuk membaca ‚Sunaryono‛ hanya diperlukan 2
probe, lebih kecil disbanding berkas sebelum diurutkan.Namun teknik tersebut
masih kurang memuaskan untuk berkas dengan jumlah rekaman yang lebih besar.
A.
PENCARIAN BINER (BINARY SEARCH)
Pencarian
Biner dalah membandingkan kunci yang dicari dengan rekaman pada posisi tengah
dari berkas. Bila sama (Kasus 1) rekaman yang diinginkan sudah ditemukan. Jika
tidak sama (kasus 2), berarti separuh rekaman-rekaman dalam berkas akan
dieliminasi dari perbandingan yang selanjutnya. Bila yang terjadi pada kasus 2,
maka proses perbandingan terhadap rekaman pada posisi di tengah dilanjutkan
menggunakan rekaman-rekaman yang tersisa. Jumlah probe (yang diperlukan untuk
membaca sebuah rekaman) pada sebuah berkas dengan rekaman yang sudah diurutkan,
dapat diperkecil dengan menggunakan teknik pencarian biner. Jika kunci
cari<kunci tengah maka bagian berkas mulai dari kunci tengah sampai akhir
berkas dieliminiasi. sebaliknya jika kunci cari>
kunci tengah,
maka bagian berkas mulai dari depan sampai dengan kunci tengah dieliminiasi.
Dengan
mengulang proses perbandingan terhadap rekaman tengah, maka lokasi rekaman yang
diinginkan akan ditemukan atau diketahui bahwa rekaman yang diinginkan tersebut
tidakberada dalam berkas. Algoritma pencarian biner:
B.
PENCARIAN INTERPOLASI
Pencarian
interpolasi (asumsinya kunci rekaman numeris) menentukan posisi yang akan
dibandingkan berikutnya berdasar posisi yang di estimasi dari sisa rekaman yang
belum diperiksa. Pencarian interpolasi tidak mencari posisi tengah, seperti
algoritma pencarian biner, melainkan menentukan posisi berikutnya.
