Hash Index

A fundamentally different approach

Unlike B-Tree/B+ Tree indexes (20.2, 20.3), which organize data by sorted key order, a hash index takes a completely different approach: it runs the indexed value through a hash function, which produces a number that directly identifies a bucket (a storage location). The engine stores the row's pointer in that bucket, and to look it up later, it simply re-computes the hash and jumps straight there.

Example

Suppose students.email has a hash index. Looking up:

sql
SELECT * FROM students WHERE email = 'jane.doe@example.com';

The engine computes hash('jane.doe@example.com'), gets (say) bucket #4821, jumps directly to that bucket, and finds the pointer to the matching row. There is no tree to descend, no sorted comparisons — just one hash computation and one direct jump. This gives O(1) average-case lookup for exact equality matches, which can be even faster than a B+ Tree's O(log n) tree traversal.

The critical limitation

The catch is significant: a hash function scrambles values into essentially unpredictable bucket numbers. Two values that are "close" to each other (like 3.49 and 3.50) can hash to completely unrelated, far-apart buckets. This means a hash index cannot support:

• Range queries: WHERE gpa BETWEEN 3.0 AND 3.5
• Comparison queries: WHERE gpa > 3.0
• Sorting: ORDER BY gpa
• Prefix/pattern matching: WHERE name LIKE 'Jo%'

None of these can be served by a hash index at all, because there is no notion of "nearby" values being stored near each other — only exact equality lookups are supported.

When to reach for a hash index

A hash index is the right tool specifically when a column is used only for exact-match lookups and never for ranges or sorting — for example, indexing an opaque session token, an exact status-code match, or (as above) an exact email lookup, provided the engine's query patterns never need > or ORDER BY on that column.

Edge cases

• Many real-world engines (e.g., PostgreSQL) support hash indexes but default to B-Tree/B+ Tree for most columns, precisely because most real query workloads eventually need a range or sort on the same column too.
• Hash collisions (two different values hashing to the same bucket) must be handled internally by the engine (e.g., chaining within a bucket), which can slightly degrade the "average O(1)" guarantee in pathological cases.
• A composite index (20.7) built as a hash index over multiple columns typically only supports equality on all the columns together — it generally cannot serve a leftmost-prefix-style partial match the way a composite B+ Tree index can.

Interview-style Q&A

Q: Why can't a hash index support `WHERE gpa > 3.0`? A: Because the hash function destroys the ordering relationship between values — 3.0 and 3.1 could hash to wildly different, non-adjacent buckets, so there's no way to walk from "greater than 3.0" without scanning everything.

Q: When would you choose a hash index over a B+ Tree index? A: When the column is used strictly for exact-match equality lookups and never needs range queries, comparisons, or sorting — a hash index can then offer faster average-case lookup.

Key takeaway: hash indexes trade away all ordering capability for potentially faster exact-match lookups — a narrow but sometimes valuable specialization compared to the general-purpose B+ Tree.