Teknik Pengalamatan dalam Algoritma dan Pemrograman
 
Teknik  Pengalamatan
Rekaman-
 rekaman dalam suatu berkas nalari diciri (diidentifikasi) oleh 
perangkat nomer yang unik atau kelompok karakter yang unik.
Perangkat
 ini disebut kunci, biasanya menempati medan yang panjangnya tetap dalam
 masing- masing rekaman. Untuk membentuk suatu kunci yang unik kadang- 
kadang diperlukan gabungan dua medan atau lebih yang disebut kunci 
berderet. (concatenated key)
Dalam
 beberapa berkas, rekaman- rekaman berisi lebih dari satu kunci. 
Misalnya barang yang sudah dibeli mempunyai nomer penyalur dan nomer 
pemakai yang berbeda. Keduanya dipakai sebagai kunci. Kunci harus unik, 
karena kunci itu dipakai untuk menentukan di mana rekaman harus diambil 
dari unit  berkas dan untukk melacak rekaman itu dari berkasnya. Ini 
disebut kunci utama atau penciri (identifier).
Persoalan
 dari pengalamatan berkas adalah: diberikan kunci utama, lalu bagaiman 
komputer mengambil rekaman atau kunci itu? Ada berbagai teknik 
pengalamatan rekaman.
Teknik 1 : Pemayaran Berkas (Scanning the file)
Cara
 yang paling sederhana untuk pengambilan rekaman adlah memayar berkas 
dengan memeriksa kunci setiap rekaman. Metode ini sangat lambat dan 
hanya mungkin digunakan dalam operasi pemrosesan kelompok yang memakai 
berkas serial, seperti pita, di mana setiap rekaman mau tidak mau harus 
dibaca.
Teknik 2 : Pencarian Ruas (Block Search) 
Pada rekaman- rekaman yang diorganisasikan serial dengan kunci, tidak perlu setiap rekaman dibaca pada waktu memayar berkas.
Berkas
 itu dalam urutan kunci utama yang menanjak (ascending). Misalnya kunci 
rekaman yang dicari Ks, maka pencarian dimulai dari kunci- kunci ruas 
yang kecil. Seperti halnya pembagian rentetan pada bab sebelumnya, 
ukuran ruas yang optimum adalah NB =
 . Nf adalah jumlah rekaman daklam berkas. Pada pemeriksaan kalau 
ditemukan rekaman yang kuncinya pertama kalau kali lebih besar dari Ks, 
maka rekaman- rekaman dari ruas yang baru saja diloncati diperiksa 
(dipayar) sampai ditemukan rekaman dengan kunci Ks.Kadang- kadang cara 
ini disebut pencarian loncatan (skiipsearch).
 Misalnya ada 10.000 rekaman dalam suatu berkas. Ruas pencarian terdiri 
atas 100 rekaman. Rata-rata ada 100 rekaman yang diperiksa sehingga 
ditemukan rekaman yang diminta. Proses pencarian baru akan dilakukan 
pada ruas yang mengandung rekaman yang diminta. Dalam praktek tidak ada 
pencarian ruas yang rekamannya sampai 10.000, yang berarti seluruh 
berkas ada 10.0002 rekaman
 . Dalam hal ini diperlukan index yang mewakili seluruh rekaman. 
Kemudian pada index inilah dilakukan pembagian ruas-ruas pencarian.
Teknik  3. Pencarian Biner ( Binary Search )
Pencarian
 biner pertama-tama menuju ketengah-tengah area yang mengandung rekaman 
yang diminta. Lalu membandingkan kunci rekaman yang ditengah-tengah itu 
dengan kunci yang dicari. Maka akan diketahui bahwa kunci yang dicari 
letaknya dibelahan yang mana. Kemudian menuju ketengah-tengah belahan 
itu lagi .Proses ini diulangi terus menerus. Berkas diperiksa rata-rata 
kurang lebih       (log 2 Nf -1 ) kali. Untuk harga Nf (jumlah rekaman dalam berkas) yang besar, log Nf – 1 lebih kecil daipada   .
Pencarian
 biner umumnya tidak tepat untuk pencarian pada piranti simpanan masup 
