Hash Index Internals

The index is an array of bucket pages. To insert a key: compute a 32- or 64-bit hash, take it modulo the number of buckets, append (hash, record reference) to that bucket page. To look a key up: compute the same bucket, read the page, compare hashes (and, on a hash match, keys) until one matches or the chain ends. There is no root, no descent and no order — the address is computed, not searched.

The entry stores the hash and the locator, not necessarily the key. That makes hash indexes compact for wide keys (a 200-byte URL becomes 8 bytes) at the cost of a heap check to confirm a match, which is exactly the trade PostgreSQL makes.

A good hash function scatters neighbouring keys as far apart as possible — that is the point of it, and it is why k BETWEEN 10 AND 20, k > 100, email LIKE 'a%', ORDER BY k, MIN(k) cannot use the index. The only correct way to answer them is to read every bucket and sort the survivors, which is a full scan of the index plus a sort: never better than a sequential scan of the table, usually worse.

This also rules out prefix use of composite keys. A hash over (country, city) says nothing about country alone; the whole key must be supplied, exactly. A B+ tree on the same columns answers country = ? with a range over the leftmost prefix; see Composite Indexes and the Leftmost-Prefix Rule.

With B buckets and n entries, the expected chain length is n/B — the load factor — and the longest chain is noticeably worse. In memory, collisions are handled by Separate Chaining (a linked list per bucket) or Open Addressing (probe the next slot). On disk, chaining is the only sensible option: a full bucket page links to an overflow page, and a lookup on that bucket reads both. The overflow chain is where a hash index's O(1) quietly becomes O(chain).

Two things make chains long: a load factor allowed to climb past ~1–2 without adding buckets, and a hash function that does not scatter the actual keys — sequential integers hashed with a weak function, or a modulus that shares factors with the data. Engines use strong, cheap hashes (PostgreSQL's hash_any, murmur-style mixing) and grow buckets before the load factor gets away.

Doubling B changes hash mod B for roughly half the keys, and moving half the index in one operation is an outage at scale. Linear hashing grows one bucket at a time: it keeps a split pointer s and hashes with modulus 2B for buckets below s, B for the rest; each overflow event splits bucket s into s and s + B and advances the pointer, so no single insert pays more than one bucket rewrite. Extendible hashing keeps a directory of 2^d pointers into bucket pages; a full bucket splits using one more bit of the hash, and the directory doubles only when that bucket already used all d bits — the directory is small (pointers only) and the doubling touches no data.

Both keep growth incremental. The interactive shows the naive version deliberately — press Resize and count the highlighted keys that moved — because the moved set is the cost the two schemes exist to spread out.

CREATE INDEX … USING hash (col) builds a hash index whose entries are the 32-bit hash and the TID — never the key — so a match always re-checks the heap tuple. Bucket pages are allocated in power-of-two batches with linear-hashing-style incremental splits; overflow pages and bitmap pages manage chains. Before version 10 the index was not WAL-logged, so it was corrupt after a crash and absent on replicas, which earned it a warning in the manual and a reputation it has not shed.

Since 10 it is crash-safe and replicated. It is still rarely the right choice: it cannot enforce UNIQUE, cannot support multi-column keys, cannot answer ranges or ordering, and a btree on the same column is usually within a page read of it. The realistic cases are equality lookups on very wide keys (long URLs, large JSON paths) where the btree entry would be large and the tree tall.

InnoDB has no user-declared hash index. Instead the adaptive hash index (AHI) watches B+ tree lookups; when the same index and key prefix are probed repeatedly, it builds an in-memory hash from that key pattern directly to the leaf page record, so subsequent equality lookups skip the descent. It lives in the buffer pool, is rebuilt after restart, is partitioned to reduce contention, and can be switched off (innodb_adaptive_hash_index = OFF) when the workload is scan-heavy and the maintenance overhead shows up in profiles.

It is the same insight as the hash index — equality does not need order — applied as a cache over the structure that does, which is why it costs nothing in range capability.