Hashing Techniques in DBMS

Hashing provides $O(1)$ average-case access to records by applying a hash function to the search key, directly computing the address (bucket) where the record is stored.

1. Static Hashing

The number of buckets is fixed at database creation.

• Hash Function: Maps the search key to a bucket number: $h(key) = key \mod N$ (where $N$ is the number of buckets).
• Collision Handling: When two keys hash to the same bucket:
  • Open Addressing: Find the next available slot (linear probing, quadratic probing).
  • Chaining (Overflow Chains): Each bucket has a linked list of overflow records.

Problem: As the database grows, all buckets overflow, and long overflow chains degrade performance to $O(n)$.

2. Dynamic Hashing (Extendible Hashing)

Solves the problem of static hashing by allowing the hash table to grow and shrink dynamically.

• Uses a directory (an array of pointers to buckets) and a global depth / local depth mechanism.
• When a bucket overflows, it is split into two buckets, and the directory is doubled if necessary.
• Only the overflowing bucket is reorganized; all other buckets remain untouched.

3. Linear Hashing

An alternative dynamic scheme that grows the hash table one bucket at a time in a round-robin fashion. No directory is needed. It uses a split pointer to track which bucket to split next.

4. Hashing vs Indexing (B+ Trees)

In practice, most modern databases default to B+ Tree indexes because they handle both equality and range queries well.