langsung, karena menghabiskan banyak waktu. Pencarian biner tidak dapat 
dipakai untuk pencarian pada rentetan, karena komputer tidak mempunyai 
peralatan untuk mengatur pencarian itu.  Sepaerti diketahui rentetan 
terdiri atas rekaman-rekaman yang disatukan dengan pointer, sehingga 
sulit untuk menentukan titik tengahnya. Pencarian biner bermanfaat untuk
 pencarian rinci-rinci dalam memori utama atau simpanan tingkat padat 
(misalnya hard disk ).
Jenis
 khusus dari pencarian biner adalah rinci-rinci yang dicari tidak 
disusun berurutan, tetapi dalam bentuk pohon biner dengan 
pointer-pointer. Kemudian pencarian diteruskan dengan menelusuri 
pointer-pointer. Keuntungan bentuk pencarian ini adalah bahwa rekaman 
– rekaman baru dapat disisipkan ke dalam berkas , tanpa harus 
menggeser ke samping ( proses ini merupakan operasi yang janggal dan 
memakan waktu). Titik tengah yang dituju akan bergeser untuk 
menyesuaikan penambahan itu.
Pencarian biner lebih baik dilakukan pada index-index berkas daripada langsung mencari berkasnya sendiri.
Teknik 4 . Berkas Serial Berindex
Pada
 umumnya pemayaran atau pencarian berkas-berkas untuk mendapatkan suatu 
rinci terlalu banyak memakan waktu. Metode tersebut hanya dipakai untuk 
menudingsuatu rinci dalam area yang kecil setelah teknik-teknik yang 
lain menemukan area yang ditempatinya.
Pemayaran cakram atau alur drum dapat dibuat bersamaan dengan waktu rotasi dan karena itu bermanfaat.
Apabila
 berkas mempunyai kunci yang berurutan, biasanya digunakan tabel yang 
disebut index . Masukan pada tabel adalah kunci rekaman yang dicari, 
danhasil operasi pencarian tabel adalah alamat relatif atau alamat 
sesungguhnya dari rekaman itu pada unit berkas.
Suatu
 index didefinisikan sebagai suatu tabel di mana beroperasi dengan 
prosedur yang menerima informasi tentang harga-harga atribet tertentu 
sebagai masukan, dan sebagai keluaran memberikan informasiyang membantu 
pengambilan rekaman dengan cepat, di mana rekaman itulah yang memiliki 
harga-harga atribut tersebut. Index utama adalah index yang menggunakan 
ciri rekaman (kunci utama) sebagai masukan dan memberikan informasi 
tentang lokasi fisis dari rekaman sebagai keluara. Index sekunder adalah
 index yangmengunakan kunci yang tidak unik, tapi dapat mewakili 
sejumlah rekaman.
Index kadang- kadang disebut sebagai penuntun (directory)
 yang memberikan informasi tentang pertalianantara rekaman- rekaman, 
sebagai contoh, memberikan hubungan- hubungan dalam struktur jaring atau
 stuktur pohon.
Apabila
 suatu index dipakai untuk pengelamatan berkas, maka komputer harus 
mencari index, bukan mencari berkas itu. Cara ini dapat menghemat banyak
 sekali waktu, tetapi dibuthkan ruangan untuk menyimpan index itu. Hal 
ini mirip dengan penggunaan indek kartu dalam perpustakaan. Pemakai 
mencari nama buku yang dia perludi dalam index kartu, dan index kartu 
itu memberikan nomor katalog, yang analog dengan alamat relatifdari 
letak buku itu pada ra
Apabila
 berkas mempunyai kunci yang berurutan, umumnya index tidak berisi acuan
 untuk setiap rekaman, tetapi cukup satuan acuan untuk ruas- ruas 
rekaman.
Pengacuan
 ruas- ruas rekaman dibandingkan dengan pengacuan pada rekaman individu 
sangant banyak mengurangi ukuran indek. Walaupun demikian index 
seringkali terlalu besar untuk dicari dalam keseluruhannya, dan dengan 
demikian diperlukan suatu index untuk sejumlah index.
Untuk
 menghemat waktu pencarian, segmen- segmen dari iondex tingkat lebih 
rendah dapat diedarkan di antara rekaman- rekaman data yang bersangkutan
Pada
 area berkas yang diwakili satu index, dilakukan pencarian dengan metode
 pencarian ruas atau pencarian biner maupun pemayaran. Pada berkas 
