Teknik Pengalamatan
Preambule
Untuk
menyimpan data ke dalam memori komputer, tentu memori tersebut diberi identitas
(yang disebut dengan alamat/ address) agar ketika data tersebut diperlukan
kembali, komputer bisa mendapatkannya sesuai dengan data yang pernah diletakkan
di sana.
Untuk
media penyimpanan yang bersifat sequential access storage device (SASD) seperti
kaset (magnetic tape), alamat tersebut tidak terlalu dipusingkan karena pasti
data disimpan secara berurutan (sequential/ consecutive) mulai dari depan
hingga ke akhir bagian dari pita kaset. Begitu juga dengan data yang
diorganisasi secara sequential, di alamat manapun data disimpan, data akan
tetap diakses secara berurutan pula, mulai dari record pertama hingga ke record
terakhir.
Lain
halnya dengan data yang diorganisasi secara relative yang disimpan di media
penyimpanan yang bersifat direct access storage device (DASD), karena data yang
akan diraih kembali, dituju langsung ke alamatnya tanpa melalui records lainnya
(belum tentu dimulai dari data yang paling awal disimpan), maka alamat memori
memegang peranan penting. Untuk itu, di catatan ini akan diterangkan beberapa
cara melakukan penempatan data di memori agar kelak dapat diraih kembali dengan
tepat, yang diberi judul “Teknik Pengalamatan.”
Teknik
pengalamatan ini hampir sudah tidak diperlukan lagi oleh pemakai komputer saat
ini karena hampir seluruh software yang beredar di pasaran tidak mengharuskan
si pemakai menentukan di alamat mana datanya akan disimpan (semua sudah
otomatis dilakukan oleh si software). Jadi, yang kita pelajari adalah bagaimana
kira-kira si software tersebut melakukan teknik pengalamatannya, sehingga data
yang sudah kita berikan dapat disimpan di alamat memori tertentu dan dapat
diambil kembali dengan tepat.
Ada
3 teknik dasar untuk pengalamatan, yakni 1. Pemetaan langsung (direct mapping)
yang terdiri dari dua cara yakni Pengalamatan Mutlak (absolute addressing) dan
Pengalamatan relatif (relative addressing), 2. Pencarian Tabel (directory
look-up), dan 3. Kalkulasi (calculating).
TEKNIK
PEMETAAN LANGSUNG
1. PENGALAMATAN MUTLAK
1. PENGALAMATAN MUTLAK
Pandang,
kita memiliki data teman-teman sekelas kita yang akan kita masukkan ke dalam
memori (misal hard disk), data tersebut berjumlah 50 orang yang masing-masing
terdiri atas atribut-atribut : NIM, NAMA, dan ALAMAT_RUMAH.
Jika
data tersebut kita masukkan dengan organisasi file sequential, maka jika kita
mencari data NIM = ‘10105787’ yang namanya ‘ALI’ dan beralamat di ‘Jl. Margonda
No. 100, Depok’, maka pencarian akan dilakukan mulai dari record pertama (data
pertama yang dimasukkan), dan seterusnya menuju ke record terakhir sampai
ketemu data yang dicari tersebut.
Lain
halnya jika data tersebut dimasukkan dengan organisasi file relative, maka data
tersebut akan didapat secara langsung dari record yang dituju. Tentu, untuk
langsung mendapatkan record yang dituju ada ‘sesuatu’ yang disebut dengan kunci
atribut (key field). Kunci atribut itulah yang dikelola sedemikian rupa
sehingga ‘kita’ bisa tahu dimana record tersebut disimpan.
Untuk
teknik pengalamatan ‘alamat mutlak’ ini, kita tidak terlalu mempermasalahkan
kunci atribut karena kita diminta langsung menuliskan di mana alamat record
yang akan kita masukkan. Jika kita menggunakan hard disk atau magnetic drum,
ada dua cara dalam menentukan alamat memorinya, yaitu (1) cylinder addressing
dan (2) sector addressing. Jika kita menggunakan cylinder addressing, maka kita
harus menetapkan nomor-nomor dari silinder (cylinder), permukaan (surface), dan
record, sedangkan bila kita menggunakan sector addressing, maka kita harus
menetapkan nomor-nomor dari sektor (sector), lintasan (track), dan permukaan
(surface). Teknik ini mudah dalam pemetaan (pemberian) alamat memorinya.
Sulitnya pada pengambilan (retrieve) data kembali, jika data yang kita masukkan
banyak, kita bisa lupa di mana alamat record tertentu, misalkan apakah kita
ingat nomor record dari data NIM = ‘10105787’ yang namanya ‘ALI’ dan beralamat
di ‘Jl. Margonda No. 100, Depok’ ?, apakah kita harus menghafal selamanya
alamat-alamat tersebut ?. Pelajari keuntungan dan kerugian lainnya.
Teknik
ini dapat dijuluki dengan device dependent (tergantung pada peralatan
rekamnya), artinya, kita tidak dapat begitu saja meng-copy data berkas ini ke
komputer lainnya, karena mungkin saja di komputer lainnya itu menggunakan alat
rekam yang berbeda spesifikasinya.
Teknik
ini juga dapat dijuluki dengan address space dependent (tergantung pada
alamat-alamat yang masih kosong), artinya, kita tidak dapat begitu saja
meng-copy data berkas ini ke komputer lainnya, karena mungkin saja di komputer
lainnya itu alamat-alamat yang dibutuhkan sudah tidak tersedia lagi.
2.
PENGALAMATAN RELATIF
Teknik
ini menjadikan atribut kunci sebagai alamat memorinya, jadi, data dari NIM
dijadikan bertipe numeric(integer) dan dijadikan alamat dari record yang
bersangkutan. Cara ini memang sangat efektif untuk menemukan kembali record
yang sudah disimpan, tetapi sangat boros penggunaan memorinya. Tentu alamat
memori mulai dari 1 hingga alamat ke sekian juta tidak digunakan karena nilai
dari NIM tidak ada yang kecil. Pelajari keuntungan dan kerugian lainnya.Teknik
ini termasuk dalam katagori address space dependent.
TEKNIK
PENCARIAN TABEL
Teknik
ini dilakukan dengan cara, mengambil seluruh kunci atribut dan alamat memori
yang ada dan dimasukkan ke dalam tabel tersendiri. Jadi tabel itu (misal
disebut dengan tabel INDEX) hanya berisi kunci atribut (misalkan NIM) yang
telah disorting (diurut) dan alamat memorinya.
Jadi,
sewaktu dilakukan pencarian data, tabel yang pertama dibaca adalah tabel INDEX
itu, setelah ditemukan atribut kuncinya, maka data alamat yang ada di sana
digunakan untuk meraih alamat record dari data (berkas/ file/ tabel) yang
sebenarnya. Pencarian yang dilakukan di tabel INDEX akan lebih cepat dilakukan
dengan teknik pencarian melalui binary search (dibagi dua-dua, ada di mata
kuliah Struktur dan Organisasi Data 2 kelak) ketimbang dilakukan secara
sequential.
Nilai
key field (kunci atribut) bersifat address space independent (tidak terpengaruh
terhadap perubahan organisasi file-nya), yang berubah hanyalah alamat yang ada
di INDEX-nya.
TEKNIK
KALKULASI ALAMAT
Kalau
pada teknik pencarian tabel kita harus menyediakan ruang memori untuk menyimpan
tabel INDEX-nya, maka pada teknik ini tidak diperlukan hal itu. Yang dilakukan
di sini adalah membuat hitungan sedemikian rupa sehingga dengan memasukkan
kunci atribut record-nya, alamatnya sudah dapat diketahui. Tinggal masalahnya,
bagaimana membuat hitungan dari kunci atribut itu sehingga hasilnya bisa
efisien (dalam penggunaan memori) dan tidak berbenturan nilainya (menggunakan
alamat yang sama).
Misal,
untuk data si ALI di atas yang memiliki NIM = ‘10105787’, di mana akan kita
letakkan ?. Bila yang kita lakukan adalah perhitungan : INT(VAL(NIM)/1000000)
maka haslinya adalah 10, dengan demikian data si ALI akan disimpan di alamat
10. Tapi, apakah alamat 10 itu tidak akan digunakan oleh data lain dengan
perhitungan yang sama ?, ternyata tidak. Untuk data si BADU yang NPMnya
’10105656’ juga di alamat tersebut, dan ternyata masih banyak juga yang
’rebutan’ untuk menempati alamat tersebut jika dilakukan dengan perhitungan
seperti di atas.
Perhitungan
(kalkulasi) terhadap nilai kunci atribut untuk mendapatkan nilai suatu alamat
disebut dengan fungsi hash. Bisa juga fungsi hash digabungkan dengan teknik
pencarian seperti tabel di atas, tetapi akan menjadi lebih lama pengerjaannya
dibanding hanya dengan satu jenis saja (fungsi hash saja atau pencarian tabel
saja).
Fungsi
hash dikatakan baik bila memiliki kalkulasi yang sederhana dan memiliki kelas
ekivalen (synonim) yang kecil, atau sederhananya, memiliki kalkulasi yang mudah
tetapi memiliki benturan alamat yang sedikit.
Ada
beberapa cara untuk mengatasi benturan (collision) penggunaan alamat seperti di
atas, antara lain : scatter diagram techniques, randomizing techniques, key to
address transformation methods, direct addressing techniques, hash tables
methods, dan hashing. Di sini, kita hanya membahas mengenai hashing. Beberapa
fungsi hash yang umum digunakan adalah : division remainder, mid square, dan
folding.
DIVISION
REMAINDER
Idenya
adalah, membagi nilai key field dengan nilai tertentu, dan sisa pembagian
tersebut dijadikan alamat relatifnya. Nilai tertentu itu terserah kita, ada
yang membagi dengan bilangan prima, namun ada juga yang tidak.Yang jelas,
tujuannya adalah agar alamat yang akan digunakan bisa berbeda sekecil mungkin
(menghemat memori) dan menghindari benturan yang bakal terjadi.
Ada
perhitungan faktor muat (load factor) yaitu, jika kita memiliki sejumlah record
yang akan ditempatkan ke dalam memori, maka setidaknya kita harus menyediakan
memori yang kapasitasnya melebihi dari jumlah record tersebut. Misalkan, kita
memiliki 4000 record, maka sebaiknya kita memiliki memory space sebanyak 5000
alamat. Faktor muat dihitung dengan cara membagi jumlah record dalam file
dengan jumlah maksimum record dalam file (alamat yang tersedia). Semakin besar
nilai faktor muat maka semakin baik teknik ini digunakan. Faktor muat untuk
contoh di atas adalah 4000/5000 = 0,8.
MID SQUARE
Teknik ini dilakukan dengan cara melakukan kuadratisasi nilai key field dan diambil nilai tengahnya sebanyak jumlah digit yang diinginkan. Misalkan, nilai key-nya = 123456790, setelah dikuadratkan hasilnya = 15241578997104100 dan diambil 4 digit di tengahnya, yaitu 8997. Jadi, alamat memori untuk data tersebut di 8997.
Teknik ini dilakukan dengan cara melakukan kuadratisasi nilai key field dan diambil nilai tengahnya sebanyak jumlah digit yang diinginkan. Misalkan, nilai key-nya = 123456790, setelah dikuadratkan hasilnya = 15241578997104100 dan diambil 4 digit di tengahnya, yaitu 8997. Jadi, alamat memori untuk data tersebut di 8997.
HASING
BY FOLDING
Teknik ini dilakukan dengan cara ’melipat’ nilai dari kunci atribut sebanyak digit yang dibutuhkan (dari kanan), kemudian dijumlahkan. Nilai terbesar dari jumlah tersebut dibuang (jika melebihi digit yang dibutuhkan). Misalkan untuk nilai key 123456790, maka empat angka di belakang setelah dilipat menjadi 0976, angka tersebut ditambahkan dengan empat angka kedua (dari kanan) yaitu 2345 dan angka 1 paling kiri :
Teknik ini dilakukan dengan cara ’melipat’ nilai dari kunci atribut sebanyak digit yang dibutuhkan (dari kanan), kemudian dijumlahkan. Nilai terbesar dari jumlah tersebut dibuang (jika melebihi digit yang dibutuhkan). Misalkan untuk nilai key 123456790, maka empat angka di belakang setelah dilipat menjadi 0976, angka tersebut ditambahkan dengan empat angka kedua (dari kanan) yaitu 2345 dan angka 1 paling kiri :
0976
2345
1
——– +
4321
2345
1
——– +
4321
Maka,
alamat dari data tersebut adalah di 4321.
Berbagai teknik dalam penentuan penempatan data di memori (sekunder) komputer terus berkembang. Tentu saja karena data yang direkam biasanya selalu bersifat dinamis (bisa bertambah, berkurang, di-copy, di-sorting) dan sebagainya. Kedinamisan tersebut tentu saja bisa berpengaruh terhadap alamat-alamat yang sudah ditetapkan sebelumnya yang bersifat fixed size space atau memiliki ukuran alamat yang tetap (satu misalnya, jika kita meng-copy data tersebut yang semula di hard disk ke dalam disket, apakah alamat-alamat yang tersedia di disket sama dengan di hard disk ?, tentu tidak).
Teknik hash baru yang dikembangkan antara lain dynamic hashing, extendible hashing, dan virtual hashing. Tujuannya adalah agar alamat-alamat yang sudah ada tidak berubah meskipun data baru ditambahkan dengan cara membagi-bagi memori menjadi bagian-bagian tertentu yang disebut dengan blok atau bucket, bila sebuah record akan dimasukkan ke dalam bucket yang sudah penuh, maka bucket baru disediakan kembali.
Dynamic hashing memakai struktur indeks binary tree untuk menyimpan track dari bucket dan pointer untuk menuju ke record yang diinginkan. Extendible hashing menggunakan direction untuk menyimpan track dari bucket dan pointer untuk menuju ke record yang diinginkan. Sedangkan virtual hashing lebih luas lagi, termasuk di dalamnya dynamic hashing dan extendible hashing dan berbagai teknik indeks lainnya (yang tidak dibahas di sini).
Berbagai teknik dalam penentuan penempatan data di memori (sekunder) komputer terus berkembang. Tentu saja karena data yang direkam biasanya selalu bersifat dinamis (bisa bertambah, berkurang, di-copy, di-sorting) dan sebagainya. Kedinamisan tersebut tentu saja bisa berpengaruh terhadap alamat-alamat yang sudah ditetapkan sebelumnya yang bersifat fixed size space atau memiliki ukuran alamat yang tetap (satu misalnya, jika kita meng-copy data tersebut yang semula di hard disk ke dalam disket, apakah alamat-alamat yang tersedia di disket sama dengan di hard disk ?, tentu tidak).
Teknik hash baru yang dikembangkan antara lain dynamic hashing, extendible hashing, dan virtual hashing. Tujuannya adalah agar alamat-alamat yang sudah ada tidak berubah meskipun data baru ditambahkan dengan cara membagi-bagi memori menjadi bagian-bagian tertentu yang disebut dengan blok atau bucket, bila sebuah record akan dimasukkan ke dalam bucket yang sudah penuh, maka bucket baru disediakan kembali.
Dynamic hashing memakai struktur indeks binary tree untuk menyimpan track dari bucket dan pointer untuk menuju ke record yang diinginkan. Extendible hashing menggunakan direction untuk menyimpan track dari bucket dan pointer untuk menuju ke record yang diinginkan. Sedangkan virtual hashing lebih luas lagi, termasuk di dalamnya dynamic hashing dan extendible hashing dan berbagai teknik indeks lainnya (yang tidak dibahas di sini).
PENDEKATAN
MASALAH BENTURAN (COLLISION)
Hampir
semua teknik akan mengalami benturan dalam penggunaan alamat memorinya. Ada
beberapa teknik untuk menyelesaikannya, yaitu linear probing dan separate
overflow.
LINEAR
PROBING
Metode
ini dilakukan dengan cara : apabila hasil perhitungan key baru ternyata sama
dengan hasil perhitungan key sebelumnya, maka dengan menambahkan hasil
perhitungan tersebut dengan satu (per satu) (secara linear) sampai ke alamat
memori yang masih kosong, ia akan menempati alamat tersebut.
Misal, hasil perhitungan adalah 300 sedangkan di alamat 300 sudah ada yang menempati, maka data baru akan menempati alamat 301, bila alamat tersebut juga sudah ada yang menempati, maka ia akan menempati alamat 302, dan seterusnya bertambah satu-satu hingga ke alamat yang masih kosong (belum ditempati). Hal semacam ini disebut dengan open addressing.
Begitu juga ketika data tersebut dipanggil kembali, maka jika tidak ketemu di home address-nya (hasil perhitungan awalnya), maka akan ditambahkan dengan satu per satu hingga di alamat tertentu yang recordnya memiliki nilai key sama dengan nilai key yang dicari.
Misal, hasil perhitungan adalah 300 sedangkan di alamat 300 sudah ada yang menempati, maka data baru akan menempati alamat 301, bila alamat tersebut juga sudah ada yang menempati, maka ia akan menempati alamat 302, dan seterusnya bertambah satu-satu hingga ke alamat yang masih kosong (belum ditempati). Hal semacam ini disebut dengan open addressing.
Begitu juga ketika data tersebut dipanggil kembali, maka jika tidak ketemu di home address-nya (hasil perhitungan awalnya), maka akan ditambahkan dengan satu per satu hingga di alamat tertentu yang recordnya memiliki nilai key sama dengan nilai key yang dicari.
DOUBLE
HASHING
Dari
namanya dapat diketahui bahwa double hashing adalah menjalankan fungsi hash
yang kedua terhadap hasil fungsi hash yang pertama jika masih terjadi
collision. Penempatan data dapat dilakukan di primary area atau home address-nya
(hasil perhitungan sebenarnya, nilai interval yang mungkin dapat dijangkau
dengan perhitungannya), atau di separate overflow area (area yang disediakan
untuk menampung data yang berbenturan/ di luar area yang masuk dalam interval
nilai perhitungannya).
Double hashing lebih baik dari linear probing pada faktor muat tinggi (lebih dari 0,8), dan sama baik pada faktor muat 0,5. Double hashing memiliki synonim (hasil perhitungan yang sama/ terjadi collision) berpencar sedangkan linear probing mengelompok pada faktor muat kurang dari 0,5.
Double hashing lebih baik dari linear probing pada faktor muat tinggi (lebih dari 0,8), dan sama baik pada faktor muat 0,5. Double hashing memiliki synonim (hasil perhitungan yang sama/ terjadi collision) berpencar sedangkan linear probing mengelompok pada faktor muat kurang dari 0,5.
SYNONIM
CHAINING
Synonim
chaining adalah suatu rangkaian pointer yang menghubungkan (link) antara satu
alamat dengan alamat lain yang berada di separate overflow area.Hal ini
dilakukan untuk mempercepat akses di area tersebut. Jadi, jika hasil
perhitungan ternyata datanya bukan yang data dicari, maka akan di-link data
yang berada di separate overflow area mulai dari awal alamatnya hingga ketemu
data yang dicarinya.
BUCKET
ADDRESSING
Cara
lain untuk menghindari benturan adalah pembuatan blok-blok memori. Misalkan,
setiap 10 record akan kita tempatkan di dalam satu blok (bucket). Jika blok
tersebut sudah penuh, maka dibuka kembali blok-blok lain. Perhitungan
penempatan record ke dalam blok dapat dilakukan dengan teknik yang mirip dengan
teknik-teknik sebelumnya. Begitu juga dengan pengambilan data kembali
(retrieve) dilakukan dengan teknik-teknik yang sama dengan sebelumnya.
Istilah prime memory (memori yang ditempati oleh record yang sesuai dengan hasil perhitungannya) dan separate overflow (memori yang menampung record yang hasil perhitungannya berbenturan sehingga tidak bisa ditempatkan di memori sebenarnya) dipakai juga di sini. Istilahnya menjadi : primary bucket dan overflow bucket.
Istilah prime memory (memori yang ditempati oleh record yang sesuai dengan hasil perhitungannya) dan separate overflow (memori yang menampung record yang hasil perhitungannya berbenturan sehingga tidak bisa ditempatkan di memori sebenarnya) dipakai juga di sini. Istilahnya menjadi : primary bucket dan overflow bucket.
FILE
ORGANIZATION : INDEX SEQUENTIAL
Selain
organisasi berkas sequential dan relative yang telah dibahas sebelumnya,
berikut akan dibahas mengenai organisasi berkas index sequential. Contoh
sederhana dari organisasi ini adalah susunan data yang ada di sebuah buku
kamus. Kita bisa mengakses buku kamus tersebut secara sequential (berurutan),
maupun melalui index (daftar isi)nya. Jadi, file organization index sequential
adalah file yang disusun sedemikian rupa sehingga dapat diakses secara
sequential maupun secara direct (langsung), atau kombinasi keduanya, direct dan
sequential.
Ada dua pendekatan dasar dalam menyusun organisasi berkas semacam ini, yaitu (1) blok index dan data, dan (2) prime dan overflow data area. Untuk cara pertama, kita menyusun data dengan lebih memperhatikan ke data yang bersifat logik, bukan fisik. Jadi, data dan index diorganisasikan ke dalam blok-blok. Blok-blok index (daftar isi dalam buku kamus) diorganisasi secara sequential (consecutive) dan bertingkat-tingkat (misal setiap blok hanya berisi 4 record index yang berisi key field dan pointer). Setiap tingkat akan menuju ke blok data (misal setiap blok hanya berisi 5 record data) di tingkat selanjutnya dan seterusnya menuju ke blok data yang akan mendapatkan record yang dicari secara direct (lihat skema di buku referensi hal. 60).
Bila dilakukan penyisipan data dan blok tertentu (tempat data baru itu) sudah penuh (tidak ada tempat kosong/ padding lagi), maka akan dilakukan reorganisasi blok dengan membentuk blok baru.Tentu, mungkin saja perubahan ini akan berdampak pada isi blok index-nya.
Pendekatan kedua adalah dengan lebih memperhatikan aspek karakteristik dari hardware (fisik) alat penyimpanan datanya. Biasanya disimpan di hard disk yang memiliki cylinder dan track. Caranya hampir sama dengan cara di pendekatan pertama, hanya di sini lebih ditekankan pada aspek fisik. Jadi, yang bertingkat-tingkat adalah cylender-nya dan blok datanya ditulis secara consecutive di setiap track (misalkan 1 cylinder berisi 4 track, nomor 0 sampai 3). Index (pencarian data) tertinggi disebut dengan master index, dari master index berturut-turut menuju ke blok-blok index tingkat berikutnya hingga meraih record data yang berada di track-nya.
Bila dilakukan penyisipan data dan track tertentu (tempat data baru itu) sudah penuh (tidak ada tempat kosong/ padding lagi), maka akan dilakukan reorganisasi track dengan membentuk track baru.Tentu, track baru itu di luar prime data file-nya, yaitu di overflow data area-nya.
Ada dua pendekatan dasar dalam menyusun organisasi berkas semacam ini, yaitu (1) blok index dan data, dan (2) prime dan overflow data area. Untuk cara pertama, kita menyusun data dengan lebih memperhatikan ke data yang bersifat logik, bukan fisik. Jadi, data dan index diorganisasikan ke dalam blok-blok. Blok-blok index (daftar isi dalam buku kamus) diorganisasi secara sequential (consecutive) dan bertingkat-tingkat (misal setiap blok hanya berisi 4 record index yang berisi key field dan pointer). Setiap tingkat akan menuju ke blok data (misal setiap blok hanya berisi 5 record data) di tingkat selanjutnya dan seterusnya menuju ke blok data yang akan mendapatkan record yang dicari secara direct (lihat skema di buku referensi hal. 60).
Bila dilakukan penyisipan data dan blok tertentu (tempat data baru itu) sudah penuh (tidak ada tempat kosong/ padding lagi), maka akan dilakukan reorganisasi blok dengan membentuk blok baru.Tentu, mungkin saja perubahan ini akan berdampak pada isi blok index-nya.
Pendekatan kedua adalah dengan lebih memperhatikan aspek karakteristik dari hardware (fisik) alat penyimpanan datanya. Biasanya disimpan di hard disk yang memiliki cylinder dan track. Caranya hampir sama dengan cara di pendekatan pertama, hanya di sini lebih ditekankan pada aspek fisik. Jadi, yang bertingkat-tingkat adalah cylender-nya dan blok datanya ditulis secara consecutive di setiap track (misalkan 1 cylinder berisi 4 track, nomor 0 sampai 3). Index (pencarian data) tertinggi disebut dengan master index, dari master index berturut-turut menuju ke blok-blok index tingkat berikutnya hingga meraih record data yang berada di track-nya.
Bila dilakukan penyisipan data dan track tertentu (tempat data baru itu) sudah penuh (tidak ada tempat kosong/ padding lagi), maka akan dilakukan reorganisasi track dengan membentuk track baru.Tentu, track baru itu di luar prime data file-nya, yaitu di overflow data area-nya.
FILE
ORGANIZATION : MULTI KEY
Selain
organisasi berkas sequential, relative, dan index sequential yang telah dibahas
sebelumnya, berikut akan dibahas mengenai organisasi berkas multi key. Inti
dari organisasi berkas ini adalah, sebuah berkas (file) harus dapat diakses
secara langsung (direct) dari berbagai kunci atribut (key field) yang ditentukan.
Misalkan file MAHASISWA yang berisi biodata mahasiswa, harus bisa dicari record data seorang mahasiswa berdasarkan NPMnya, atau NAMAnya atau mungkin ALAMATnya. Organisasi berkas seperti ini sangat diperlukan karena berbagai user akan membutuhkan data yang sama dengan cara pandang yang berbeda. Sayangnya, jarang software database yang bisa melakukan hal ini (menyediakan fasilitas pengorganisasian berkasnya secara multi key).
Ada banyak cara untuk mengorganisasi berkas semacam ini, misalkan dengan cara (1) inversion, dan (2) multi-list. Cara inversion mirip dengan organisasi relative yang satu tabel index-nya berisi key field yang terurut dan sebuah pointer yang menunjuk ke alamat di mana data disimpan. Bedanya, karena di sini dibutuhkan banyak kunci, maka di tabel tersebut disimpan pula kunci-kunci atribut lainnya yang dibutuhkan.
Cara kedua (multi-list) hampir sama dengan cara pertama, yaitu dibuat tabel index yang terurut key field-nya dan penunjuk ke nomor record (pertama) datanya, hanya di setiap record ditambahkan pointer (penunjuk) ke record-record berikutnya sesuai urutan key field yang ditentukannya. Tentu penunjuk itu akan berubah datanya bila akses dilakukan dengan key field lainnya.
Misalkan file MAHASISWA yang berisi biodata mahasiswa, harus bisa dicari record data seorang mahasiswa berdasarkan NPMnya, atau NAMAnya atau mungkin ALAMATnya. Organisasi berkas seperti ini sangat diperlukan karena berbagai user akan membutuhkan data yang sama dengan cara pandang yang berbeda. Sayangnya, jarang software database yang bisa melakukan hal ini (menyediakan fasilitas pengorganisasian berkasnya secara multi key).
Ada banyak cara untuk mengorganisasi berkas semacam ini, misalkan dengan cara (1) inversion, dan (2) multi-list. Cara inversion mirip dengan organisasi relative yang satu tabel index-nya berisi key field yang terurut dan sebuah pointer yang menunjuk ke alamat di mana data disimpan. Bedanya, karena di sini dibutuhkan banyak kunci, maka di tabel tersebut disimpan pula kunci-kunci atribut lainnya yang dibutuhkan.
Cara kedua (multi-list) hampir sama dengan cara pertama, yaitu dibuat tabel index yang terurut key field-nya dan penunjuk ke nomor record (pertama) datanya, hanya di setiap record ditambahkan pointer (penunjuk) ke record-record berikutnya sesuai urutan key field yang ditentukannya. Tentu penunjuk itu akan berubah datanya bila akses dilakukan dengan key field lainnya.
SORT
dan MERGE FILE
Banyak
kebutuhan agar data harus diurut (sort), yang paling sederhana adalah ketika
kita akan mencetak absensi mahasiswa. Jika data dicetak tanpa diurut, maka akan
dibutuhkan waktu yang lebih lama bagi mahasiswa untuk mencari datanya di lembar
absensinya. Padahal, sewaktu memasukkan data ke komputer dulu, kecil
kemungkinan data diurut terlebih dulu secara manual karena data calon mahasiswa
yang membayar uang kuliah dan menjadi mahasiswa juga tidak urut abjad.
Sortir yang dilakukan di komputer jaman sekarang umumnya cukup dilakukan di dalam memori utama komputer (internal sort), sedangkan pada masa lalu, sortir dilakukan sebagian-sebagian dengan bantuan memori sekunder (sebagai penampung sementara) sebelum akhirnya semua akan (di-merge) dan direkam ke memori sekunder itu.
Faktor-faktor yang mempengaruhi metode eksternal sort adalah : (1) jumlah record yang akan akan disortir, (2) ukuran (panjang) record, (3) jumlah storage yang digunakan, (4) kapasitas memori internal, dan (5) distribusi nilai key dalam input file. Berbagai macam teknik sort/ merge file adalah (a) natural merge, (2) balanced merge, (3) polyphase merge, dan (4) cascade merge.
Sortir yang dilakukan di komputer jaman sekarang umumnya cukup dilakukan di dalam memori utama komputer (internal sort), sedangkan pada masa lalu, sortir dilakukan sebagian-sebagian dengan bantuan memori sekunder (sebagai penampung sementara) sebelum akhirnya semua akan (di-merge) dan direkam ke memori sekunder itu.
Faktor-faktor yang mempengaruhi metode eksternal sort adalah : (1) jumlah record yang akan akan disortir, (2) ukuran (panjang) record, (3) jumlah storage yang digunakan, (4) kapasitas memori internal, dan (5) distribusi nilai key dalam input file. Berbagai macam teknik sort/ merge file adalah (a) natural merge, (2) balanced merge, (3) polyphase merge, dan (4) cascade merge.
NATURAL
MERGE
M-natural
merge adalah sebanyak m input file yang akan disortir/ merge untuk menghasilkan
1 buah output file yang sudah terurut. Contoh, untuk mengurut 6000 record data
tetapi memori utama komputernya hanya dapat menampung 2000 record, maka file
tersebut akan dijadikan 3 input file (3-way natural merge) yang akhirnya
kembali disimpan menjadi sebuah output file yang sudah terurut.
BALANCE
MERGE
Balance
merge hampir sama dengan natural merge, namun kondisi awalnya adalah banyaknya
input file seimbang dengan banyaknya output file (m-way balance merge berarti
m-input file dan m-output file), meskipun pada akhirnya tidak demikian.
POLYPHASE
MERGE
Polyphase
merge merupakan teknik perbaikan dari balance merge dengan cara memanfaatkan
file yang nganggur (idle) ketika dilakukan merge. Pada m-polyphase merge
digunakan 2m-1 input file dan 1 output file.
CASCADE
MERGE
Cascade
merge merupakan teknik merge yang selalu mengurangi 1 file input pada setiap
tahapnya. Jadi, jika digunakan m-way cascade merge, maka file input yang
digunakan adalah 2m-1, kemudian 2m-2, 2m-3, dan seterusnya hingga bernilai 2
input file.
{Contoh-contoh
skemanya dapat dilihat di buku referensi halaman 86 sampai 91}.
BEBERAPA
ISTILAH DALAM SISTEM OPERASI
YANG TERKAIT DENGAN SISTEM BERKAS
YANG TERKAIT DENGAN SISTEM BERKAS
Kita
(programmer) tidak dapat berbuat apa-apa tanpa adanya sistem operasi di
komputer. Sistem operasi membantu kita untuk mengontrol alat-alat (devices) komputer
agar bekerja dengan baik. Misalkan, kita minta ”SAVE” data atau ”WRITE” data
kita ke disket, maka sistem operasi akan membuka jalur transportasi (pathway)
data dari hard disk ke memori utama dan dilanjutkan ke disket. Bukan itu saja,
jika kita minta ”PRINT” maka sistem operasi mengaktifkan printer dan melakukan
”READ” data yang akan dicetak dari alat penyimpanannya dan kembali ”mengangkut”
data tersebut hingga akhirnya ke printer, dan sebagainya.
Beberapa istilah dalam sistem operasi antara lain :
Beberapa istilah dalam sistem operasi antara lain :
(1)
Supervisor I/O : adalah bagian dari sistem operasi yang mengontrol peralatan
input/ output (I/O) komputer
(2) File manager : adalah bagian dari sistem operasi yang bertugas untuk mengatur pemberkasan di dalam alat-alat penyimpanan data di komputer.
(3) Device manager : adalah bagian dari sistem operasi yang bertugas untuk mengatur alat-alat (piranti-piranti) yang ada di dalam konfigurasi komputernya.
(4) I/O channel : adalah prosesor yang telah diprogram untuk mengakses peralatan yang dibutuhkan dan mengontrol jalur data.
(5) Selector channel : mengatur aliran data antara memori utama dengan peralatan lain seperti disk (peralatan dengan kecepatan tinggi).
(6) Multiplexer channel : mengatur aliran data antara memori utama dengan peralatan-peralatan lain seperti printer, magnetic tape, dsb. (peralatan dengan kecepatan rendah).
(7) Block multiplexer channel : mengatur aliran data ke berbagai peralatan.
(8) Dedicated device : peralatan yang hanya dapat digunakan oleh seorang pemakai dalam satu saat.
(9) Shared device : peralatan yang bisa digunakan oleh satu atau lebih pemakai dalam satu saat (waktu yang bersamaan)
(10) Spooling : dukungan peralatan virtual I/O yang biasanya digunakan di komputer multiuser. Misalkan 10 orang user akan mencetak ke sebuah printer dalam waktu bersamaan, maka spooling dapat menampung antrean mana urutan yang akan dicetak terlebih dulu dan mana yang kemudian.
(11) Buffer : adalah bagian dari CPU yang bertugas untuk menampung data sementara dari dan/ atau ke main memory. Contoh, ketika kita ’membakar (burn)’ CD data, maka data yang ada di disk akan ditampung ke buffer terlebih dulu sebelum ditulis ke CD.
(12) Single buffering : (buffer tunggal), jika kita memiliki data sebesar 1MB yang akan dicetak dan buffer hanya dapat menampung 256KB, maka data 1MB tersebut diletakkan ke buffer sebesar 256KB dulu, baru dicetak hingga selesai 256KB itu, kemudian data diambil kembali untuk mengisi buffer itu, dan seterusnya.
(13). Anticipatory buffering : pada (12) ada waktu tunggu antara pencetakan isi buffer hingga buffer kosong dengan pengisian kembali buffer itu. Karenanya, sistem kontrol I/O dibuat sedemikian rupa sehingga sebelum buffer sampai benar-benar kosong sudah dimuat lagi dengan data yang baru.
(14) Double buffering : (buffer ganda), digunakan untuk meniadakan waktu tunggu seperti di single buffer, karena, ketika isi dari buffer 1 dicetak, buffer 2 diisi data. Ketika buffer 1 selesai dicetak, maka ia akan diisi data, sementara isi buffer 2 mulai dicetak. Demikian seterusnya.
(15) Multiple buffering : untuk mengantisipasi kemungkinan pengisian buffer kalah cepat dengan pengosongan buffer sehingga diharapkan tidak ada waktu tunggu yang kemungkinan masih ada di (14).
(2) File manager : adalah bagian dari sistem operasi yang bertugas untuk mengatur pemberkasan di dalam alat-alat penyimpanan data di komputer.
(3) Device manager : adalah bagian dari sistem operasi yang bertugas untuk mengatur alat-alat (piranti-piranti) yang ada di dalam konfigurasi komputernya.
(4) I/O channel : adalah prosesor yang telah diprogram untuk mengakses peralatan yang dibutuhkan dan mengontrol jalur data.
(5) Selector channel : mengatur aliran data antara memori utama dengan peralatan lain seperti disk (peralatan dengan kecepatan tinggi).
(6) Multiplexer channel : mengatur aliran data antara memori utama dengan peralatan-peralatan lain seperti printer, magnetic tape, dsb. (peralatan dengan kecepatan rendah).
(7) Block multiplexer channel : mengatur aliran data ke berbagai peralatan.
(8) Dedicated device : peralatan yang hanya dapat digunakan oleh seorang pemakai dalam satu saat.
(9) Shared device : peralatan yang bisa digunakan oleh satu atau lebih pemakai dalam satu saat (waktu yang bersamaan)
(10) Spooling : dukungan peralatan virtual I/O yang biasanya digunakan di komputer multiuser. Misalkan 10 orang user akan mencetak ke sebuah printer dalam waktu bersamaan, maka spooling dapat menampung antrean mana urutan yang akan dicetak terlebih dulu dan mana yang kemudian.
(11) Buffer : adalah bagian dari CPU yang bertugas untuk menampung data sementara dari dan/ atau ke main memory. Contoh, ketika kita ’membakar (burn)’ CD data, maka data yang ada di disk akan ditampung ke buffer terlebih dulu sebelum ditulis ke CD.
(12) Single buffering : (buffer tunggal), jika kita memiliki data sebesar 1MB yang akan dicetak dan buffer hanya dapat menampung 256KB, maka data 1MB tersebut diletakkan ke buffer sebesar 256KB dulu, baru dicetak hingga selesai 256KB itu, kemudian data diambil kembali untuk mengisi buffer itu, dan seterusnya.
(13). Anticipatory buffering : pada (12) ada waktu tunggu antara pencetakan isi buffer hingga buffer kosong dengan pengisian kembali buffer itu. Karenanya, sistem kontrol I/O dibuat sedemikian rupa sehingga sebelum buffer sampai benar-benar kosong sudah dimuat lagi dengan data yang baru.
(14) Double buffering : (buffer ganda), digunakan untuk meniadakan waktu tunggu seperti di single buffer, karena, ketika isi dari buffer 1 dicetak, buffer 2 diisi data. Ketika buffer 1 selesai dicetak, maka ia akan diisi data, sementara isi buffer 2 mulai dicetak. Demikian seterusnya.
(15) Multiple buffering : untuk mengantisipasi kemungkinan pengisian buffer kalah cepat dengan pengosongan buffer sehingga diharapkan tidak ada waktu tunggu yang kemungkinan masih ada di (14).
Tambahan
istilah :
(1)
completely inverted file adalah file yang memiliki index inversi untuk setiap
fieldnya
(2) partialy inverted file adalah file yang minimal satu fieldnya memiliki index inversi
(3) primary key adalah atribut (field) yang dipilih untuk menentukan struktur storage pada organisasi file multi key, adapun key lainnya disebut dengan secondary key.
(4) head switching : waktu yang dibutuhkan untuk head dari hard disk ke track dan permukaan yang tepat.
(5) seek time : waktu yang digunakan untuk menggerakkan tangkai penghubung head dari hard disk ke posisi silinder yang tepat.
(6) parity check : sebuah track dalam tape yang digunakan untuk menyimpan kesalahan data
(7) hit ratio : perbandingan antara banyaknya record yang akan diakses dengan banyaknya record dalam sebuah file. Semakin tinggi nilainya, semakin baik sequential digunakan.
(2) partialy inverted file adalah file yang minimal satu fieldnya memiliki index inversi
(3) primary key adalah atribut (field) yang dipilih untuk menentukan struktur storage pada organisasi file multi key, adapun key lainnya disebut dengan secondary key.
(4) head switching : waktu yang dibutuhkan untuk head dari hard disk ke track dan permukaan yang tepat.
(5) seek time : waktu yang digunakan untuk menggerakkan tangkai penghubung head dari hard disk ke posisi silinder yang tepat.
(6) parity check : sebuah track dalam tape yang digunakan untuk menyimpan kesalahan data
(7) hit ratio : perbandingan antara banyaknya record yang akan diakses dengan banyaknya record dalam sebuah file. Semakin tinggi nilainya, semakin baik sequential digunakan.
