Hash Index vs B-Tree Index: What is the Difference?
Compare hash indexes and B-tree indexes in SQL: lookup speed, range query support, and when to choose each type.
Expected Interview Answer
A hash index maps each key to a bucket via a hash function, giving O(1) average-case exact-match lookups but no support for range queries or ordering, while a B-tree index keeps keys sorted in a balanced tree, giving O(log n) lookups that also support range scans and ordered retrieval.
Because a hash function scatters keys unpredictably across buckets, a hash index cannot answer "greater than" or "between" queries efficiently — it can only tell you whether an exact key exists and where. A B-tree preserves the sort order of keys at every level, so range predicates, ORDER BY, and prefix matches on composite keys can all use the index directly. Hash indexes can be marginally faster for pure equality lookups since they avoid tree traversal, but most relational databases default to B-tree indexes because query workloads overwhelmingly need range and ordering support alongside equality.
- Hash index: fastest possible equality lookups
- B-tree index: supports range scans and ORDER BY
- B-tree supports partial matches on leading columns of a composite key
- Choosing correctly avoids full table scans for range-heavy queries
AI Mentor Explanation
A hash index is like assigning each player a locker number computed from their name through a formula, so if you know the exact name you jump straight to their locker — but the lockers are in no particular order, so you cannot ask for "every player alphabetically between Kohli and Sharma" without checking every locker. A B-tree index is like a scorebook sorted by name, where finding one player takes a few page flips, but finding every player in that alphabetical range is just reading a contiguous block of pages. The hash locker wins for one exact name; the sorted scorebook wins for any range.
Step-by-Step Explanation
Step 1
Understand hash index lookup
A hash function computes a bucket for the key, giving direct O(1) average access for exact matches only.
Step 2
Understand B-tree lookup
A balanced tree keeps keys sorted, giving O(log n) access that also preserves ordering.
Step 3
Compare range support
Hash indexes cannot serve range predicates efficiently; B-tree indexes can scan a contiguous sorted range.
Step 4
Choose based on workload
Use a hash index only for pure equality lookups on high-cardinality keys; default to B-tree otherwise.
What Interviewer Expects
- Clear statement that hash indexes support equality only, not ranges
- Understanding that B-trees preserve sort order at every level
- Awareness that most databases default to B-tree for general workloads
- A concrete example of when a hash index would be a poor choice
Common Mistakes
- Claiming hash indexes are always faster than B-trees
- Forgetting that hash indexes cannot support ORDER BY or range predicates
- Not mentioning that B-trees support prefix matches on composite keys
- Assuming every database engine supports hash indexes on every column type
Best Answer (HR Friendly)
“A hash index is great for instantly finding an exact match, like looking up one specific ID, but it cannot help with ranges or sorting because the hashed positions are scattered. A B-tree index keeps values sorted, so it handles both exact lookups and range or ordered queries, which is why most databases use B-trees by default.”
Code Example
-- Hash index: efficient for exact equality only
CREATE INDEX idx_sessions_token_hash
ON Sessions USING HASH (session_token);
SELECT * FROM Sessions WHERE session_token = 'abc123';
-- fast: O(1) average lookup
-- B-tree index: supports equality, ranges, and ordering
CREATE INDEX idx_orders_created_btree
ON Orders (created_at);
SELECT * FROM Orders
WHERE created_at BETWEEN '2026-01-01' AND '2026-01-31'
ORDER BY created_at;
-- fast: contiguous range scan via sorted leavesFollow-up Questions
- Why can a hash index not support ORDER BY?
- When would a hash index outperform a B-tree index?
- What happens to a hash index if a query uses a range predicate?
- How do hash collisions affect hash index performance?
MCQ Practice
1. Which query type does a hash index fail to serve efficiently?
Hash indexes scatter keys across buckets with no order, so range predicates require scanning every bucket instead of a contiguous read.
2. Why do most relational databases default to B-tree indexes?
Real workloads mix equality lookups with range scans and sorting, which B-trees handle natively while hash indexes cannot.
3. What is the average-case time complexity of a hash index lookup?
A well-distributed hash function computes the bucket directly, giving constant average-case lookup time for exact matches.
Flash Cards
What is a hash index good for? — Extremely fast exact-match equality lookups, on average O(1).
What can a hash index not do? — Serve range queries, ORDER BY, or prefix matches efficiently, since hashed keys have no order.
What is a B-tree index good for? — Both equality lookups and range/ordered queries, since keys stay sorted at every level.
Which index type do databases default to? — B-tree, because it handles the mixed equality-and-range workloads most applications need.