TopolearnKnowing when hashing beats sorting (and when it can't help) clarifies how every index type is a trade-off.
A hash index applies a hash function to the key and stores row pointers in buckets addressed by that hash. A lookup computes the hash and reads one bucket, so cost doesn't grow with the size of the index the way tree depth does (though in practice B-tree depth grows very slowly too).
The price is that hashing destroys order. A hash index can answer only equality: WHERE token = '...'. It cannot do ranges, prefix matches, ORDER BY or MIN/MAX, and it usually can't enforce uniqueness or cover multiple columns.
Where they show up:
- In PostgreSQL,
CREATE INDEX ... USING hashexists and has been crash-safe since version 10. It can be smaller than a B-tree for long keys (it stores only the 4-byte hash), useful for equality lookups on long strings like URLs. Still, B-tree is the default for good reason and is rarely much slower. - MySQL InnoDB builds B-trees even if you write
USING HASH; its "adaptive hash index" is an internal cache on top of B-trees. The MEMORY engine supports real hash indexes. - Hashing is everywhere internally: hash joins build an in-memory hash table of one input, and key-value stores and distributed systems use hashing to place keys on nodes.
Rule of thumb: use B-tree unless you have measured that a hash index is smaller or faster for a pure-equality workload.
Example
CREATE TABLE short_link (id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
long_url text NOT NULL);
INSERT INTO short_link (long_url)
SELECT 'https://example.com/articles/' || md5(g::text) || '/' || repeat('x', 100)
FROM generate_series(1, 50000) g;
CREATE INDEX link_url_btree ON short_link USING btree (long_url);
CREATE INDEX link_url_hash ON short_link USING hash (long_url);
SELECT relname, pg_size_pretty(pg_relation_size(oid))
FROM pg_class WHERE relname LIKE 'link_url_%';
-- the hash index is several times smaller than the B-tree here
EXPLAIN SELECT id FROM short_link
WHERE long_url BETWEEN 'https://example.com/articles/00' AND 'https://example.com/articles/01';
-- uses the B-tree: hash indexes can't do rangesRemember
- Hash indexes support only equality lookups
- They store the hash, so they can be small for long keys
- B-tree stays the default; hashing matters more inside joins and sharding
Watch out for
- Choosing a hash index and later needing ORDER BY or range queries on the same column.