Database Hashing: Static vs. Dynamic Hashing (Extendible & Linear)

What is Hashing in Databases? (In Simple Words)

In tree-based indexing (like B+ Trees), finding a record requires traversing multiple levels from root to leaf, which takes multiple disk block reads.

Hashing provides direct O(1) search time (a single disk I/O read!) by using a mathematical formula called a Hash Function h(K):

• The hash function takes a primary key K (like Roll_No = 1045) as input and directly computes the physical disk address (or Bucket Number) where the record is stored!

1. Fundamental Hashing Terminology

• Bucket: A unit of disk storage (typically one disk block or cluster of blocks) that can hold multiple records.
• Hash Function h(K): A mathematical function that maps the large search key space into a fixed range of bucket numbers {0, 1, 2, ... M-1}.
  (A common simple hash function is the modulo function: h(K) = K mod M).
• Hash Collision: Occurs when two distinct search keys produce the exact same bucket address (h(K1) = h(K2)).
• Bucket Overflow: Occurs when a bucket is completely full of records and a new record hashing to that same bucket arrives.

2. Collision and Overflow Resolution in Static Hashing

In Static Hashing, the total number of buckets M is fixed during database creation. When collisions cause a bucket to overflow, one of two resolution strategies is used:

Drawbacks of Static Hashing:

1. If Database Grows Too Large: Buckets become overfilled, overflow chains become very long, and search performance degrades from O(1) down to linear O(N) scans!
2. If Database Shrinks Too Small: Large numbers of allocated disk buckets sit completely empty, causing massive wasted disk space.
3. Reorganization Penalty: Resizing the hash table requires re-hashing every single record in the entire database!

3. Dynamic Hashing (Extendible Hashing)

To overcome the rigid limitations of static hashing, Dynamic Hashing allows the number of buckets to grow and shrink dynamically as records are inserted and deleted—without requiring a full re-hash of the database!

The most prominent implementation is Extendible Hashing:

Key Concepts in Extendible Hashing:

1. Global Depth (d): The number of prefix bits from the binary hash value currently used by the directory. A global depth of d means the directory contains 2ᵈ pointer entries.
2. Local Depth (d'): Each individual physical bucket has its own local depth d' indicating that all keys in that bucket share the same d' leading bits.
3. Always: Local Depth (d') <= Global Depth (d).

How Bucket Splitting Works in Extendible Hashing:

Suppose a bucket overflows:

• Case 1: If Local Depth (d') < Global Depth (d):
  • We do NOT need to double the directory!
  • We simply allocate one new bucket on disk.
  • Increment the local depth of both buckets (d' = d' + 1).
  • Re-distribute the records of the overflowing bucket based on their d'-th bit.
  • Update the directory pointers.
• Case 2: If Local Depth (d') == Global Depth (d):
  • The directory is doubled in size (Global Depth d = d + 1).
  • Directory size jumps from 2ᵈ to 2ᵈ⁺¹.
  • The overflowing bucket is split, its local depth increments, and pointers are updated.
  • No other buckets in the system need to be modified!

4. Linear Hashing Overview

Linear Hashing is another form of dynamic hashing that allows the hash file to grow incrementally:

• Unlike Extendible Hashing, Linear Hashing does NOT require a Directory!
• Buckets are split in a systematic linear round-robin order (Bucket 0, Bucket 1, Bucket 2...) whenever the file storage utilization exceeds a defined threshold (e.g., 85%).
• Avoids the sudden directory doubling memory spikes of Extendible Hashing.

5. Comprehensive Comparison: Static vs. Dynamic Hashing

💡 DAVV Exam Preparation Tips

5-Mark Question: “What is a Hash Collision? Explain Open Addressing and Overflow Chaining resolution techniques.”

• Define hash collision (h(K1) = h(K2)).
• Explain Open Addressing / Linear Probing (finding the next sequential open slot).
• Explain Chaining (linking an overflow bucket via physical disk pointers).

10-Mark Question: “Differentiate between Static Hashing and Dynamic Hashing. Explain Extendible Hashing in detail with the concepts of Global Depth and Local Depth. Show how an overflowing bucket is split.”

• Provide the 6-point comparison table between Static and Dynamic hashing.
• Define Global Depth (d) and Local Depth (d').
• Detail the two bucket split cases (d' < d vs d' = d).
• Draw the directory and bucket diagram showing bit-prefix pointer mappings.