DBMS - Hashing
Untuk struktur database yang besar, hampir tidak mungkin untuk mencari semua nilai indeks melalui semua levelnya dan kemudian mencapai blok data tujuan untuk mengambil data yang diinginkan. Hashing adalah teknik yang efektif untuk menghitung lokasi langsung dari catatan data pada disk tanpa menggunakan struktur indeks.
Hashing menggunakan fungsi hash dengan tombol pencarian sebagai parameter untuk menghasilkan alamat rekaman data.
Organisasi Hash
Bucket- File hash menyimpan data dalam format keranjang. Bucket dianggap sebagai unit penyimpanan. Sebuah ember biasanya menyimpan satu blok disk lengkap, yang pada gilirannya dapat menyimpan satu atau lebih catatan.
Hash Function - Fungsi hash, h, adalah fungsi pemetaan yang memetakan semua kumpulan tombol pencarian Kke alamat tempat catatan aktual ditempatkan. Ini adalah fungsi dari kunci pencarian ke alamat keranjang.
Hashing Statis
Dalam pencirian statis, ketika nilai kunci pencarian diberikan, fungsi hash selalu menghitung alamat yang sama. Misalnya, jika fungsi hash mod-4 digunakan, maka itu hanya akan menghasilkan 5 nilai. Alamat keluaran harus selalu sama untuk fungsi itu. Jumlah keranjang yang disediakan tetap tidak berubah sepanjang waktu.
Operasi
Insertion - Jika sebuah record harus dimasukkan menggunakan hash statis, fungsi hash h menghitung alamat keranjang untuk kunci penelusuran K, dimana record akan disimpan.
Alamat ember = h (K)
Search - Saat record perlu diambil, fungsi hash yang sama dapat digunakan untuk mengambil alamat bucket tempat data disimpan.
Delete - Ini hanyalah pencarian yang diikuti dengan operasi penghapusan.
Bucket Overflow
Kondisi luapan ember dikenal sebagai collision. Ini adalah keadaan fatal untuk semua fungsi hash statis. Dalam hal ini, rantai luapan dapat digunakan.
Overflow Chaining- Jika keranjang penuh, keranjang baru dialokasikan untuk hasil hash yang sama dan ditautkan setelah yang sebelumnya. Mekanisme ini disebutClosed Hashing.
Linear Probing- Saat fungsi hash menghasilkan alamat di mana datanya sudah disimpan, keranjang gratis berikutnya dialokasikan untuk itu. Mekanisme ini disebutOpen Hashing.
Hashing Dinamis
Masalah dengan hashing statis adalah ia tidak meluas atau menyusut secara dinamis saat ukuran database bertambah atau menyusut. Hash dinamis menyediakan mekanisme di mana keranjang data ditambahkan dan dihapus secara dinamis dan sesuai permintaan. Hash dinamis juga dikenal sebagaiextended hashing.
Fungsi hashing, dalam hashing dinamis, dibuat untuk menghasilkan nilai dalam jumlah besar dan hanya sedikit yang digunakan pada awalnya.
Organisasi
Awalan dari seluruh nilai hash diambil sebagai indeks hash. Hanya sebagian dari nilai hash yang digunakan untuk menghitung alamat bucket. Setiap indeks hash memiliki nilai kedalaman untuk menandakan berapa banyak bit yang digunakan untuk menghitung fungsi hash. Bit ini dapat menangani ember 2n. Jika semua bit ini digunakan - yaitu, saat semua bucket penuh - maka nilai kedalaman dinaikkan secara linier dan dua kali bucket dialokasikan.
Operasi
Querying - Lihat nilai kedalaman indeks hash dan gunakan bit tersebut untuk menghitung alamat bucket.
Update - Lakukan query seperti di atas dan perbarui datanya.
Deletion - Lakukan kueri untuk menemukan data yang diinginkan dan menghapusnya.
Insertion - Hitung alamat ember
- Jika ember sudah penuh.
- Tambahkan lebih banyak ember.
- Tambahkan bit tambahan ke nilai hash.
- Hitung ulang fungsi hash.
- Lain
- Tambahkan data ke keranjang,
- Jika semua bucket penuh, lakukan perbaikan dari hashing statis.
- Jika ember sudah penuh.
Hashing tidak disukai ketika data diatur dalam beberapa urutan dan kueri membutuhkan berbagai data. Jika data bersifat diskrit dan acak, hash memiliki performa terbaik.
Algoritme hashing memiliki kompleksitas yang tinggi daripada pengindeksan. Semua operasi hash dilakukan dalam waktu yang konstan.