How does MySQL optimize queries differently when using B-Tree vs. HASH indexes?

How MySQL Optimizes Queries Using B-Tree vs. HASH Indexes

MySQL uses different optimization strategies depending on whether an index is a B-Tree or a HASH index. B-Tree indexes are the default for most MySQL storage engines (especially InnoDB), while HASH indexes are mainly used in MEMORY tables or internally by InnoDB for adaptive hashing.

1. How B-Tree Indexes Work

1
Stores keys in sorted order.
2
Supports equality lookups, range scans, prefix matching, and ORDER BY optimization.
3
Allows navigation to adjacent keys efficiently.
4
Used by InnoDB, MyISAM, and most other engines.

2. How HASH Indexes Work

1
Keys are converted to a hash value via a hash function.
2
Supports only equality comparisons (= or <=>).
3
Cannot be used for range queries, sorting, or prefix matches.
4
Used in MEMORY tables and InnoDB's Adaptive Hash Index (AHI).

3. Query Optimization Differences

1
B-Tree indexes allow full index scans and partial matches, enabling more optimizer strategies.
2
HASH indexes support only exact-match lookups, limiting optimizer flexibility.
3
Range conditions (>, <, BETWEEN) can only use B-Tree indexes.
4
ORDER BY and GROUP BY optimizations are possible with B-Tree, not HASH.

4. When MySQL Chooses B-Tree vs. HASH

1
B-Tree is used when:
2
• Sorting or range scans are needed.
3
• Queries rely on prefix matches.
4
• ORDER BY or GROUP BY can be optimized via index order.
5
6
HASH is used when:
7
• Queries require only fast equality lookups.
8
• Table is stored in MEMORY engine.
9
• InnoDB identifies frequently accessed B-Tree pages and builds an Adaptive Hash Index automatically.

Example: Creating a HASH Index in a MEMORY Table

5. Limitations of HASH Indexing

1
Cannot use for range queries.
2
Cannot assist with ORDER BY/GROUP BY.
3
Hash collisions cause slower lookups.
4
Not useful for prefix-based searches (LIKE 'abc%').

6. Performance Summary

1
B-Tree → best for most general-purpose queries.
2
HASH → best for fast equality comparisons on MEMORY tables or hot InnoDB pages.
3
B-Tree is more flexible; HASH is more specialized and limited.

In short, MySQL's optimizer prefers B-Tree indexes because they support more query patterns, while HASH indexes are used in special cases where high-speed equality lookup is required.

Difficulty: 6/10

Topics: B-Tree index usage, HASH index limitations, query pattern optimization

Scenario Questions

0-2 years experience

1
You're adding an index to a users table to speed up lookups by email, which is always queried with =. Should you use a HASH index? What happens if you later need to find users by email prefix, like 'john@'?
2
Your teammate added a HASH index on a date column to speed up queries filtering by exact timestamps. Now queries that find all records from last week are slow. Why?
3
You're told to index a product_id column for fast lookups. The table has 10M rows and queries only use =. Should you use a B-Tree or HASH index? What's the catch?

2-5 years experience

1
Our analytics dashboard just started timing out on user activity reports that filter by date ranges. We added a HASH index on created_at last month to speed up exact-time lookups. What went wrong, and how do you fix it?
2
A new feature queries a large logs table with both exact ID matches and partial string matches on a message field. The team added a HASH index on message. Now some queries are 10x slower. How do you diagnose and resolve this?
3
We migrated from MyISAM to InnoDB and noticed some queries got slower. We used HASH indexes in MyISAM for exact lookups. What changed, and what’s the right approach now?

5-8 years experience

1
We have a high-throughput session store using MEMORY tables with HASH indexes on session_id. We're seeing memory pressure and occasional crashes under load. How would you redesign this to be more scalable and resilient?
2
A critical API endpoint queries a 500M-row table with both exact ID lookups and range filters on timestamps. We can't afford two indexes due to write overhead. How do you decide between B-Tree and HASH, and what tradeoffs do you accept?
3
Our DBA team wants to replace all B-Tree indexes with HASH indexes on lookup-heavy tables to improve read performance. What are the hidden risks, and how would you convince them this is a bad idea at scale?

8+ years experience

1
We're migrating a legacy system that relies on HASH indexes in MEMORY tables for real-time user lookups. The system is now hitting memory limits and can't scale horizontally. How do you architect a long-term replacement that preserves low-latency lookups while supporting durability and growth?
2
A cross-team initiative wants to standardize indexing patterns across 50 microservices. Some teams use HASH indexes for exact key lookups in temporary tables, others use B-Trees. How do you define a company-wide indexing policy that balances performance, maintainability, and future-proofing?
3
We're considering switching from MySQL to PostgreSQL for better indexing flexibility. How would you evaluate whether the current reliance on HASH indexes in MySQL is a technical debt liability or a strategic advantage — and what migration path would you propose?

Follow-up Questions

❓What happens if you accidentally use a HASH index on a column you later need to filter with LIKE '%abc'?
❓How would you detect if a query is unexpectedly doing a full table scan due to index misuse?
❓Can you force MySQL to use a HASH index on an InnoDB table? Why or why not?