Database Indexing with Hash Tables
You'll learn how databases use hash tables to enable lightning-fast equality searches on indexed columns.
The Core Idea
When you query a database with something like SELECT * FROM users WHERE email = 'user@example.com', the database could scan every single row—slow! Instead, databases build indexes: data structures that speed up lookups. Hash tables are one powerful indexing option.
A hash-based index works just like the hash tables you've studied: the database hashes the indexed column's value (like an email address) and uses that hash to quickly locate the corresponding row(s). This provides O(1) average-case lookup for exact-match queries.
When Hash Indexes Shine
Hash indexes excel at equality comparisons:
WHERE id = 42WHERE username = 'alice'WHERE email = 'user@example.com'
They're perfect for dictionary-like lookups where you know the exact value you're searching for.
The Limitation: No Range Queries
Here's the critical tradeoff: hash functions scatter values unpredictably. Even though "alice" and "alex" are alphabetically close, their hash values could be miles apart in the table. This means hash indexes cannot efficiently handle:
- Range queries:
WHERE age BETWEEN 20 AND 30 - Sorting:
ORDER BY name - Prefix matching:
WHERE name LIKE 'A%'
For these operations, databases use tree-based indexes (like B-trees) that maintain sorted order.
Choosing Your Index Type
Think of it as choosing the right tool:
- Hash index = phone book organized by hashed names (fast exact lookup, can't browse alphabetically)
- Tree index = traditional phone book (slower exact lookup, but supports ranges and sorting)
Key Takeaway: Hash-based database indexes provide O(1) equality lookups but cannot support range queries or ordering—that's where tree-based indexes are essential.