cakram biasanya mempunyai satu alur index untuk setiap silinder, yang 
berisi acuan – acuan untuk rekaman- rekaman yang tersimpan dalam 
silinder itu.
Berkas
 serial berindex merupakan bentuk yang paling umum dari pengalamatan 
berkas. Mode lokasi VIA dari CODASYL memakai teknik ini.
Teknik 5 : Berkas Tak Berurutan Berindex (Indexed Nonsequential Files)
Berkas
 yang tak berurutan dapat diberi index seperti halnya berkas berurutan. 
Tetapi memerlukan index yang jauh lebih banyak, karena harus berisi satu
 entry
 untuk satu rekaman. Lagi pula, harus berisi alamat lengkap tertentu 
(atau alamat relatip), sedangkan suatu index pada berkas berurutan dapat
 memotong alamat yang dikandungnya, karena urutan karakter tingkat 
tinggidari alamat berturut-turut biasanya sama.
Misalnya APNA, APNE, APNI, APNK, dan seterusnya. Dalam hal ini APN sama semua.
Berkas berurutan berindex jauh lebih ekonomis, karena ruang index jauh lebih sedikit dan waktu pencarian lebih cepat.
Alasan
 utama tetap digunakanya berkas tak berurutan ialah bahwa harus 
dialamatkan lebih dari satu kunci. Apabila kunci yang satu diurutkan, 
maka kunci yang lain tidak akan terurutkan. Suatu index dapat dipakai 
untuk tiap kunci, index untuk kunci berurutan mempunyai satu entry per ruas. Sedang kunci tak berurutan, satu entry untuk
 setiap rekaman. Untuk berkas yang berkunci banyak, kunci yang paling 
sering dipakai biasanya yang diurutkan, karena masup cepat dimungkinkan 
oleh index berurutan pendek.
Analogi
 index kartu perpustakaan lebih tepat untuk berkas berurutan berindex. 
Dua kunci dipakai dalam indek kartu, yakni judul buku dan nama 
pengarang. Kedua kunci ini tidak dipakai untuk pengurutan buku- buku 
pada rak- rak. Oleh karena itu harus ada suatu entri untuk setiap buku 
dalam kedua index it.
Buku-
 buku itu disusun dalam urutan dengan nomor katalog, Apabila pemakai 
telah menemukan nomor katalog dari buku yang diinginkannya, lalu dia 
mencari pada jajaran-jajaran rak (lemari- lemari rak). Analog dengan 
pencarian Index dalam berkas. Masing- masing jajaran rak biasanya 
terdapat tanda nomor permulaan dan nomor akhir katalog dari buku- buku 
dalam jajaran itu. Pemakai membandingkan nomor katalog yang telah 
diperoleh dengan batasan nomor pada jajaran
 itu. Apabila  nomor katalog yang dipegangnya berada dalam batasan itu,
 berarti buku yang dicari berada dalam jajaran itu. Lalu dicocokkan batasan nomor pada tiap rak
 dalam jajaran itu. Analog dengan index induk pada suatu index silinder 
dam kemudian pada index  alur. Setelah menemukan rak yang memuat buku 
tersebut , lalu pemakai mencari- cari buku tersebut dalam rak itu. Dalam
 hal ini pencarian dalam berkas dapat menggunakan metode pencarian ruas 
ataupun pemayaran dan pencarian biner.
Index
 perpustakaan tidak menunjukkan lokasi fisis dari buku pada raknya. 
Tetapi memberikan pada nomor katalog yang dapat dianggap sebagai alamat 
relatif atau alamat simbul. Alasannya dipakai alamat simbul ialah kalau 
alamat fisis yang dipakai, lalu karena buku-buku dalan rak selalu 
bergeser tempatnya, maka index perpustakaan harus sering diperbarui/ 
diubah. Dengan alasan yang sama berkas tak berurutan berindex juga 
kadang- kadang memakai simbul daripada alamat sungguh. Penambahan 
rekaman baru dan penghapusan rekaman lama selalu menggeser lokasi 
rekaman- rekaman.
Apabila
 lebih dari satu kunci digunakan dalan rekaman- rekaman. Index pada 
