B Tree Indexing vs Hash Indexing

B-tree indexes serve range queries, sorting, and prefix lookups; hash indexes only do equality. For a general-purpose database index, B-tree wins decisively.

What they actually are

A B-tree (really a B+-tree in most engines) keeps keys sorted in a balanced multi-level structure, so any lookup is O(log n) and leaf nodes are linked for in-order traversal. A hash index runs the key through a hash function and parks the row pointer in a bucket, giving amortized O(1) equality lookups and nothing else. That structural difference is the whole story. The B-tree's sorted order is what lets it answer 'give me everything between X and Y', 'sort by this column', and 'find rows starting with foo'. The hash index scatters keys deliberately, so adjacency is meaningless — there is no 'next' key. One is a filing cabinet ordered alphabetically; the other is a coat check with numbered tags. Most queries want the filing cabinet, and they want it badly.

Where each one wins

Hash indexes win exactly one contest: single-key equality lookups on high-cardinality columns, where O(1) edges out O(log n) and the buckets stay in memory. Session-token lookups, cache-key tables, big join keys you only ever match exactly. That's the entire list. B-trees win everything else and tie on equality: range scans (created_at > last week), BETWEEN, ORDER BY served straight from the index, MIN/MAX, prefix LIKE 'foo%', multicolumn composites, and unique constraints. The painful part is that B-trees are so close on equality that hash's one advantage rarely shows up in a real workload. You buy a structure that can do one thing slightly faster and nothing else at all. That trade only pays off when you've profiled and you know the access pattern will never, ever change.

The real-world gotchas

In Postgres, hash indexes were genuinely dangerous before version 10 — not WAL-logged, so they didn't survive crashes or replicate. Fixed now, but they still can't be unique, can't be multicolumn, and can't back a foreign key the way you'd want. MySQL/InnoDB doesn't even let you choose: every secondary index is a B-tree, and the 'adaptive hash index' is something InnoDB builds automatically on top of B-trees when it notices a hot equality pattern. Memory engines and Redis use hashing, but that's a different layer. So in the two databases most teams actually run, hash-as-a-CREATE-INDEX-option is either a footgun-turned-niche-tool (Postgres) or simply absent (InnoDB). Reaching for a hash index is usually a sign someone read a Big-O table and not the manual.

The verdict

B-tree is the default for a reason, and the reason is that it refuses to be a one-trick structure. It answers equality nearly as fast as a hash and then keeps going — ranges, sorts, prefixes, uniqueness, composites — all from the same index you already built. Hash indexing is a scalpel for a wound you probably don't have: a measured, equality-only, high-cardinality hot path where the buckets live in RAM and the schema will never grow a range query. If you can't say that sentence out loud about your table, you want a B-tree. Don't optimize for a constant factor on point lookups while throwing away every other query shape. Build the B-tree, profile, and only reach for hash when the data — not a blog post — tells you to. It won't say it often.

Quick Comparison

Factor	B Tree Indexing	Hash Indexing
Equality lookups	O(log n), in practice nearly as fast	O(1) amortized, marginal edge
Range / BETWEEN / ORDER BY	Native — sorted leaves serve it directly	Impossible — buckets have no order
Prefix & multicolumn / unique	Supported (LIKE 'x%', composites, unique)	Single-column, equality-only, not unique
Engine support	Universal default (Postgres, InnoDB, etc.)	Niche in Postgres, absent as an option in InnoDB
Crash safety / durability	Always WAL-logged and replicated	WAL-logged only since Postgres 10

The Verdict

Use B Tree Indexing if: You want a default index that handles range scans, ORDER BY, BETWEEN, prefix LIKE, and equality — i.e. almost every workload.

Use Hash Indexing if: You have a verified, equality-only hot path on a high-cardinality column and you've measured that the hash variant actually beats B-tree.

Consider: In Postgres, hash indexes are finally WAL-logged (10+) but still can't be unique, multicolumn, or cover ORDER BY. That's a lot of giving up for a memory win you probably won't notice.

B Tree Indexing vs Hash Indexing: FAQ

Is B Tree Indexing or Hash Indexing better?

B Tree Indexing is the Nice Pick. B-tree handles equality, ranges, sorting, and prefix matching with one structure. Hash only does point lookups, breaks on ranges, and barely beats B-tree even at its one trick. Versatility wins.

When should you use B Tree Indexing?

You want a default index that handles range scans, ORDER BY, BETWEEN, prefix LIKE, and equality — i.e. almost every workload.

When should you use Hash Indexing?

You have a verified, equality-only hot path on a high-cardinality column and you've measured that the hash variant actually beats B-tree.

What's the main difference between B Tree Indexing and Hash Indexing?

B-tree indexes serve range queries, sorting, and prefix lookups; hash indexes only do equality. For a general-purpose database index, B-tree wins decisively.

How do B Tree Indexing and Hash Indexing compare on equality lookups?

B Tree Indexing: O(log n), in practice nearly as fast. Hash Indexing: O(1) amortized, marginal edge. Hash Indexing wins here.

Are there alternatives to consider beyond B Tree Indexing and Hash Indexing?

In Postgres, hash indexes are finally WAL-logged (10+) but still can't be unique, multicolumn, or cover ORDER BY. That's a lot of giving up for a memory win you probably won't notice.

The Bottom Line

B Tree Indexing wins

B-tree handles equality, ranges, sorting, and prefix matching with one structure. Hash only does point lookups, breaks on ranges, and barely beats B-tree even at its one trick. Versatility wins.

Related Comparisons