Hash Index vs B-Tree Index: When to Use Each

A hash index maps each indexed value to a bucket using a hash function, giving near-constant-time lookups for exact matches but no ability to answer range queries — while a B-tree index keeps values in sorted order, giving slightly slower exact-match lookups but full support for ranges, sorting, and prefix matching. Most databases default to B-tree indexes for good reason, but understanding what a hash index trades away explains why that default exists.

How a hash index works

A hash index runs each key through a hash function and stores the result in a bucket, similar to how a hash table works as a general-purpose data structure. Looking up a value means hashing it and jumping straight to the bucket that would contain it — no traversal, no comparisons against a sorted structure, just a direct computation followed by (usually) one lookup.

That gives hash indexes their headline advantage: equality lookups (WHERE id = 42) are effectively O(1), independent of how large the table gets. There’s no traversal cost that grows with the number of rows, unlike a tree structure where lookup cost grows — slowly, but nonzero — with depth.

Why hash indexes can’t do ranges

The property that makes hashing fast — scattering similar values into unrelated buckets — is exactly what breaks range queries. A good hash function deliberately destroys ordering: two values that are numerically close, like 41 and 42, will typically land in completely unrelated buckets. There’s no way to ask a hash index for “everything between 40 and 50” without scanning every bucket, because the index has no concept of adjacency between keys.

The same limitation applies to sorting, prefix matching (LIKE 'app%'), and ORDER BY — anything that depends on the relative order of values is unavailable, because a hash index only knows equality.

How a B-tree index avoids that tradeoff

A B-tree keeps keys in sorted order across a balanced tree of nodes, with each node holding multiple keys and pointers to child nodes. Because the structure preserves order, a B-tree can efficiently answer:

• Equality lookups — a bit slower than a hash index since it has to traverse a few levels of the tree rather than compute one hash, but still logarithmic in the number of rows, which is fast in practice.
• Range scans — walk the sorted leaves between two bounds directly.
• Ordered retrieval — an ORDER BY on an indexed column can sometimes be satisfied by reading the index in order, avoiding a separate sort step.
• Prefix matching — a LIKE 'app%' query can use the index because matching prefixes sit next to each other in sorted order.

This versatility is why B-tree variants are the default index type in most relational databases; see how database query optimizers work for how the planner decides whether a given query can actually use an available index.

Side by side

	Hash index	B-tree index
Equality lookup (= )	O(1) average	O(log n)
Range query (BETWEEN, <, >)	Not supported	Supported
Sorted output (ORDER BY)	Not supported	Often supported directly
Prefix match (LIKE 'x%')	Not supported	Supported
Storage overhead	Generally lower	Slightly higher — internal node pointers
Common default	Rare as the default index type	Default in most relational databases

Where a hash index is actually the right call

Despite the limitations, hash indexes aren’t obsolete — they’re a narrower tool for a narrower job. They make sense when a column is queried almost exclusively by exact match, never by range or sort, and the workload is large enough that shaving lookup cost matters. Some databases expose hash indexes as an explicit option alongside B-tree, and some in-memory key-value stores use hashing internally as their only index structure, since their access pattern is pure key lookup by design.

The decision mirrors a more general one covered in composite indexes and covering indexes: index structure should follow query pattern, not the other way around. If you inspect your slow-query log and every query against a column is WHERE col = ? with nothing else, a hash index is a legitimate specialization. If there’s any chance you’ll need ranges, sorting, or partial matches later, a B-tree’s flexibility is worth its modest overhead.

A note on bitmap indexes

It’s worth distinguishing both from a bitmap index, which takes a third approach entirely — one bitmap per distinct value, efficient when a column has few possible values (like a status flag) rather than many unique ones. Hash and B-tree indexes are built for high-cardinality columns like IDs or timestamps; bitmap indexes are built for the opposite case. Picking the right index type starts with asking how many distinct values the column actually has, and how the column gets queried.

The takeaway

A hash index trades away ordering entirely in exchange for constant-time equality lookups; a B-tree keeps ordering and pays a small, logarithmic cost for it. That’s why B-tree indexes are the default almost everywhere — they handle the common case (equality) reasonably well while also supporting ranges and sorting that hash indexes simply cannot do. Reach for a hash index only when you’re certain the access pattern is pure equality lookup and you’ve confirmed your database supports it as a first-class option, not an implementation detail of something else.