suatu kunci yang bukan utama dapat menunjukkan kunci utama dari rekaman 
sebagai keluarannya. Kunci utama ini kemudian digunakan untuk 
pengembilan rekaman dengan pengalamatan yang lain. Analogi dengan index 
perpustakaan, misalnya judul buku adalah kunci utama, sedang nama 
pengarangbukan kunci utama. Dengan kunci nama pengarang, kitadapat 
menemukan kunci utamanya. Metode dengan menggunakan alamat simbul lebih 
lambat daripada alamat fisis, tetapi pada berkas yang rekaman- 
rekamannya sering berubah posisinya, pengalamatan simbul menunjuk 
manfaatnya.
Alasan
 lain untuk penggunaan susunan rekaman tak berurutan adalah bahwa berkas
 itu sangaty lincah dan penyisipan penghapusan ke dalam berkas yang 
berurutan akan terlalu sulit dan terlalu makan waktu. Apabilabuku yang 
disimpan dalam rak diurutkan menurut abjadnya, maka pemeliharaannya 
memerlukan waktu banyak, karenasetiap kali ditambahkan buku baru, 
sejumlah buku harus digeser. Kalau buku- buku itu tak berurutan, 
tapitapi nomor katalognya berurutan, maka buku barudapat diletakkan pada
 posisi terakhir dengan nomor urut katalog yang terakhir.
Teknik 6 : Pengalamatan Alamat Setara Kunci 
(Key- Equals- Address)
Berbagai
 metode pengubahan kunci langsung ke dalam suatu alamat berkas dipakai. 
Penggunaan metode- metode ini dapat menghasilkan perangkat pengalamatan 
yang tercepat dan tidak diperlukan pencarian berkasatau operasi index.
Cara
 pemecahan persoalan pengalamatan yang paling sederhana aialah dalam 
transaksi input, memiliki alamatsama dengan kunci supaya pengambilannya 
sederhana.Pola ini termasuk pengalamatan langsung.Dlam banyak aplikasi, 
pendekatan langsung ini tidak dimungkikan. Nomor- nomor barang dari 
suatu pabrik tidak dapat diubah untuk menyesuaikan komputer karena 
nomor- nomor itu mempunyai arti yang penting bagi perusahaan tersebut.
Kadang-
 kadang nomor acuan mesin dapat digunakan dalam transaksi input tanpa 
membutuhkan nomor konsumen ataupun nomor barang. Sebagai contoh, alamat 
berkas dari rekaman dapat dicetak pada buku tabungan langganan bank. 
Apabila komputer pemesan perusahaan penerbangan mengirimkan pesan 
teletip pada perusahaanpenerbangan yang lain, biasanya pesan itu 
mancakup nomor acuan mesin dari rekaman penumpang. Jawabandalam pesanan 
teletip diterima, misalnya tentang penegasan pemesanan, maka harus 
mencakup nomor acuan mesin, sehingga rekaman penumpang itu segera 
ditemukan.
Mode lokasi DIRECT dari CODASYL memakai teknik ini.
Teknik 7 : Alogaritma Untuk Konversi Kunci
Penggunaan
 algoritma untuk mengbah kunci ke dalam alamat, hampir secepat dengan 
teknik alamat setara kunci   (teknik 6). Alamat pada beberapa apilkasi
 dapat dihitung dari penciri entiti seperti lokasi jalan, nomor 
penerbangan dan tanggal penerbangan. Tidak semua aplikasi yang tidak 
menerapkannya. Tetapi metode ini adalah sederhana dan cepat untuk 
aplikasi yang dapat menerapkannya.
Teknik
 ini biasanya mempunyai kerugian karena tidak memenuhi barkas dengan 
sempurna. Ada celah- celahnya, karena kunci- kunci tidak diubah menjadi 
satu himpunan alamat yang kontinu. Sebagai contoh, perusahaan 
penerbangan mempunyai 150 nomor penerbangan. Algoritma memakai nomor 
penerbangan dan tanggal untuk menghitung alamat berkas. Tetapi tidak 
setiap penerbangan terbang pada setiap hari; karena itu, beberapa alamat
 yang dihasilkannya tidak memuat rekaman.
Apabila
 rekaman- rekaman membentuk suatu matrik, maka cocok untuk perhitungan 
alamat berkas. Sebagai contoh, suatu perusahaan mempunyai banyak 
distributor,. Masing- masing distributor menangani 200 produk. Rekaman 
yang diberikan adalah tentang penjualan setiap produk untuk setiap 
distributor dalam setiap distributor dalam setiap minggu untuk tahun 
ini. Apabila panjang rekaman 100 byte, maka alamat byte relatif dari rekaman untuk distributor ke-A, produk ke- B, dan minggu ke- C dapat dihitung dengan rumus:
(A
 -1) × 200 × 52 × 100 + (B− 1) × 52 × 100 + (C − 1) × 100 + 1.
 Suatu program akan mengubah alamat relatif ini ke dalam sebuah alamat 
