Tugas 7 Sistem Berkas

Tugas 7 Sistem Berkas
loading...

Tugas 7

Sistem Berkas

Organisasi Berkas Hashing

 

 

 

Nama : Rizky Pujian Dasa Pratama

NIM : 151051015

 

Institut Sains dan Teknologi AKPRIND Yogyakarta

Teknik Informatika

2018

Dalam sistem manajemen basis data, Ketika kita ingin mengambil data tertentu, menjadi sangat tidak efisien untuk mencari semua nilai indeks dan mencapai data yang diinginkan. Dalam situasi ini, teknik Hashing masuk ke dalam gambar.

Hashing adalah teknik yang efisien untuk secara langsung mencari lokasi data yang diinginkan pada disk tanpa menggunakan struktur indeks. Data disimpan di blok data yang alamatnya dihasilkan dengan menggunakan fungsi hash. Lokasi memori tempat penyimpanan catatan ini disebut sebagai blok data atau keranjang data.

Hash File Organization:

  • Bucket data –Keranjang data adalah lokasi memori tempat catatan disimpan. Bucket ini juga dianggap sebagai Unit Penyimpanan .
  • Hash Function –Hash function adalah fungsi pemetaan yang memetakan semua set kunci pencarian ke alamat rekaman yang sebenarnya. Umumnya, fungsi hash menggunakan kunci primer untuk menghasilkan indeks hash – alamat blok data. Fungsi hash dapat menjadi fungsi matematika sederhana untuk setiap fungsi matematika yang kompleks.
  • Hash Index– Awalan dari seluruh nilai hash diambil sebagai indeks hash. Setiap indeks hash memiliki nilai kedalaman untuk menandakan berapa banyak bit yang digunakan untuk menghitung fungsi hash. Bit ini dapat mengatasi 2n bucket. Kapan semua bit ini dikonsumsi? maka nilai kedalamannya meningkat secara linier dan dua kali lipat dari yang dialokasikan.

Hashing statis

Dalam hashing statis, ketika nilai kunci pencarian diberikan, fungsi hash selalu menghitung alamat yang sama. Sebagai contoh, jika kita ingin menghasilkan alamat untuk STUDENT_ID = 76 menggunakan fungsi hash mod (5), itu selalu menghasilkan alamat bucket yang sama 4. Tidak akan ada perubahan ke alamat bucket di sini. Oleh karena itu jumlah keranjang data dalam memori untuk hashing statis ini tetap konstan di seluruh.

Operasi

  • Penyisipan –Ketika catatan baru dimasukkan ke dalam tabel, Fungsi hash h menghasilkan alamat bucket untuk catatan baru berdasarkan kunci hashnya. K.
    Alamat bucket = h (K)
  • Pencarian –Saat catatan harus dicari, Fungsi hash yang sama digunakan untuk mengambil alamat bucket untuk catatan. Sebagai contoh, jika kita ingin mengambil seluruh catatan untuk ID 76, dan jika fungsi hash adalah mod (5) pada ID itu, alamat bucket yang dihasilkan adalah 4. Kemudian kita akan langsung mendapat alamat 4 dan mengambil seluruh catatan untuk ID 104. Di sini ID bertindak sebagai kunci hash.
  • Penghapusan –Jika kami ingin menghapus rekaman, Menggunakan fungsi hash kami akan mengambil rekaman yang seharusnya dihapus terlebih dahulu. Lalu kami akan menghapus rekaman untuk alamat itu di memori.
  • Pembaruan –Catatan data yang perlu diperbarui pertama kali dicari menggunakan fungsi hash, dan kemudian catatan data diperbarui.

Sekarang, Jika kita ingin memasukkan beberapa catatan baru ke dalam file Tapi alamat keranjang data yang dihasilkan oleh fungsi hash tidak kosong atau data sudah ada di alamat itu. Ini menjadi situasi kritis untuk ditangani. Situasi ini dalam hashing statis disebut  bucket overflow.
Bagaimana kita memasukkan data dalam kasus ini?
Ada beberapa metode yang disediakan untuk mengatasi situasi ini. Beberapa metode yang umum digunakan dibahas di bawah ini:

  1. Open Hashing
    Pada metode Open hashing, blok data berikutnya yang tersedia digunakan untuk memasukkan record baru, alih-alih menimpa yang lama. Metode ini juga disebut linear probing.

Sebagai contoh, D3 adalah catatan baru yang perlu disisipkan, fungsi hash menghasilkan alamat sebagai 105. Tapi itu sudah penuh. Jadi sistem mencari ember data yang tersedia berikutnya, 123 dan memberikan D3 ke sana.

  1. Hashing Tertutup
    Dalam metode hashing Tertutup, keranjang data baru dialokasikan dengan alamat yang sama dan dihubungkan setelah bucket data lengkap. Metode ini juga dikenal sebagai luapan overflow.
    Sebagai contoh, kita harus memasukkan catatan D3 baru ke dalam tabel. Fungsi hash statis menghasilkan alamat keranjang data sebagai 105. Tetapi keranjang ini penuh untuk menyimpan data baru. Dalam hal ini adalah bucket data baru yang ditambahkan pada akhir dari 105 data bucket dan terhubung dengannya. Kemudian D3 rekaman baru dimasukkan ke dalam ember baru.

    • Quadratic probing:
      Probing kuadrat sangat mirip dengan hashing terbuka atau probing linier. Di sini, Satu-satunya perbedaan antara keranjang lama dan baru adalah linier. Fungsi kuadrat digunakan untuk menentukan alamat bucket baru.
    • Double Hashing:
      Double Hashing adalah metode lain yang mirip dengan probing linier. Di sini perbedaannya tetap seperti pada probing linier, tetapi perbedaan tetap ini dihitung dengan menggunakan fungsi hash yang lain. Itu sebabnya namanya hashing ganda.

Hashing Dinamis

Kelemahan dari hashing statis adalah bahwa ia tidak mengembang atau menyusut secara dinamis ketika ukuran basis data bertambah atau menyusut. Dalam hashing dinamis, kumpulan data tumbuh atau menyusut (ditambahkan atau dihapus secara dinamis) saat catatan meningkat atau menurun. Hashing dinamis juga dikenal sebagai hashing diperpanjang.

Dalam hashing dinamis, fungsi hash dibuat untuk menghasilkan sejumlah besar nilai. Sebagai contoh, ada tiga catatan data D1, D2 dan D3. Fungsi hash menghasilkan tiga alamat 1001, 0101 dan 1010 masing-masing. Metode penyimpanan ini hanya mempertimbangkan sebagian dari alamat ini – terutama hanya satu bit pertama untuk menyimpan data. Jadi ia mencoba memuat tiga dari mereka di alamat 0 dan 1.

Tetapi masalahnya adalah tidak ada alamat bucket yang tersisa untuk D3. Bucket harus tumbuh secara dinamis untuk mengakomodasi D3. Jadi itu mengubah alamat memiliki 2 bit daripada 1 bit, dan kemudian memperbarui data yang ada untuk memiliki 2 alamat bit. Kemudian mencoba untuk mengakomodasi D3.

Untuk lebih lengkapnya bisa download disini : TUGAS 7 SISTEM BERKAS

loading...

 

loading...

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *