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.
Stores keys in sorted order.
Supports equality lookups, range scans, prefix matching, and ORDER BY optimization.
Allows navigation to adjacent keys efficiently.
Used by InnoDB, MyISAM, and most other engines.
Keys are converted to a hash value via a hash function.
Supports only equality comparisons (
=or<=>).Cannot be used for range queries, sorting, or prefix matches.
Used in MEMORY tables and InnoDB's Adaptive Hash Index (AHI).
B-Tree indexes allow full index scans and partial matches, enabling more optimizer strategies.
HASH indexes support only exact-match lookups, limiting optimizer flexibility.
Range conditions (>, <, BETWEEN) can only use B-Tree indexes.
ORDER BY and GROUP BY optimizations are possible with B-Tree, not HASH.
B-Tree is used when:
• Sorting or range scans are needed.
• Queries rely on prefix matches.
• ORDER BY or GROUP BY can be optimized via index order.
HASH is used when:
• Queries require only fast equality lookups.
• Table is stored in MEMORY engine.
• InnoDB identifies frequently accessed B-Tree pages and builds an Adaptive Hash Index automatically.
Cannot use for range queries.
Cannot assist with ORDER BY/GROUP BY.
Hash collisions cause slower lookups.
Not useful for prefix-based searches (
LIKE 'abc%').
B-Tree → best for most general-purpose queries.
HASH → best for fast equality comparisons on MEMORY tables or hot InnoDB pages.
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.