Hash Index vs B-Tree: How to Choose

Choosing between a hash index and a B-tree index is a core database performance decision. This guide walks you through the key differences—equality lookups vs. range queries, memory vs. disk, and write overhead—so you can pick the right index for your workload. No prior knowledge beyond basic SQL is assumed.

What You’ll Need

A general understanding of what an index does (speeds up lookups at the cost of write performance).
Knowledge of your query patterns: are you doing exact-match lookups, range scans, or sorting?
Access to your database’s documentation to confirm which index types are supported.

Step-by-Step

List your most frequent queries. Write down the WHERE clauses, JOIN conditions, and ORDER BY columns. For each, note if it’s an equality comparison (=), a range (>, <, BETWEEN), or a sort (ORDER BY).
Check for equality-only lookups. If your queries use only = or IN on the indexed column, a hash index is a strong candidate. Hash indexes are optimized for exact matches and can be faster than B-trees for this case.
Check for range queries or sorting. If you use >, <, BETWEEN, LIKE 'prefix%', or ORDER BY, a B-tree is required. B-trees maintain data in sorted order, so they can answer range queries and produce sorted output efficiently. Hash indexes cannot do this at all.
Consider write patterns. If the indexed column is frequently updated or inserted, B-trees generally handle writes better because they are balanced and don’t require rehashing. Hash indexes can suffer from performance degradation when many collisions occur, and some implementations (like PostgreSQL’s hash index) historically had poor concurrency under heavy writes, though modern versions have improved.
Think about memory vs. disk. Hash indexes are often memory-optimized (e.g., in MySQL’s MEMORY engine) or work best when the entire index fits in RAM. B-trees are designed for disk-based storage because they minimize disk I/O by keeping the tree height low. If your index is larger than available memory, a B-tree is usually the safer choice.
Check for unique constraints. If you need to enforce uniqueness, both index types can do it, but B-trees are more commonly used for unique constraints because they also support range scans. Some databases only allow unique constraints on B-tree indexes.
Evaluate multi-column indexes. B-trees support composite indexes (multiple columns) and can use a leftmost prefix for queries. Hash indexes typically only support single-column or full multi-column equality, not prefix lookups. If you need a composite index, B-tree is usually the way to go.
Test with your actual workload. Create both indexes on a copy of your data and run EXPLAIN or EXPLAIN ANALYZE to compare execution plans and actual timings. Use realistic data volumes and query patterns.
Make the final choice. If you have a mix of query types, or if you’re unsure, default to a B-tree. It’s the most versatile and widely supported. Reserve hash indexes for the specific case where you have a high volume of equality lookups and no range queries.

Common Mistakes

Using a hash index for range queries. This will either fail or result in a full table scan, negating the index’s benefit.
Ignoring write overhead. Hash indexes can be slower for inserts/updates because rehashing or collision handling adds overhead. For write-heavy tables, a B-tree may be better.
Assuming all databases support hash indexes. MySQL’s InnoDB doesn’t support hash indexes directly (only adaptive hash indexes internally), while PostgreSQL and Microsoft SQL Server do. Check your database’s documentation.
Not considering index size. Hash indexes can be more compact than B-trees for equality lookups, but if the index doesn’t fit in memory, performance can degrade. B-trees are more predictable on disk.
Forgetting about ORDER BY. If you ever sort by the indexed column, a B-tree can avoid a sort operation. A hash index cannot.

Tips

Use B-tree for primary keys. Primary keys are often used in range scans (e.g., pagination) and are frequently the clustered index in InnoDB.
Consider a hash index for lookup tables. For small, static lookup tables where you only fetch by a code, a hash index can be very fast.
Monitor index usage. Use your database’s index usage statistics to see if an index is actually being used. If not, drop it.
Combine with other indexes. You can have both a hash and a B-tree index on the same column if you have mixed query patterns, but be aware of the extra write cost.
Read your database’s documentation. Each database has nuances—for example, PostgreSQL’s hash indexes were improved in version 10 and now support crash recovery, but they still don’t support range scans.

Troubleshooting

Query is still slow after creating a hash index. Check if the query actually uses the index with EXPLAIN. If not, the query might not be a simple equality, or the index might not be selective enough. Try a B-tree instead.

Index creation fails. Some databases don’t support hash indexes on certain data types (e.g., large text). Check the data type and database version. You may need to use a B-tree.

Performance degrades over time. If you’re using a hash index, it might be due to collisions or index bloat. Rebuild the index or consider switching to a B-tree if the workload includes any range queries.

Frequently Asked Questions

Q: Can a hash index be used for ORDER BY?
A: No. Hash indexes are not ordered, so they cannot help with sorting. Use a B-tree.

Q: Is a hash index always faster than a B-tree?
A: For exact-match lookups, a hash index can be faster because it has O(1) average time complexity, but this is only true if the index fits in memory and there are few collisions. For most workloads, the difference is negligible, and B-trees are more versatile.

Q: Which databases support hash indexes?
A: PostgreSQL, Microsoft SQL Server, and MySQL (in the MEMORY engine) support them. MySQL’s InnoDB does not support user-defined hash indexes; it uses an adaptive hash index internally.

Q: Can I use a hash index for a unique constraint?
A: Yes, but it’s uncommon. B-trees are typically used for unique constraints because they also support range queries. Check your database’s specific implementation.

Q: What about a composite index?
A: B-trees support composite indexes and can use a leftmost prefix. Hash indexes generally only support equality on the entire composite key, not partial prefixes.

Q: Should I use a hash index for a foreign key column?
A: If your queries only do equality lookups on the foreign key (e.g., fetching all orders for a customer), a hash index can work. But if you also do range queries (e.g., orders by date), a B-tree is better.

Method: the standard formula for this calculation, rounded as each result states. See how the calculators work or report an error.

More cards in this drawer

The whole Numbers and Powers drawer →