Tampilkan postingan dengan label sistem berkas. Tampilkan semua postingan
ORGANISASI BERKAS LANGSUNG
Pengguna teknologi pada umumnya dan teknologi informasi pada
khususnya merasa bahwa waktu yang diperlukan untuk memperoleh suatu informasi
masih terlalu lama. Metode pencarian biner maupun interpolasi masih belum dapat
mengimbangi ketidaksabaran manusia terhadap penyediaan informasi yang cepat dan
akurat. Perkembangan media perekam data dalam hal kemampuan untuk menampung
volume data yang sangat besar harus diimbangi dengan peningkatan teknik
pencarian kembali data yang tersimpan.
A. KUNCI SEBAGAI ALAMAT REKAMAN YANG UNIK
Untuk mendapat rekaman yang diasosiasikan dengan suatu kunci
primer, sangat diharapkan agar proses langsung menuju ke alamat tempat rekaman
dengan kunci tertentu disimpan. Hal tersebut mungkin terjadi apabila satu kunci
rekaman juga merupakan alamat lokasi rekaman. Untuk aplikasi rekaman berisi
nomor induk mahasiswa, terdapat 8 digit (kunci rekaman yang merupakan gabungan
2 digit tahun angkatan + 2 digit kode program studi + 4 digit nomor urut), maka
diperlukan lokasi sebanyak 99.999.999. Dengan demikian waktu pencarian
akansangat baik, yaitu 1 probe untuk setiap rekaman yang dicari. Akan tetapi,
teknik tersebut memiliki kerugian karena diperlukan ruang yang sangat besar
untuk menampung semua rekaman. Untuk menampung data NIM mahasiswa diperlukan
ruang yang besar, meski jumlah mahasiswa mungkin hanya 500, pasti ada beberapa
nomor yang kosong karena beberapa alasan, misalnya sudah lulus, mengundurkan
diri, drop-out, cuti, dan sebagainya. Sehingga tidak semua ruang dimanfaatkan.
B. KONVERSI KUNCI REKAMAN MENJADI SATU ALAMAT
YANG UNIK
Contoh klasik yang menggambarkan fenomena konversi kunci
rekaman adalah 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.
C. MENENTUKAN ALAMAT DENGAN KONVERSI
KUNCI
Diperlukan satu fungsi untuk memetakkan cakupan nilai kunci
yang lebih luas ke dalam cakupan yang lebih sempit nilai alamat. Fungsi yang
dikenal dengan fungsi hashakan
melakukan pemetaan sebagaimana diharapkan. Hash (kunci) kemungkinan alamat
Keluaran dari proses hashing bukan lagi alamat yang unik, melainkan kemungkinan alamat bagi kunci yang di
hash. Alamat untuk menempatkan alamat yang diperoleh dari fungsi hash disebut home-address untuk rekaman tersebut.
Tidak ada batasan mengenai bentuk fungsi yang akan memetakkan kunci ke cakupan
alamat, tetapi diharapkan fungsi tersebut menghasilkan kemungkinan alamat
yang:
Mampu
mendistribusi kunci secara merata ke dalam cakupan alamat. Hal tersebut
dimaksudkan untuk mengurangi terjadinya kolisi. Kolisi terjadi bila hasil
hashing dua kunci rekaman yang berbeda menunjuk ke alamat yang persis
sama.
Dapat
dieksekusi dengan efisien. Hal tersebut dimaksudkan agar waktu pembacaan dapat
ditekan seminimal mungkin.
Maka fungsi hashing dapat
dipandang dari 2 aspek, yaitu:
Fungsi
hash itu sendiri
Metode
untuk meresolusi kolisi
Mekanisme resolusi kolusi diperlukan untuk mengatasi
terjadinya jumlah rekaman yang dikonversikan ke suatu lokasi melebihi
kapasitasnya.Dalam bahasan ini diasumsikan bahawa satu lokasi memiliki
kapasitas satu rekaman. Berikut adalah beberapa fungsi hash, dimulai dari yang
paling sering digunakan.
a) Hashing dengan Kunci Modulus N
Satu fungsi hash yang paling
popular dan paling sering diimplementasikan adalah modulus N,
dengan N sebagai ukuran tabel atau berkas. Hasil fungsi
modulus adalah sisa pembagian kunci oleh N. Sabagai contoh untuk N=12 maka: 30
mod N = 6 40 mod N = 4 Keuntungan fungsi ini 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 modulus N, rumusnya adalah:
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: untuk N=12 maka P=13 30 mod P = 4 40 mod P =
1
c) Hashing dengan Pemotongan
Alternatif lain untuk fungsi hashing adalah pemotongan.
Sebagai contoh adalah para pegawai negeri sipil di Indonesia. Para pegawai
memiliki NIP (Nomor Induk Pegawai) dengan panjang total 9 digit, terdiri atas 3
digit pertama sebagai identitas departemen, sementara 6 digit terakhir adalah
nomor urutnya. Bila ingin dijadikan 6 digit saja, maka bisa dilakukan
pemotongan jumlah digit.Pemotongan bisa dilakukan dibagian mana saja, tentunya
dengan konsekuensi masing-masing. Pada kasus NIP, jika pemotongan dilakukan
pada bagian belakang, akan diperoleh sejumlah alamat yang memiliki 3 digit yang
sama (identitas departemen) sehingga kemudian kolisinya akan lebih besar
dibanding bila pemotongan dilakukan di bagian depan.
d) Hashing dengan Lipatan
Fungsi ini melipat digit pada batasan yang ditentukan
berdasarkan kondisi digit awal dan digit yang akan dihasilkan. Sebagai contoh 9
digit NIP akan direduksi menjadi 3 digit, maka digit awal di bagi 3, kemudian
dilipat pada batas antarbagian.
Kunci asli tersebut ditulis pada selembar kertas. Batasan
dimana lipatan akan dilakukan ditandai dengan garis .
Penjumlahan dari susunan tersebut
adalah:
385
976
421
----- +
Jika penjumlahan dilakukan dengan mengabaikan carry maka
diperoleh alamat 672, sedangkan jika tidak mengabaikan carry maka hasilnya 782.
e) Hashing dengan Penggeseran
Hashing dengan penggeseran memiliki proses yang serupa dengan
hashing lipatan, bedanya setelah ditentukan batasan. Digit asli dipotong
kemudian digeser dan dihitung hasil jumlahnya. 583 976 124 ----- + Yang
diperoleh alamat yang berbeda yaitu 573 (tanpa carry). Jika kedua hasil
penjumlahan tersebut diterapkan dengan menggunakan carry dan hanya tiga digit
yang paling kanan saja yang digunakan, maka diperoleh 683.
f) Hashing dengan Pengkuadratan
Hashing dengan penguadratan adalah fungsi hashing dengan
menguadratkan kunci.Hasil penguadratan ini kemudian dapat dikombinasi dengan
pemotongan atau lipatan untuk mendapatkan alamat yang diperbolehkan. Sebagai
contoh, penguadratan kunci 782 akan menghasilkan kemungkinan alamat 117. F(782)
= 117
g) Hashing dengan Konversi Radix
Dalam
konversi radix, kunci dianggap dalam base selain 10 yang kemudian dikonversi ke
dalam basis 10, misal kunci 5 6 7 8 dalam base 13 akan menghasilkan 12098,
diperoleh dari: 5 6 7 8 Posisi: 3 2 1 0 Hasil tersebut masih dapat dikombinasi
dengan fungsi hash lain (pemotongan atau lipatan) untuk mendapatkan digit
alamat yang diinginkan.
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.
ORGANISASI
BERKAS PRIMER
Organisasi berkas akan
mempelajari struktur yang tepat untuk mengorganisasi:
1) Jumlah rekaman yang besar
2) Berkas dengan kinerja tertentu
3) Informasi yang diolah dengan cara yang berbeda untuk
keperluan yang berbeda
4) Informasi yang memungkinkan dilakukannya tugas-tugas
khusus
5) Menyelesaikan permasalahan dengan cara yang berbeda
dari yang selama ini dilakukan
A. ORGANISASI BERKAS
Terdapat tiga oganisasi berkas
primer, yaitu sekuensial, langsung, dan sekuensial berindeks. Masing-masing
organisasi tersebut memiliki cara memproses atau mengakses berkas.
Sebagai contoh, terdapat
sejumlah unit informasi yang disebut rekaman yang mengandung data mengenai
entitas individual.Rekaman tersebut dapat diuraikan menjadi unit-unit yang
lebih kecil, yang disebut medan-medan yang mengandung nilai-nilai khusus bagi
atribut-atribut yang mewakili individu tersebut.
B. MEDAN DATA
Medan berisi nilai dasar yang
membentuk sebuah rekaman. Isi sebuah medan bergantung pada atribut yang
dimiliki oleh individu pemilik rekaman. Nilai tersebut pada saatnya nanti akan
dimanipulasi oleh proses komputasi. Nilai-nilai dalam medanharus tunduk pada
deskripsi tentang tipe nilai, kapasitas byte maksimum, domain dan seterusnya
yang dimiliki oleh medan tersebut.
Rekaman yang disimpan dalam
berkas pada umumnya memiliki medan yang berfungsi khusus, yaitu sebagai
identitas rekaman yang memiliki sifat pembeda baik internal maupun eksternal.
Medan ‘tanggal’ yang umumnya dimiliki oleh sebuah rekaman merupakan contoh yang
unik. Medan tersebut bisa memiliki kapasitas byte maksimum 8, dan disusun dari
3 medan yang lebih elementer, yaitu tanggal (2digit), bulan (2digit), tahun
(4digit). Data tanggal paling baik dinyatakan dalam tipe bilangan, mengingat
tanggal memiliki kemungkinan untuk diperbandingkan (lebih tua atau lebih muda),
proses dengan aritmatik sederhana (menghitung umur) dan sebagainya. Pemilihan
tipe data yang paling sesuai dengan kebutuhan yang disyaratkan oleh sistem yang
sedang dibangun merupakan hal yang penting.Suatu domain yang spesifik, sangat
baik bila diuraikan dalam satu tipe dan satu representasi. Representasi yang
tidak sesuai akan menyebabkan hilangnya informasi yang sulit untuk dilacak
kembali.
C. REKAMAN DATA
Rekaman merupakan koleksi
berbagai medan yang berisi beberapa item data elementer. Beberapa medan dapat
berhubungan satu dengan yang lainnya karena mereka melakukan deskripsi suatu
hal yang spesifik, misalnya tentang seseorang , tentang sebuah subyek, atau
suatu kejadian. Informasi tentang seseorang mahasiswa misalnya, dapat disimpan
dengan cara berikut : Rekaman mahasiswa
Rekaman tersebut dapat disimpan
dengan nama-nama medan ‚Nama Mahasiswa‛, ‚Nomor Mahasiswa‛, ‚Jenjang‛, ‚Program
Studi‛, ‚Dosen Wali‛, ‚SPP‛, dan lain-lain. Kunci primernya merupakan suatu
medan, atau gabungan beberapa medan, yang secara unik membedakan satu rekaman
dengan yang lainnya, sedangkan semua medan yang tersisa merupakan kunci skunder
dari atribut. Sebagai contoh: medan ‚Nama Mahasiswa‛ ataupun ‚Nomor Mahasiswa‛
mungkin merupakan kunci primer, sedangkan medan ‚Jenjang‛, ‚Program Studi‛, dan
yang lain merupakan kunci skunder.
D. BERKAS DATA
Sebuah berkas merupakan koleksi
dari rekaman-rekaman yang sama, yang diletakkan dalam peralatan penyimpanan
data komputer. Salah satu tipe peralatan penyimpanan eksternal, dari berbagai
alternatif, adalah penggerak disk dengan disk magnetiknya. Sebuah berkas akan
memiliki nama yang dikenal oleh sistem operasi, dan mempunyai struktur atau
organisasi yang ditentukan oleh program pengakses berkas.
Dalam merancang sebuah berkas
untuk menyimpan semua rekaman yang menggambarkan tentang mahasiswa sebuah universitas,
bukanlah gagasan yang baik bila beberapa tipe rekaman di campur-aduk, missal
rekaman mahasiswa dengan daftar matakuliah yang ditawarkan, dalam sebuah berkas
yang sama. Sebaliknya, mempunyai berbagai berkas yang berbeda juga mengundang
berbagai kesulitan dikemudian hari.Untuk mengulangi kesulitan-kesulitan
tersebut, para pakar berusaha mencari jalan keluar.Akhirnya ditemukan suatu
alternatif yaitu menggabungkan rekaman-rekaman milik semua mahasiswa untuk
semua jurusan dalam sebuah berkas.
