Hash vs B+ tree indexes: which one wins

Part of the free LogicWiz SQL & Databases course, Module 14: Indexes and query plans. The queries and practice run in the app on real Postgres.

A hash table finds a key in one step, a B+ tree needs three or four. So why is the B+ tree the default index in every major database, and when is a hash index the better pick?

You'll learn to

• Explain how a hash index finds a key and what it can't do
• Choose between a hash and a B+ tree index for a query
• Create a hash index in Postgres and read it in EXPLAIN
• Recognise GIN, GiST and BRIN when someone mentions them

Learn

Two ways to find a key

• A B+ tree keeps keys sorted. It finds a key by walking down 3-4 levels, and because the leaves are in order it can also do ranges (BETWEEN, >), prefixes (LIKE 'Ros%') and ORDER BY.
• A hash index runs each key through a hash function to get a bucket number, and stores the row address in that bucket. To find a key, hash it and look in one bucket: about one step. But the hash scrambles the order: buckets 17 and 18 hold unrelated keys.

So a hash index answers exactly one question: "which rows equal this value?"

B+ tree vs hash index in Postgres

A hash index: equality yes, range no

CREATE INDEX idx_orders_cust_hash ON orders USING hash (customer_id);
EXPLAIN (COSTS OFF)
SELECT * FROM orders WHERE customer_id = 42;
EXPLAIN (COSTS OFF)
SELECT * FROM orders WHERE customer_id BETWEEN 40 AND 45;
EXPLAIN (COSTS OFF)
SELECT * FROM orders ORDER BY customer_id LIMIT 5;

The equality lookup uses idx_orders_cust_hash. The range is a Seq Scan, and the ORDER BY needs a full Sort: the hash index has no order to offer. A plain CREATE INDEX … (customer_id) would serve all three.

Where hash wins: long keys

CREATE TABLE sessions (token TEXT NOT NULL);
INSERT INTO sessions
SELECT md5(g::text) || md5((g * 7)::text)
FROM generate_series(1, 30000) AS g;
CREATE INDEX idx_sessions_btree ON sessions (token);
CREATE INDEX idx_sessions_hash ON sessions USING hash (token);
SELECT pg_size_pretty(pg_relation_size('idx_sessions_btree')) AS btree,
       pg_size_pretty(pg_relation_size('idx_sessions_hash')) AS hash;

Each login token is 64 characters. The B+ tree stores every token in its leaves; the hash index stores a 4-byte code per row, so it is about a third of the size. For an integer key the B+ tree is already compact and the hash index is the bigger one. Long keys looked up only by = (session tokens, API keys, URLs) are the hash index's home ground.

So which one?

Default to the B+ tree. It does everything a hash index does, plus ranges, sorting, uniqueness and multi-column keys, and the 3-4 page reads are usually already in memory.

Pick a hash index only when all of these hold: the column is only ever compared with =, the keys are long, the table is big, and you don't need it to be UNIQUE.

Don't confuse a hash index with a Hash Join. A Hash Join builds a temporary hash table in memory while the query runs; it needs no index at all.

Other index types you may hear about

You only need to recognise these in an interview: name the type and its use case. B+ tree and hash are the two you should be able to explain inside out.

Old blog posts say "never use hash indexes in Postgres" because they were not crash-safe or replicated. That was fixed years ago; hash indexes are now safe. The real reason to avoid them is still the list above: equality only, no UNIQUE, one column.

"Hash index or B-tree?" is a common follow-up to "what is an index". A strong answer: hash gives about one-step equality lookups and smaller indexes on long keys, but no ranges, no ordering, no uniqueness; B+ tree is O(log n), handles all of those, and is the default for a reason. MySQL: InnoDB only builds B+ tree indexes (its "adaptive hash index" is an automatic in-memory cache); the MEMORY engine supports real hash indexes.

In one line

A hash index answers only =, in about one step, and is small for long keys; a B+ tree also does ranges, ORDER BY, UNIQUE and multi-column keys, so it is the default.

Interview corner

Hash index vs B+ tree index: when would you use each?

Use a B+ tree by default: it supports equality, ranges, prefix LIKE, ORDER BY, UNIQUE and multi-column keys in O(log n). Use a hash index only for pure equality lookups on long keys (tokens, URLs) where its smaller size matters; it can't do ranges, sorting or uniqueness.

Why do databases use B+ trees as the default index?

They are shallow (3-4 levels for huge tables), keep keys sorted so one structure serves equality, ranges and sorting, and stay balanced as rows are inserted and deleted. A hash index is only better for equality, and only slightly.

What are GIN, GiST and BRIN indexes?

GIN indexes the items inside a value (array elements, JSONB keys, words for full-text search). GiST handles geometric and range data, including nearest-neighbour searches. BRIN stores a min and max per block range, so it is tiny and works well on huge tables whose rows arrive in order, like time-stamped logs.