ORGANISASI BERKAS LANGSUNG
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.
Dalam hal ini akan dibahas berbagai teknik yang dapat digunakan sebagai alternatif dalam merancang system. Khususnya dalam menentukan lokasi rekaman yang akan disimpan serta pembacaan rekaman tersebut.
Hal tersebut hanya mungkin terjadi bila bila kunci rekaman juga merupakan alamat lokasi rekaman. Dengan demikian waktu pencarian akan sangat baik, yaitu 1 probe untuk setiap rekaman yang dicari. Harus dimengerti harus tersedia 1 lokasi untuk setiap kemungkinan kunci rekaman.
Cara Untuk mengorganisasi berkas untuk pengaksesan langsung, yaitu :
1. Kunci Sebagai Alamat Rekaman Yang Unik
Untuk mendapatkan rekaman yang diasosiasikan dengan suatu kunci primer, sangat diharapkan agar proses langsung menuju ke alamat tempat rekaman dengan kunci tertentu disimpan. Hal tersebut hanya mungkin terjadi apabila kunci rekaman juga merupakan alamat lokasi rekaman. Untuk suatu aplikasi dengan rekaman berisi informasi mahasiswa, untuk tigabelas digit nomor identitas mahasiswa (atau kunci utama rekaman yang merupakan gabungan dari 4 digit kode fakultas + jurusan, 4 digit tahun angkatan + 5 digit nomor urut), maka diperlukan 9.000.000.000.000 lokasi sebagaimana diperlihatkan pada gambar dibawah ini.
Dengan demikian waktu pencarian akan sangat baik, yaitu probe 1 untuk setiap rekaman yang dicari. Namun teknik tersebut memiliki kerugian, karena diperlukan ruang yang sangat besar untuk menampung semua rekaman. Namun, pasti ada beberapa nomor yang kosong karena beberapa alasan, misalnya sudah lulus, mengundurkan diri, drop-out, cuti, dan sebagainya. Sehingga tidak semua ruang dimanfaatkan.
2. Konversi kunci rekaman menjadi satu alamat yang unik
Dilakukan untuk mengantisipasi kerugian dengan korespondensi 1-1. Terdapat beberapa formula, beberapa diantaranya.
Contoh 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.
3. Menentukan alamat dengan konversi kunci
Karena tidak sebanding antara kunci yang aktual dengan jumlah ruang kunci yang harus disediakan, maka korespondensi 1-1 tidak efisien. Jika ruang-ruang kosong bisa dieliminasi, maka akan diperoleh ruang kunci yang lebih besar dibanding ruang alamat.
Sebagai konsekuensinya, diperlukan suatu fungsi untuk memetakan cakupan nilai kunci yang lebih luas ke dalam cakupan yang lebih sempit nilai alamat. Fungsi ini dikenal dengan fungsi hash. Berikut ini adalah beberapa fungsi hash.
a) Hashing dengan kunci modulus N
Home address dicari dengan cara mencari sisa hasil bagi nilai kunci dengan suatu nilai tertentu.
f(kunci) = kunci mod N
Dengan nilai N dapat berupa 2 kemungkinan, yaitu :
– Banyaknya ruang alamat yang tersedia
– Bilangan prima terdekat yang berada di atas nilai banyaknya data, setelah itu banyaknya ruang alamat disesuaikan dengan N.
contoh soal :
N = 12 maka :
f(30) = 30 mod 12
= 5
Keuntungan fungsi ini adalah 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 kunci modulus N, rumusnya adalah :
f(kunci) = kunci mod P
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 soal :
N = 12; P=13
30 mod P = 4, diperoleh dari 30 dibagi 13 menghasilkan 2 dan menghasilkan sisa 4.
c) Hashing dengan pemotongan
Home address dicari dengan memotong nilai kunci ke jumlah digit tertentu yang lebih pendek.
Contoh soal :
Nilai NIP yang tadinya 9 digit dipotong menjadi hanya 3 digit dengan mengambil 3 nomor terakhir. Misalnya : NIP 132312090 akan memiliki home address 090 atau 90
d) Hashing dengan Lipatan
Fungsi ini akan melipat digit pada batasan yang ditentukan berdasarkan kondisi digit awal dan digit yang akan dihasilkan.
Contoh soal :
Nilai NIP yang 9 digit dibagi ke dalam 3 bagian masing-masing 3 digit, terus dilipat pada bagian-bagian tersebut. NIP 132312090.
Penjumlahan dari susunan tersebut :
2 3 1
3 1 2
0 9 0
yang dijumlahkan dan menghasilkan 633 (dengan carrier tidak diabaikan) atau 533 (mengabaikan carrier).
a) Hashing dengan pergeseran
Hashing dengan pergeseran memiliki proses yang serupa dengan hashing dengan lipatan, perbedaannya setelah ditentukan batasan, digit asli dipotong kemudian digeser dan dihitung hasil jumlahnya.
Contoh soal :
Untuk kunci yang memiliki 9 digit.
5 8 3
9 7 6
1 2 4
Yang akan menghasilkan alamat yang berbeda yaitu 572 (tanpa carry). Jika kedua hasil penjumlahan diatas diterapkan dengan menggunakan carry dan hanya tiga digit. digit yang paling kanan saja yang digunakan maka diperoleh (1)782 dan (1)683.
b) Hashing dengan pengkuadratan
Home address dicari dengan mengkuadratkan setiap digit pembentuk kunci, lalu semua hasilnya dijumlahkan.
Contoh soal :
NIP 132312090
memiliki home address = 12+32+22+32+12+22+02+92+02
= 1+9+4+9+1+4+0+81+0
= 104
c) Hashing dengan Konversi Radix
Dalam konversi radix, kunci dianggap dalam base selain 10 yang kemudian dikonversi ke dalam basis 10, misalnya kunci 5 6 7 8 dalam base 13 akan menghasilkan 12098 yang diperoleh dari :
Posisi : 3 2 1 0
5 6 7 8
(5 x 133) + (6 x 132) + (7 x 131) + (8 x 130) = 10985 + 1014 + 91 + 8
Sehingga hasilnya 12098 ketika dikonversi ke basis 10. Hasil tersebut masih dapat dikombinasi dengan fungsi hash lain (pemotongan atau lipatan) untuk mendapatkan digit alamat yang diijinkan.ORGANISASI BERKAS LANGSUNG
ORGANISASI BERKAS LANGSUNG
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.
Dalam hal ini akan dibahas berbagai teknik yang dapat digunakan sebagai alternatif dalam merancang system. Khususnya dalam menentukan lokasi rekaman yang akan disimpan serta pembacaan rekaman tersebut.
Hal tersebut hanya mungkin terjadi bila bila kunci rekaman juga merupakan alamat lokasi rekaman. Dengan demikian waktu pencarian akan sangat baik, yaitu 1 probe untuk setiap rekaman yang dicari. Harus dimengerti harus tersedia 1 lokasi untuk setiap kemungkinan kunci rekaman.
Cara Untuk mengorganisasi berkas untuk pengaksesan langsung, yaitu :
1. Kunci Sebagai Alamat Rekaman Yang Unik
Untuk mendapatkan rekaman yang diasosiasikan dengan suatu kunci primer, sangat diharapkan agar proses langsung menuju ke alamat tempat rekaman dengan kunci tertentu disimpan. Hal tersebut hanya mungkin terjadi apabila kunci rekaman juga merupakan alamat lokasi rekaman. Untuk suatu aplikasi dengan rekaman berisi informasi mahasiswa, untuk tigabelas digit nomor identitas mahasiswa (atau kunci utama rekaman yang merupakan gabungan dari 4 digit kode fakultas + jurusan, 4 digit tahun angkatan + 5 digit nomor urut), maka diperlukan 9.000.000.000.000 lokasi sebagaimana diperlihatkan pada gambar dibawah ini.
Dengan demikian waktu pencarian akan sangat baik, yaitu probe 1 untuk setiap rekaman yang dicari. Namun teknik tersebut memiliki kerugian, karena diperlukan ruang yang sangat besar untuk menampung semua rekaman. Namun, pasti ada beberapa nomor yang kosong karena beberapa alasan, misalnya sudah lulus, mengundurkan diri, drop-out, cuti, dan sebagainya. Sehingga tidak semua ruang dimanfaatkan.
2. Konversi kunci rekaman menjadi satu alamat yang unik
Dilakukan untuk mengantisipasi kerugian dengan korespondensi 1-1. Terdapat beberapa formula, beberapa diantaranya.
Contoh 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.
3. Menentukan alamat dengan konversi kunci
Karena tidak sebanding antara kunci yang aktual dengan jumlah ruang kunci yang harus disediakan, maka korespondensi 1-1 tidak efisien. Jika ruang-ruang kosong bisa dieliminasi, maka akan diperoleh ruang kunci yang lebih besar dibanding ruang alamat.
Sebagai konsekuensinya, diperlukan suatu fungsi untuk memetakan cakupan nilai kunci yang lebih luas ke dalam cakupan yang lebih sempit nilai alamat. Fungsi ini dikenal dengan fungsi hash. Berikut ini adalah beberapa fungsi hash.
a) Hashing dengan kunci modulus N
Home address dicari dengan cara mencari sisa hasil bagi nilai kunci dengan suatu nilai tertentu.
f(kunci) = kunci mod N
Dengan nilai N dapat berupa 2 kemungkinan, yaitu :
– Banyaknya ruang alamat yang tersedia
– Bilangan prima terdekat yang berada di atas nilai banyaknya data, setelah itu banyaknya ruang alamat disesuaikan dengan N.
contoh soal :
N = 12 maka :
f(30) = 30 mod 12
= 5
Keuntungan fungsi ini adalah 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 kunci modulus N, rumusnya adalah :
f(kunci) = kunci mod P
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 soal :
N = 12; P=13
30 mod P = 4, diperoleh dari 30 dibagi 13 menghasilkan 2 dan menghasilkan sisa 4.
c) Hashing dengan pemotongan
Home address dicari dengan memotong nilai kunci ke jumlah digit tertentu yang lebih pendek.
Contoh soal :
Nilai NIP yang tadinya 9 digit dipotong menjadi hanya 3 digit dengan mengambil 3 nomor terakhir. Misalnya : NIP 132312090 akan memiliki home address 090 atau 90
d) Hashing dengan Lipatan
Fungsi ini akan melipat digit pada batasan yang ditentukan berdasarkan kondisi digit awal dan digit yang akan dihasilkan.
Contoh soal :
Nilai NIP yang 9 digit dibagi ke dalam 3 bagian masing-masing 3 digit, terus dilipat pada bagian-bagian tersebut. NIP 132312090.
Penjumlahan dari susunan tersebut :
2 3 1
3 1 2
0 9 0
yang dijumlahkan dan menghasilkan 633 (dengan carrier tidak diabaikan) atau 533 (mengabaikan carrier).
a) Hashing dengan pergeseran
Hashing dengan pergeseran memiliki proses yang serupa dengan hashing dengan lipatan, perbedaannya setelah ditentukan batasan, digit asli dipotong kemudian digeser dan dihitung hasil jumlahnya.
Contoh soal :
Untuk kunci yang memiliki 9 digit.
5 8 3
9 7 6
1 2 4
Yang akan menghasilkan alamat yang berbeda yaitu 572 (tanpa carry). Jika kedua hasil penjumlahan diatas diterapkan dengan menggunakan carry dan hanya tiga digit yang paling kanan saja yang digunakan maka diperoleh (1)782 dan (1)683.
b) Hashing dengan pengkuadratan
Home address dicari dengan mengkuadratkan setiap digit pembentuk kunci, lalu semua hasilnya dijumlahkan.
Contoh soal :
NIP 132312090
memiliki home address = 12+32+22+32+12+22+02+92+02
= 1+9+4+9+1+4+0+81+0
= 104
c) Hashing dengan Konversi Radix
Dalam konversi radix, kunci dianggap dalam base selain 10 yang kemudian dikonversi ke dalam basis 10, misalnya kunci 5 6 7 8 dalam base 13 akan menghasilkan 12098 yang diperoleh dari :
Posisi : 3 2 1 0
5 6 7 8
(5 x 133) + (6 x 132) + (7 x 131) + (8 x 130) = 10985 + 1014 + 91 + 8
Sehingga hasilnya 12098 ketika dikonversi ke basis 10. Hasil tersebut masih dapat dikombinasi dengan fungsi hash lain (pemotongan atau lipatan) untuk mendapatkan digit alamat yang diijinkan.
Materi Pertemuan 5.
ORGANISASI BERKAS LANGSUNG
ORGANISASI BERKAS LANGSUNG
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.
Dalam hal ini akan dibahas berbagai teknik yang dapat digunakan sebagai alternatif dalam merancang system. Khususnya dalam menentukan lokasi rekaman yang akan disimpan serta pembacaan rekaman tersebut.
Hal tersebut hanya mungkin terjadi bila bila kunci rekaman juga merupakan alamat lokasi rekaman. Dengan demikian waktu pencarian akan sangat baik, yaitu 1 probe untuk setiap rekaman yang dicari. Harus dimengerti harus tersedia 1 lokasi untuk setiap kemungkinan kunci rekaman.
Cara Untuk mengorganisasi berkas untuk pengaksesan langsung, yaitu :
1. Kunci Sebagai Alamat Rekaman Yang Unik
Untuk mendapatkan rekaman yang diasosiasikan dengan suatu kunci primer, sangat diharapkan agar proses langsung menuju ke alamat tempat rekaman dengan kunci tertentu disimpan. Hal tersebut hanya mungkin terjadi apabila kunci rekaman juga merupakan alamat lokasi rekaman. Untuk suatu aplikasi dengan rekaman berisi informasi mahasiswa, untuk tigabelas digit nomor identitas mahasiswa (atau kunci utama rekaman yang merupakan gabungan dari 4 digit kode fakultas + jurusan, 4 digit tahun angkatan + 5 digit nomor urut), maka diperlukan 9.000.000.000.000 lokasi sebagaimana diperlihatkan pada gambar dibawah ini.
Dengan demikian waktu pencarian akan sangat baik, yaitu probe 1 untuk setiap rekaman yang dicari. Namun teknik tersebut memiliki kerugian, karena diperlukan ruang yang sangat besar untuk menampung semua rekaman. Namun, pasti ada beberapa nomor yang kosong karena beberapa alasan, misalnya sudah lulus, mengundurkan diri, drop-out, cuti, dan sebagainya. Sehingga tidak semua ruang dimanfaatkan.
2. Konversi kunci rekaman menjadi satu alamat yang unik
Dilakukan untuk mengantisipasi kerugian dengan korespondensi 1-1. Terdapat beberapa formula, beberapa diantaranya.
Contoh 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.
3. Menentukan alamat dengan konversi kunci
Karena tidak sebanding antara kunci yang aktual dengan jumlah ruang kunci yang harus disediakan, maka korespondensi 1-1 tidak efisien. Jika ruang-ruang kosong bisa dieliminasi, maka akan diperoleh ruang kunci yang lebih besar dibanding ruang alamat.
Sebagai konsekuensinya, diperlukan suatu fungsi untuk memetakan cakupan nilai kunci yang lebih luas ke dalam cakupan yang lebih sempit nilai alamat. Fungsi ini dikenal dengan fungsi hash. Berikut ini adalah beberapa fungsi hash.
a) Hashing dengan kunci modulus N
Home address dicari dengan cara mencari sisa hasil bagi nilai kunci dengan suatu nilai tertentu.
f(kunci) = kunci mod N
Dengan nilai N dapat berupa 2 kemungkinan, yaitu :
– Banyaknya ruang alamat yang tersedia
– Bilangan prima terdekat yang berada di atas nilai banyaknya data, setelah itu banyaknya ruang alamat disesuaikan dengan N.
contoh soal :
N = 12 maka :
f(30) = 30 mod 12
= 5
Keuntungan fungsi ini adalah 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 kunci modulus N, rumusnya adalah :
f(kunci) = kunci mod P
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 soal :
N = 12; P=13
30 mod P = 4, diperoleh dari 30 dibagi 13 menghasilkan 2 dan menghasilkan sisa 4.
c) Hashing dengan pemotongan
Home address dicari dengan memotong nilai kunci ke jumlah digit tertentu yang lebih pendek.
Contoh soal :
Nilai NIP yang tadinya 9 digit dipotong menjadi hanya 3 digit dengan mengambil 3 nomor terakhir. Misalnya : NIP 132312090 akan memiliki home address 090 atau 90
d) Hashing dengan Lipatan
Fungsi ini akan melipat digit pada batasan yang ditentukan berdasarkan kondisi digit awal dan digit yang akan dihasilkan.
Contoh soal :
Nilai NIP yang 9 digit dibagi ke dalam 3 bagian masing-masing 3 digit, terus dilipat pada bagian-bagian tersebut. NIP 132312090.
Penjumlahan dari susunan tersebut :
2 3 1
3 1 2
0 9 0
yang dijumlahkan dan menghasilkan 633 (dengan carrier tidak diabaikan) atau 533 (mengabaikan carrier).
a) Hashing dengan pergeseran
Hashing dengan pergeseran memiliki proses yang serupa dengan hashing dengan lipatan, perbedaannya setelah ditentukan batasan, digit asli dipotong kemudian digeser dan dihitung hasil jumlahnya.
Contoh soal :
Untuk kunci yang memiliki 9 digit.
5 8 3
9 7 6
1 2 4
Yang akan menghasilkan alamat yang berbeda yaitu 572 (tanpa carry). Jika kedua hasil penjumlahan diatas diterapkan dengan menggunakan carry dan hanya tiga digit. digit yang paling kanan saja yang digunakan maka diperoleh (1)782 dan (1)683.
b) Hashing dengan pengkuadratan
Home address dicari dengan mengkuadratkan setiap digit pembentuk kunci, lalu semua hasilnya dijumlahkan.
Contoh soal :
NIP 132312090
memiliki home address = 12+32+22+32+12+22+02+92+02
= 1+9+4+9+1+4+0+81+0
= 104
c) Hashing dengan Konversi Radix
Dalam konversi radix, kunci dianggap dalam base selain 10 yang kemudian dikonversi ke dalam basis 10, misalnya kunci 5 6 7 8 dalam base 13 akan menghasilkan 12098 yang diperoleh dari :
Posisi : 3 2 1 0
5 6 7 8
(5 x 133) + (6 x 132) + (7 x 131) + (8 x 130) = 10985 + 1014 + 91 + 8
Sehingga hasilnya 12098 ketika dikonversi ke basis 10. Hasil tersebut masih dapat dikombinasi dengan fungsi hash lain (pemotongan atau lipatan) untuk mendapatkan digit alamat yang diijinkan.ORGANISASI BERKAS LANGSUNG
ORGANISASI BERKAS LANGSUNG
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.
Dalam hal ini akan dibahas berbagai teknik yang dapat digunakan sebagai alternatif dalam merancang system. Khususnya dalam menentukan lokasi rekaman yang akan disimpan serta pembacaan rekaman tersebut.
Hal tersebut hanya mungkin terjadi bila bila kunci rekaman juga merupakan alamat lokasi rekaman. Dengan demikian waktu pencarian akan sangat baik, yaitu 1 probe untuk setiap rekaman yang dicari. Harus dimengerti harus tersedia 1 lokasi untuk setiap kemungkinan kunci rekaman.
Cara Untuk mengorganisasi berkas untuk pengaksesan langsung, yaitu :
1. Kunci Sebagai Alamat Rekaman Yang Unik
Untuk mendapatkan rekaman yang diasosiasikan dengan suatu kunci primer, sangat diharapkan agar proses langsung menuju ke alamat tempat rekaman dengan kunci tertentu disimpan. Hal tersebut hanya mungkin terjadi apabila kunci rekaman juga merupakan alamat lokasi rekaman. Untuk suatu aplikasi dengan rekaman berisi informasi mahasiswa, untuk tigabelas digit nomor identitas mahasiswa (atau kunci utama rekaman yang merupakan gabungan dari 4 digit kode fakultas + jurusan, 4 digit tahun angkatan + 5 digit nomor urut), maka diperlukan 9.000.000.000.000 lokasi sebagaimana diperlihatkan pada gambar dibawah ini.
Dengan demikian waktu pencarian akan sangat baik, yaitu probe 1 untuk setiap rekaman yang dicari. Namun teknik tersebut memiliki kerugian, karena diperlukan ruang yang sangat besar untuk menampung semua rekaman. Namun, pasti ada beberapa nomor yang kosong karena beberapa alasan, misalnya sudah lulus, mengundurkan diri, drop-out, cuti, dan sebagainya. Sehingga tidak semua ruang dimanfaatkan.
2. Konversi kunci rekaman menjadi satu alamat yang unik
Dilakukan untuk mengantisipasi kerugian dengan korespondensi 1-1. Terdapat beberapa formula, beberapa diantaranya.
Contoh 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.
3. Menentukan alamat dengan konversi kunci
Karena tidak sebanding antara kunci yang aktual dengan jumlah ruang kunci yang harus disediakan, maka korespondensi 1-1 tidak efisien. Jika ruang-ruang kosong bisa dieliminasi, maka akan diperoleh ruang kunci yang lebih besar dibanding ruang alamat.
Sebagai konsekuensinya, diperlukan suatu fungsi untuk memetakan cakupan nilai kunci yang lebih luas ke dalam cakupan yang lebih sempit nilai alamat. Fungsi ini dikenal dengan fungsi hash. Berikut ini adalah beberapa fungsi hash.
a) Hashing dengan kunci modulus N
Home address dicari dengan cara mencari sisa hasil bagi nilai kunci dengan suatu nilai tertentu.
f(kunci) = kunci mod N
Dengan nilai N dapat berupa 2 kemungkinan, yaitu :
– Banyaknya ruang alamat yang tersedia
– Bilangan prima terdekat yang berada di atas nilai banyaknya data, setelah itu banyaknya ruang alamat disesuaikan dengan N.
contoh soal :
N = 12 maka :
f(30) = 30 mod 12
= 5
Keuntungan fungsi ini adalah 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 kunci modulus N, rumusnya adalah :
f(kunci) = kunci mod P
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 soal :
N = 12; P=13
30 mod P = 4, diperoleh dari 30 dibagi 13 menghasilkan 2 dan menghasilkan sisa 4.
c) Hashing dengan pemotongan
Home address dicari dengan memotong nilai kunci ke jumlah digit tertentu yang lebih pendek.
Contoh soal :
Nilai NIP yang tadinya 9 digit dipotong menjadi hanya 3 digit dengan mengambil 3 nomor terakhir. Misalnya : NIP 132312090 akan memiliki home address 090 atau 90
d) Hashing dengan Lipatan
Fungsi ini akan melipat digit pada batasan yang ditentukan berdasarkan kondisi digit awal dan digit yang akan dihasilkan.
Contoh soal :
Nilai NIP yang 9 digit dibagi ke dalam 3 bagian masing-masing 3 digit, terus dilipat pada bagian-bagian tersebut. NIP 132312090.
Penjumlahan dari susunan tersebut :
2 3 1
3 1 2
0 9 0
yang dijumlahkan dan menghasilkan 633 (dengan carrier tidak diabaikan) atau 533 (mengabaikan carrier).
a) Hashing dengan pergeseran
Hashing dengan pergeseran memiliki proses yang serupa dengan hashing dengan lipatan, perbedaannya setelah ditentukan batasan, digit asli dipotong kemudian digeser dan dihitung hasil jumlahnya.
Contoh soal :
Untuk kunci yang memiliki 9 digit.
5 8 3
9 7 6
1 2 4
Yang akan menghasilkan alamat yang berbeda yaitu 572 (tanpa carry). Jika kedua hasil penjumlahan diatas diterapkan dengan menggunakan carry dan hanya tiga digit yang paling kanan saja yang digunakan maka diperoleh (1)782 dan (1)683.
b) Hashing dengan pengkuadratan
Home address dicari dengan mengkuadratkan setiap digit pembentuk kunci, lalu semua hasilnya dijumlahkan.
Contoh soal :
NIP 132312090
memiliki home address = 12+32+22+32+12+22+02+92+02
= 1+9+4+9+1+4+0+81+0
= 104
c) Hashing dengan Konversi Radix
Dalam konversi radix, kunci dianggap dalam base selain 10 yang kemudian dikonversi ke dalam basis 10, misalnya kunci 5 6 7 8 dalam base 13 akan menghasilkan 12098 yang diperoleh dari :
Posisi : 3 2 1 0
5 6 7 8
(5 x 133) + (6 x 132) + (7 x 131) + (8 x 130) = 10985 + 1014 + 91 + 8
Sehingga hasilnya 12098 ketika dikonversi ke basis 10. Hasil tersebut masih dapat dikombinasi dengan fungsi hash lain (pemotongan atau lipatan) untuk mendapatkan digit alamat yang diijinkan.
----------------------------------------------------------------------------------------------
Materi Pertemuan 6.
ORGANISASI BERKAS DENGAN BANYAK KEY
Organisasi berkas yang memperbolehkan record diakses oleh lebih dari satu key field. Inti dari organisasi berkas ini adalah, sebuah berkas (file) harus dapat diakses secara langsung (direct) dari berbagai kunci atribut (key field) yang ditentukan.
Contoh Organisasi Berkas dengan Banyak Key
Misalkan file MAHASISWA yang berisi biodata mahasiswa, harus bisa dicari record data seorang mahasiswa berdasarkan NPMnya, atau NAMAnya atau mungkin ALAMATnya.
Sebuah sistem perbankan yang mempunyai beberapa pemakai (user), seperti kasir, pegawai kredit, manajer cabang, pegawai bank, nasabah dan lain-lain. Semuanya memerlukan akses data yang sama dengan format record:
Adanya pemakai yang berbeda memerlukan akses record-record ini dalam cara yang berbeda.
Kasir Mengidentifikasikan record account menurut nilai ID.
Kredit Akses semua record menurut nilai OVERDRAW LIMIT atau semua record account dengan nilai NO SOSIAL SOCIATY.
Manajer Cabang Akses semua record menurut Branch dan Type.
Pegawai Bank Membuat laporan berkala untuk semua record account yang disortir berdasarkan ID.
Nasabah Memerlukan akses recordnya
dengan memberikan ID yang
dimilikinya atau kombinasi dari NAME, NO SOSIAL SOCIATY dan Type.
Satu pendekatan yang dapat mendukung semua jenis akses adalah dipunyainya banyak berkas yang berbeda. Setiap berkas diorganisasi untuk melayani satu jenis keperluan.
Maka untuk contoh sistem perbankan di atas harus ada:
File account yang organisasinya indeks sequential dengan nilai key
ID untuk melayani kasir, pegawai bank dan nasabah.
File account yang organisasinya sequential dengan record diurut menurut
OVERDRAW LIMIT untuk melayani pegawai kredit.
File account yang organisasinya relatif dengan nilai key
NO SOSIAL SOCIATY
untuk melayani pegawai kredit.
File account yang organisasinya sequential dengan record diurut menurut
GROUP-CODE untuk melayani manajer cabang.
File account yang organisasinya relatif dengan nilai key
NAME, NO SOSIAL SOCIATY dan TYPE untuk melayani nasabah.
Jadi kita mempunyai 5 file, semuanya mempunyai record yang sama. Kelima file itu hanya berbeda dalam organisasi dan cara aksesnya.metode
Metode Organisasi Berkas dengan Banyak Key
Ada banyak cara untuk mengorganisasi berkas semacam ini, yaitu dengan cara:
Inverted
Yaitu dengan cara yang 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.
Pengindekan dengan Pengalamatan tidak langsung yaitu:
1. Inversion bisa menggunakan kunci yang bukan nilai yang unik.
Seperti indeks berdasarkan kunci Kode-Group.
2. Struktur Index Inversion menggunakan Pengalamatan tidak langsung
Data Recordnya adalah:
Multi-List
File multi list mempunyai sebuah indeks untuk setiap kunci sekunder. Organisasi multi list berbeda dengan file terbalik dimana dalam indek inverse untuk sebuah nilai kunci mempunyai sebuah petunjuk untuk data record pertama dengan nilai kunci, sedangkan dalam indeks multilist untuk sebuah nilai kunci mempunyai hanya sebuah petunjuk untuk data record pertama dengan nilai kunci. Data record mempunyai sebuah penujuk untuk data record selanjutnya dengan nilai kunci dan seterusnya. Karena terdapat sebuah linked-list dari data record untuk setiap nilai dari kunci sekunder.
Contoh File data dengan struktur Multi List:
Dari Tabel Data Record di atas, dapat ditunjukkan file multi-list di bawah ini untuk kunci sekunder Kode-group. Setiap data record mempunyai tempat penunjuk untuk mengakses record selanjutnya.
Nilai kunci harus diurut, struktur indek adalah tabel dengan indirect addressing dan mempunyai hubungan data record yang disusun menurut ID secara menaik. Hasil sebuah struktur multilist adalah sebuah kunci sekunder yang mempunyai nilai unik atau tunggal. Ini berarti ada N data record maka ada N nilai kunci sekunder dalam indeks yang menunjukkan record pertama.
Suatu sifat yang menaik dari multilist bahwa indeks dapat berupa fixed length. Pendekatan multilist memberikan jenis kemampuan akses yang sama dengan pendekatan inverted file tetapi memproses dari 2 jenis file yang berbeda, sbg contoh :
a) Berapa jumlah account dengan kode grup = ‘DT001’?
b) Berapa jumlah cabang ‘NE’?
c) Daftar nilai ID untuk account dengan grup ‘DT002’?
d) Daftar nilai ID untuk account dengan tipe ‘002’?
e) Apakah ID = 198121 mempunyai account dengan tipe ‘002’?
Contoh di atas memerlukan data record dalam pengaksesannya. Agar dapat menjawab pertanyaan di atas dalam hal jumlah (seperti soal a dan b) dan setiap nilai second y dalam indeks multilist mempunyai banyak record dalam link-list di samping penunjuk untuk record pertama dan nilai kunci
Terima kasih banyak atas waktu kalian untuk pembahasan kisah hari ini. Semoga kita sehat selalu ya guys. See u 😊
Wassalamualaikum Warahmatullahi Wabarakatu.
Tidak ada komentar:
Posting Komentar