Hash Index Structure
What you'll learn: You'll understand how hash indexes physically organize data using hash functions, buckets, and key-to-location mappings.
The Internal Architecture
A hash index works like a giant filing cabinet with numbered drawers. When you want to store or find a record, you don't search sequentially—you apply a hash function to the key, which tells you exactly which drawer (bucket) to open.
Core Components
Hash Function
A mathematical function that takes your search key (like a customer ID or email) and converts it into a bucket number. For example, hash(key) = key % 1000 might map any key to one of 1,000 possible buckets.
Buckets
Storage locations on disk where records (or pointers to records) are kept. Each bucket has a fixed address and can hold multiple entries. Think of them as labeled slots in memory or disk blocks.
Key-to-Location Mapping
The process works like this:
- You provide a search key
- The hash function computes:
bucket_number = hash(key) - The index jumps directly to that bucket's disk location
- It scans entries within that bucket to find your exact record
Why This Structure Matters
Unlike B-Trees that traverse multiple levels, hash indexes offer O(1) average-case lookup—one hash computation, one disk read to the bucket. However, if multiple keys hash to the same bucket (collisions), that bucket might overflow into a linked chain of additional disk blocks, degrading performance.
The structure is simple: an array of bucket pointers, each pointing to a disk page. Compact, fast for equality searches (WHERE id = 42), but useless for range queries since nearby keys scatter across random buckets.
Key Takeaway:
Hash indexes use a hash function to map keys directly to bucket addresses on disk, enabling constant-time lookups for exact-match queries but requiring collision handling when multiple keys share the same bucket.