Hash Index

Back to IF3140 Sistem Basis Data

Topic

Questions/Cues

• Bagaimana cara kerja Hash Index?

• Apa itu bucket dan collision?

• Apa perbedaan Static dan Dynamic Hashing?

• Apa itu Hash File Organization?

Konsep Dasar Hash Index

Hash Index menggunakan sebuah fungsi hash untuk memetakan nilai search-key secara langsung ke sebuah “bucket”. Bucket adalah sebuah unit penyimpanan (biasanya satu blok disk) yang berisi entri-entri indeks. Berbeda dengan indeks terurut yang memerlukan penelusuran, hash index bertujuan untuk mendapatkan lokasi data dalam satu kali perhitungan. Metode ini sangat efisien untuk equality queries (misal, WHERE id = 123), tetapi tidak mendukung range queries (misal, WHERE harga > 100).

Collision dan Overflow Chaining

Collision (tabrakan) terjadi ketika fungsi hash memetakan beberapa search-key yang berbeda ke bucket yang sama. Ketika sebuah bucket menjadi penuh karena collision, bucket tambahan yang disebut overflow bucket akan digunakan. Bucket-bucket overflow ini kemudian dihubungkan dalam sebuah linked list, yang dikenal sebagai overflow chaining. Jika terjadi collision, sistem harus mencari secara sekuensial di sepanjang rantai bucket tersebut untuk menemukan record yang tepat.

Static vs. Dynamic Hashing

• Static Hashing: Jumlah bucket ditentukan di awal dan bersifat tetap. Kelemahannya adalah jika jumlah data membengkak, collision akan semakin sering terjadi dan menurunkan performa. Jika data menyusut, banyak bucket akan kosong dan membuang-buang ruang.

• Dynamic Hashing: Jumlah bucket dapat bertambah atau berkurang seiring dengan perubahan jumlah data. Ketika sebuah bucket meluap, sistem dapat mereorganisasi indeks dengan menambah jumlah bucket. Metode ini lebih fleksibel dan dapat beradaptasi, meskipun implementasinya lebih kompleks.

Hash File Organization

Serupa dengan B+-Tree File Organization, Hash File Organization adalah sebuah metode di mana fungsi hash digunakan untuk menentukan bucket (blok disk) tempat record data itu sendiri akan disimpan, bukan hanya entri indeksnya. Fungsi hash diterapkan pada search-key dari sebuah record untuk secara langsung menentukan di blok mana record tersebut harus ditempatkan.

Summary

Hash Index menggunakan fungsi hash untuk memetakan search-key secara langsung ke sebuah bucket penyimpanan, yang sangat efisien untuk pencarian kesetaraan (equality query). Ketika beberapa key dipetakan ke bucket yang sama, terjadi collision yang ditangani dengan overflow chaining. Hashing dapat bersifat Static (jumlah bucket tetap) atau Dynamic (jumlah bucket bisa berubah). Dalam Hash File Organization, fungsi hash digunakan untuk menentukan lokasi penyimpanan dari record data secara langsung.

Additional Information (Optional)

Memilih Fungsi Hash yang Baik

Kualitas sebuah hash index sangat bergantung pada fungsi hash yang digunakan. Fungsi hash yang ideal memiliki dua properti:

1. Uniform: Fungsi hash harus menyebarkan key secara merata ke semua bucket. Tidak boleh ada bucket yang cenderung menerima lebih banyak key daripada yang lain.

2. Random: Efek penyebarannya harus terlihat acak, tidak peduli distribusi asli dari nilai search-key. Bahkan jika key yang masuk cenderung berurutan (misal: 100, 101, 102), fungsi hash harus tetap menyebarkannya ke bucket yang berbeda-beda.

Kapan Hash Index Unggul?

Hash index adalah pilihan yang sangat baik untuk kolom yang sering digunakan dalam klausa WHERE dengan operator =. Contoh paling umum adalah pencarian berdasarkan primary key. Karena primary key unik, pencarian SELECT * FROM pengguna WHERE user_id = 'xyz' akan sangat cepat karena fungsi hash akan langsung menunjuk ke satu bucket spesifik. Sebaliknya, B+-Tree akan lebih unggul untuk query seperti WHERE tanggal_transaksi > '2024-01-01'.