Dynamic Hash Indexes
What you'll learn: How dynamic hashing techniques like extendible hashing allow hash indexes to expand gracefully without requiring complete reorganization.
The Problem with Static Hash Indexes
Traditional hash indexes (which you've just learned) have a fixed number of buckets. When data grows beyond capacity, you face two bad options: either let buckets overflow with long chains (slowing lookups), or rebuild the entire index with more buckets (expensive and disruptive).
Dynamic Hashing to the Rescue
Dynamic hash indexes solve this by allowing the hash table to grow incrementally. The most popular technique is extendible hashing, which uses a clever directory structure.
Think of it like a phone book that starts with just area codes, but as your contact list grows, you can split sections without rewriting the entire book—just add more detailed prefixes (area code + first digit, then area code + first two digits, etc.).
How Extendible Hashing Works
Instead of hashing directly to buckets, you hash to a directory of pointers. The directory uses only the first few bits of the hash value (called the global depth). Each directory entry points to a bucket.
When a bucket overflows:
- You split just that bucket (not the entire index)
- The directory may double in size, but multiple entries can still point to the same bucket
- You use one more bit of the hash value to distinguish entries
This means growth happens locally where needed, maintaining O(1) lookup performance without full reorganization.
Real-World Benefit
Dynamic hash indexes combine the speed of hash lookups with the flexibility to handle growing datasets efficiently—perfect for databases where data volume is unpredictable.
Key Takeaway: Dynamic hash indexes like extendible hashing allow hash tables to grow incrementally by using a directory structure and bit-level hash prefixes, avoiding costly full reorganizations while preserving O(1) lookup performance.