Teknik pemetaan pada organisasi berkas relatif
Kalkulasi alamat
R(nilai key) Address
R(nilai key) Address
Pemetaan tabel
R(NILAI KEY) <> ADDRESS.
Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif. Ide dasar dari kalkulasi alamat adalah mengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil alamat relative. Salah satu kelemahan dari teknik pengalamatan relative adalah ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key. Salah satu masalah dari teknik ini adalah ditemukannya alamat relative yang sama untuk nilai key yang berbeda. Seperti di bawah ini adalah maksud dari keadaan itu;
Keadaan dimana :
R(K1) = R(K2) Disebut benturan atau
K1 ¹ K2 collision
Sedangkan nilai K1 dan K2 disebut synonym.
Ket : Synonim merupakan dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.
Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif. Ide dasar dari kalkulasi alamat adalah mengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil alamat relative. Salah satu kelemahan dari teknik pengalamatan relative adalah ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key. Salah satu masalah dari teknik ini adalah ditemukannya alamat relative yang sama untuk nilai key yang berbeda. Seperti di bawah ini adalah maksud dari keadaan itu;
Keadaan dimana :
R(K1) = R(K2) Disebut benturan atau
K1 ¹ K2 collision
Sedangkan nilai K1 dan K2 disebut synonym.
Ket : Synonim merupakan dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.
Teknik-teknik yang terdapat pada kalkulasi alamat :
Dalam teknik kalkulasi terdapat macam – macamnya dan sebagai berikut;
– Scatter storage techniques
– Randomizing technique
– Key-to-address transformation methods
– Direct addressing techniques
– Hash table methods
– Hashing
Dalam teknik kalkulasi terdapat macam – macamnya dan sebagai berikut;
– Scatter storage techniques
– Randomizing technique
– Key-to-address transformation methods
– Direct addressing techniques
– Hash table methods
– Hashing
Teknik Hashing
Akan di jelaskan keuntungan dan kerugian dari teknik ini;
Keuntungan pemakaian Hashing :
– Nilai key yang sebenarnya dapat dipakai sehingga dapat di terjemahkan ke dalam sebuah alamat.
– Nilai key merupakan address space independent bila berkas direorganisasi, fungsi hash berubah tetapi nilai key tetap.
Kelemahan dati hasing :
– Distribusi nilai key yang dipakai
– Banyaknya nilai key yang dipakai relative terhadap ukuran dari ruang alamat
– Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebakan benturan
– Teknik yang dipakai untuk mengatasi benturan
Penampilan fungsi hash bergantung pada :
– Distribusi nilai key yang dipakai
– Banyaknya nilai key yang dipakai relative terhadap ukuran dari ruang alamat
– Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebabkan benturan
– Teknik yang dipakai untuk mengatasi benturan
Beberapa fungsi hash yang umum digunakan :
– Division Remainder
– Mid Square
– Folding
KEY TO ADDRESS TRANSFORMATION METHODS
Teknik yang digunakan dalam teori mengoreksi kesalahan-kode ini diterapkan untuk menyelesaikan masalah menangani file besar. dalam Pendekatan baru ini ke file menangani masalah digambarkan dengan desain khusus untuk menampilkan kelayakan. dari Efektivitas merupakan lebih lanjut diilustrasikan dengan membandingkan hasil uji yang diperoleh dari simulasi perhitungan, yang menggunakan data khas, terhadap nilai-nilai dihitung dari model yang ideal.
DIRECT ADDRESSING
Semua instruksi lain yang diperlihatkan menggunakan pengalamatan langsung, yang berarti bahwa data yang direferensikan sebenarnya disimpan dalam struktur lain – baik sebuah register atau lokasi memori.
Akan di jelaskan keuntungan dan kerugian dari teknik ini;
Keuntungan pemakaian Hashing :
– Nilai key yang sebenarnya dapat dipakai sehingga dapat di terjemahkan ke dalam sebuah alamat.
– Nilai key merupakan address space independent bila berkas direorganisasi, fungsi hash berubah tetapi nilai key tetap.
Kelemahan dati hasing :
– Distribusi nilai key yang dipakai
– Banyaknya nilai key yang dipakai relative terhadap ukuran dari ruang alamat
– Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebakan benturan
– Teknik yang dipakai untuk mengatasi benturan
Penampilan fungsi hash bergantung pada :
– Distribusi nilai key yang dipakai
– Banyaknya nilai key yang dipakai relative terhadap ukuran dari ruang alamat
– Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebabkan benturan
– Teknik yang dipakai untuk mengatasi benturan
Beberapa fungsi hash yang umum digunakan :
– Division Remainder
– Mid Square
– Folding
KEY TO ADDRESS TRANSFORMATION METHODS
Teknik yang digunakan dalam teori mengoreksi kesalahan-kode ini diterapkan untuk menyelesaikan masalah menangani file besar. dalam Pendekatan baru ini ke file menangani masalah digambarkan dengan desain khusus untuk menampilkan kelayakan. dari Efektivitas merupakan lebih lanjut diilustrasikan dengan membandingkan hasil uji yang diperoleh dari simulasi perhitungan, yang menggunakan data khas, terhadap nilai-nilai dihitung dari model yang ideal.
DIRECT ADDRESSING
Semua instruksi lain yang diperlihatkan menggunakan pengalamatan langsung, yang berarti bahwa data yang direferensikan sebenarnya disimpan dalam struktur lain – baik sebuah register atau lokasi memori.
TABEL HASH
Adalah merupakan struktur data yang menggunakan fungsi hash untuk efisien peta pengidentifikasi tertentu atau kunci (misalnya, nama-nama orang) untuk dihubungkan nilai (misalnya, nomor telepon mereka). Fungsi dari hash digunakan untuk mengubah kunci ke indeks (hash) dari array elemen (dalam slot atau ember) dimana nilai yang sesuai yang akan dicari.
Dalam banyak situasi, tabel hash ternyata lebih efisien daripada pohon pencarian atau lainnya tabel struktur lookup. Untuk alasan ini, mereka banyak digunakan di berbagai jenis komputer perangkat lunak , terutama untuk array asosiatif , pengindeksan database , cache , dan set .
Keuntungan
Keuntungan utama dari tabel hash atas struktur tabel data lainnya adalah kecepatan. Keuntungan ini lebih jelas ketika jumlah entri yang besar (ribuan atau lebih). tabel Hash dapat sangat efisien ketika jumlah maksimum entri dapat diprediksi dari sebelumnya, sehingga ember array dapat dialokasikan sekali dengan ukuran optimal dan tidak pernah diubah ukurannya.
2. Jika himpunan pasangan kunci-nilai adalah tetap dan dikenal lebih dulu sehingga insersi dan penghapusan tidak diijinkan, yang dapat mengurangi biaya rata-rata lookup pilihan hati-hati dari fungsi hash, ember ukuran meja, dan struktur data internal. Secara khusus, satu mungkin dapat menyusun fungsi hash yang tabrakan-bebas, atau bahkan sempurna.
Kerugian
1. Untuk aplikasi pengolahan string tertentu, seperti spell-checking , tabel hash mungkin kurang efisien daripada mencoba , automata terbatas , atau array Judy . Juga, jika setiap tombol diwakili oleh sejumlah kecil bit yang cukup, maka, bukan sebuah tabel hash, yang dapat menggunakan tombol langsung sebagai indeks ke array nilai.
2. Meskipun rata-rata biaya per operasi adalah konstan dan cukup kecil, dengan biaya operasi tunggal dapat cukup tinggi. Secara khusus, jika tabel hash menggunakan ukuran dinamis , penyisipan atau penghapusan operasi yang memerlukan waktu sebanding dengan jumlah entri.Hal ini dapat di katakan kelemahan yang serius secara real-time atau aplikasi interaktif.
Adalah merupakan struktur data yang menggunakan fungsi hash untuk efisien peta pengidentifikasi tertentu atau kunci (misalnya, nama-nama orang) untuk dihubungkan nilai (misalnya, nomor telepon mereka). Fungsi dari hash digunakan untuk mengubah kunci ke indeks (hash) dari array elemen (dalam slot atau ember) dimana nilai yang sesuai yang akan dicari.
Dalam banyak situasi, tabel hash ternyata lebih efisien daripada pohon pencarian atau lainnya tabel struktur lookup. Untuk alasan ini, mereka banyak digunakan di berbagai jenis komputer perangkat lunak , terutama untuk array asosiatif , pengindeksan database , cache , dan set .
Keuntungan
Keuntungan utama dari tabel hash atas struktur tabel data lainnya adalah kecepatan. Keuntungan ini lebih jelas ketika jumlah entri yang besar (ribuan atau lebih). tabel Hash dapat sangat efisien ketika jumlah maksimum entri dapat diprediksi dari sebelumnya, sehingga ember array dapat dialokasikan sekali dengan ukuran optimal dan tidak pernah diubah ukurannya.
2. Jika himpunan pasangan kunci-nilai adalah tetap dan dikenal lebih dulu sehingga insersi dan penghapusan tidak diijinkan, yang dapat mengurangi biaya rata-rata lookup pilihan hati-hati dari fungsi hash, ember ukuran meja, dan struktur data internal. Secara khusus, satu mungkin dapat menyusun fungsi hash yang tabrakan-bebas, atau bahkan sempurna.
Kerugian
1. Untuk aplikasi pengolahan string tertentu, seperti spell-checking , tabel hash mungkin kurang efisien daripada mencoba , automata terbatas , atau array Judy . Juga, jika setiap tombol diwakili oleh sejumlah kecil bit yang cukup, maka, bukan sebuah tabel hash, yang dapat menggunakan tombol langsung sebagai indeks ke array nilai.
2. Meskipun rata-rata biaya per operasi adalah konstan dan cukup kecil, dengan biaya operasi tunggal dapat cukup tinggi. Secara khusus, jika tabel hash menggunakan ukuran dinamis , penyisipan atau penghapusan operasi yang memerlukan waktu sebanding dengan jumlah entri.Hal ini dapat di katakan kelemahan yang serius secara real-time atau aplikasi interaktif.
3. Hash tabel dalam pameran umumnya miskin pemukiman referensi -yaitu, data yang akan diakses didistribusikan tampaknya secara acak di memori. Hal ini Karena tabel hash menyebabkan pola akses berupa melompat-lompat, ini dapat memicu cache mikroprosesor yang menyebabkan penundaan yang lama. struktur data seperti array, mencari dengan pencarian linear , akan lebih cepat jika meja relatif kecil dan tombol yang integer atau string singkat lainnya.
4. Tabel Hash menjadi sangat tidak efisien bila ada banyak tabrakan. Sementara itu hash distribusi yang tidak merata sangat tidak mungkin muncul secara kebetulan, seorang dengan pengetahuan dari fungsi hash mungkin dapat memberikan informasi untuk hash yang menciptakan perilaku-kasus terburuk dengan menyebabkan tabrakan yang berlebihan, yang mengakibatkan kinerja yang sangat buruk yaitu, sebuah serangan penolakan layanan . Dalam aplikasi kritis, baik universal hashing dapat digunakan atau struktur data dengan jaminan terburuk lebih baik mungkin lebih disukai.
4. Tabel Hash menjadi sangat tidak efisien bila ada banyak tabrakan. Sementara itu hash distribusi yang tidak merata sangat tidak mungkin muncul secara kebetulan, seorang dengan pengetahuan dari fungsi hash mungkin dapat memberikan informasi untuk hash yang menciptakan perilaku-kasus terburuk dengan menyebabkan tabrakan yang berlebihan, yang mengakibatkan kinerja yang sangat buruk yaitu, sebuah serangan penolakan layanan . Dalam aplikasi kritis, baik universal hashing dapat digunakan atau struktur data dengan jaminan terburuk lebih baik mungkin lebih disukai.
SCATTER STORAGE TECHNIQUES
Sebuah metode dan aparatus untuk melakukan penyimpanan dan pengambilan dalam suatu sistem penyimpanan informasi yang diungkapkan menggunakan teknik hashing. Untuk mencegah kontaminasi dari media penyimpanan dengan secara otomatis berakhir catatan, teknik pengumpulan sampah digunakan yang menghapus semua berakhir catatan di lingkungan dari penyelidikan ke dalam sistem storge data.. Lebih khususnya, masing-masing probe untuk penyisipan, pengambilan atau penghapusan merekam adalah kesempatan untuk mencari seluruh rangkaian catatan ditemukan untuk catatan berakhir dan kemudian menghapusnya dan menutup rantai.Koleksi ini sampah secara otomatis menghapus catatan kontaminasi berakhir di sekitar probe, sehingga secara otomatis decontaminating ruang penyimpanan.. Karena tidak ada kontaminasi jangka panjang dapat membangun dalam sistem ini, akan sangat berguna untuk basis data yang besar yang banyak digunakan dan yang memerlukan akses cepat disediakan oleh hashing.
RANDOMIZING TECHNIQUE
Meskipun secara historis “teknik pengacakan” manual (seperti menyeret kartu, gambar potongan kertas dari tas, memintal roulette wheel) yang umum, saat ini teknik otomatis sebagian besar digunakan. . Seperti kedua memilih sampel acak dan permutasi acak dapat dikurangi menjadi hanya memilih nomor acak, nomor acak generasi sekarang metode yang paling umum digunakan, baik hardware nomor acak generator dan nomor acak generator-pseudo .
metode pengacakan Non-algoritmik meliputi:
• Casting Yarrow batang (untuk I Ching )
• Lempar dadu
• Menggambar sedotan
• Shuffling cards Mengocok kartu
• Roulette wheels Roulette roda
• Menggambar potongan kertas atau bola dari kantong
• ” Lottery mesin “
Meskipun secara historis “teknik pengacakan” manual (seperti menyeret kartu, gambar potongan kertas dari tas, memintal roulette wheel) yang umum, saat ini teknik otomatis sebagian besar digunakan. . Seperti kedua memilih sampel acak dan permutasi acak dapat dikurangi menjadi hanya memilih nomor acak, nomor acak generasi sekarang metode yang paling umum digunakan, baik hardware nomor acak generator dan nomor acak generator-pseudo .
metode pengacakan Non-algoritmik meliputi:
• Casting Yarrow batang (untuk I Ching )
• Lempar dadu
• Menggambar sedotan
• Shuffling cards Mengocok kartu
• Roulette wheels Roulette roda
• Menggambar potongan kertas atau bola dari kantong
• ” Lottery mesin “
Pemetaan langsung
Teknik ini merupakan teknik yang sederhana untuk menerjemahkan nilai record key menjadi address. Ada 2 cara dalam pemetaan langsung :
1. Absolute Addressing (Pengalamatan Mutlak)
2. Relative Addressing (Pengalamatan Relatif)
· Pengalamatan Mutlak
R(nilai key) Address
Nilai key = alamat mutlak
Jika nilai key yang diberikan oleh pemakai program sama dengan address sebenarnya dari record tersebut pada penyimpanan sekunder. Pada waktu record tersebut disimpan, lokasi penyimpanan record (nomor silinder, nomor permukaan, nomor record) bila dipakai cylinder addressing atau (nomor sektor, nomor record) bila dipakai sector addressing harus ditentukan oleh pamakai.
Keuntungan dari pengalamatan mutlak adalah sebagai berikut :
Ø Fungsi pemetaan R sangat sederhana
Ø Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder
Kelemahannya dari pengalaman mutlak adalah sebagai berikut :
Ø Pemakai harus mengetahui dengan pasti record-record yang disimpan secara fisik
Ø Alamat mutlak adalah device dependent, perbaikan atau pengubahan device, dimana berkas berada akan mengubah nilai key
Ø Alamat mutlak adalah address space dependent, reorganisasi berkas relatif akan menyebabkan nilai key berubah.
· Pengalamatan Relatif
R(nilai key) Address
Nilai key = alamat relative
Alamat relatif dari sebuah record dalam sebuah berkas adalah urutan record tersebut dalam berkas. Sebuah berkas dengan N record mempunyai record dengan alamat relatif dari himpunan (1,2,3, …, N -2, N -1). Record yang ke I mempunyai alamat relatif I atau I – 1 (bila mulai dihitung dari 0).
Keuntungan dari pengalamatan relatif adalah Sebagai berikut:
Ø Fungsi pemetaan R sangat sederhana
Ø Nilai key dari sebuah record dapat ditentukan lokasi recordnya dalam sebuah penyimpanan sekunder tanpa memerlukan waktu proses yang berarti.
Kelemahannya adalah sebagai berikut :
Ø Alamat relatif adalah bukan device dependent
Ø Alamat relatif adalah address space dependent
Ø Terjadinya pemborosan ruanganmerupakan teknik yang sederhana untuk menerjemahkan nilai record key menjadi address. Ada 2 cara dalam pemetaan langsung :
1. Absolute Addressing (Pengalamatan Mutlak)
2. Relative Addressing (Pengalamatan Relatif)
· Pengalamatan Mutlak
R(nilai key) Address
Nilai key = alamat mutlak
Jika nilai key yang diberikan oleh pemakai program sama dengan address sebenarnya dari record tersebut pada penyimpanan sekunder. Pada waktu record tersebut disimpan, lokasi penyimpanan record (nomor silinder, nomor permukaan, nomor record) bila dipakai cylinder addressing atau (nomor sektor, nomor record) bila dipakai sector addressing harus ditentukan oleh pamakai.
Keuntungan dari pengalamatan mutlak adalah sebagai berikut :
Ø Fungsi pemetaan R sangat sederhana
Ø Tidak membutuhkan waktu lama dalam menentukan lokasi record pada penyimpanan sekunder
Kelemahannya dari pengalaman mutlak adalah sebagai berikut :
Ø Pemakai harus mengetahui dengan pasti record-record yang disimpan secara fisik
Ø Alamat mutlak adalah device dependent, perbaikan atau pengubahan device, dimana berkas berada akan mengubah nilai key
Ø Alamat mutlak adalah address space dependent, reorganisasi berkas relatif akan menyebabkan nilai key berubah.
· Pengalamatan Relatif
R(nilai key) Address
Nilai key = alamat relative
Alamat relatif dari sebuah record dalam sebuah berkas adalah urutan record tersebut dalam berkas. Sebuah berkas dengan N record mempunyai record dengan alamat relatif dari himpunan (1,2,3, …, N -2, N -1). Record yang ke I mempunyai alamat relatif I atau I – 1 (bila mulai dihitung dari 0).
Keuntungan dari pengalamatan relatif adalah Sebagai berikut:
Ø Fungsi pemetaan R sangat sederhana
Ø Nilai key dari sebuah record dapat ditentukan lokasi recordnya dalam sebuah penyimpanan sekunder tanpa memerlukan waktu proses yang berarti.
Kelemahannya adalah sebagai berikut :
Ø Alamat relatif adalah bukan device dependent
Ø Alamat relatif adalah address space dependent
Ø Terjadinya pemborosan ruangan
Pemetaan tabel
Dasar pemikiran pendekatan pencarian tabel adalah sebuah tabel atau direktori dari nilai key dan address. Untuk menemukan sebuah record dalam berkas relatif, pertama dicari dalam direktori nilai key dari record tersebut, yang akan menunjukan alamat dimana record tersebut berada dalam penyimpanan.
Gambar struktur tabel file relatif
Directory
| ||||||
Key
|
Address
|
File Relatif
|
Alamat Relatif
| |||
APE
|
I – 1
|
COW
|
1
| |||
BAT
|
N
|
ZEBRA
|
2
| |||
CAT
|
N – 1
|
.
| ||||
.
|
APE
|
I – 1
| ||||
COW
|
1
|
EEL
|
I
| |||
DOG
|
I + 1
|
DOG
|
I + 1
| |||
EEL
|
I
|
.
| ||||
.
|
CAT
|
N – 1
| ||||
ZEBRA
|
2
|
BAT
|
N
| |||
DIRECTORY
APE, I - 1
BAT, N
CAT, N - 1
COW, 1
DOG, I + 1
EEL, I
ZEBRA, 2
Data dalam direktori tersebut disusun secara urut menurut nilai key, sehingga pencarian nilai key dalam direktori lebih cepat dengan binary search dibanding sequential search. Alternatif lain, direktori dapat disusun dalam binary search tree, m-way search tree atau B-tree.
Keuntungan dari pencarian tabel
· Sebuah record dapat diakses dengan cepat, setelah nilai key dalam direktori ditentukan.
· Nilai key dapat berupa field yang mudah dimengerti seperti PART NUMBER, NPM, karena nilai key tersebut akan diterjemahkan menjadi alamat.
· Nilai key adalah address space independent, dimana reorganisasi berkas tak akan memepengaruhi nilai key, yang berubah adalah alamat dalam direktori.
Komentar
Posting Komentar