mesin.
Kerugian
 dari pola ini pengalamatan langsung yakni kelakuannya. Sepaerti 
diketahui bahwa alamt mesin dpat berubah- ubah, karena berkas berkembang
 atau dipindahkan pada suatu unit yang lain atau berkas digabungkan atau
 dimodifikasi. Dalam hal ini pengalamatan langsung tidak dapat berjalan.
 Untuk menghilangkan sifat kekakuan ini pengalamatan langsung biasanya 
diselesaikan dalam dua tingkat. Tingkat pertama mengubah kunci menjadi 
suatu bilangan urut. Tingkat kedua mengubah bilangan urut itu menjadi 
alamt mesin. Apabila alamat mesin rekaman berbah, maka bilangan- 
bilangan urut yang dipakai tingkat kedua dapat dimodifikasi dengan mudah
 untuk menyesuaikan perubahan alamat mesin tersebut.
Mode lokasi CALC dari CODASYL memakai teknik ini.
Teknik 8 : Gabungan (Hashing) 
Suatu bentuk yang bermanfaat dan akurat dari teknik perhitungan alamat disebut gabungan atau kadang- kadang disebut pengacakan (randomizing) atau pengadukan (scrambling).
 Dalam teknik ini kunci rinci diubah menjadi suatu bilangan hampir acak,
 dan bilangan ini dipakai untuk menentuksn di man rinci tersebut 
disimpan. Bilangan hampir acak itu dapat berhubungan dengan alamat di 
mana suatu rekaman disimpan. Cara ini ;lebih ekonomis, karena 
berhubungan dengansuatu area di mana suatu grup rekaman disimpan yang 
disebut sebagai bucket (keranjang), kadang- kadang disebut pocket (saku) atau slot. Jumalah rekaman nalari yang dapat disimpan dalam area ini disebut kapasitas bucket.
Apabila pada permulaan, berkas hendak diamati, lokasi dalam mana rekaman- rekaman disimpan ditentukan sebagai berikut:
- Kunci
 dari rekaman diubah menjadi suatu bilangan hampir      acak, n, yang 
terletak dalam interval l sampai N, di mana N adalah jumlah bucket
      yang dapat dipakai untuk simpanan. Banyak algoritma gabungan 
memungkinkan      operasi ini, dan harus dipilih satu yang sesuai dengan
 himpunan kunci dari      rekaman- rekaman yang dibicarakan.
 
- Bilangan n diubah menjadi alamt dari bucket itu      dibaca.
 
- Apabila ada sisa ruang dalam bucket itu, maka      rekaman nalari dapat disimpan ke dalam bucket itu.
 
- Apabila bucket luapan (overflow). Ini dapat        sebagai urutan berikut, atau dapat sebagai suatu bucket      pada area yang terpisah yang duihubungkan dengan pointer.
 
Apabila rekaman- rekaman hendak dibaca dari berkas, maka metode pencarian adalah sama dengan di atas , yaitu:
- Kunci
 dari rekaman yang akan dicari, diubah menjadi      suatu bilangan 
hampir acak, yaitu n, dengan menggunakan algoritma yang      sama.
 
- Bilangan n itu diubah menjadi alamat dari bucket      ke- n, dan dan rekaman fisis di dalamnya dibaca.
 
- Bucket      dicari untuk mendapatkan rekaman nalari yng diminta.
 
- Apabika rekaman yang diminta tiadak ada dalam bucket      luapan dibaca dan di- search. Kadang- kadang perlu membaca lebih      dari satu bucket luapan.
 
Teknik ini tidak akan mencapai kerapatan packing 100%, karena adanya sifat- sifat acak dari algoritma. Banyak Berkas dapat mencapai kerapatan packing
 80%atau 90% dan tidak ada ruang yang diperlukan untuk index. Banyak 
rekaman dapat diperoleh dengansatu pencarian, tetapi ada yang memerlukan
 pencarian dalam satu detik, yaitu pada bucket luapan. Jarang diperlukan pencarian ketiga atau keempat.
sumber: http://id.wikipedia.org