Hash Indexes, in depth: bucket addressing, linear and extendible hashing, PostgreSQL internals, and when a hash index beats a B-tree

From hash function to bucket

A hash index has three parts: a hash function that maps a key to a large integer, an addressing rule that maps that integer to one of N buckets, and bucket storage, usually one or more pages holding (hash or key, row pointer) entries. A lookup for token = 'abc' hashes 'abc', computes the bucket, reads that bucket's page and any overflow pages chained to it, and returns the rows whose stored hash (and, after a recheck, whose actual value) matches.

With a good hash function and a sensible load, each bucket holds a few entries and a lookup costs about one page read, regardless of table size. This is the expected O(1) cost people quote. Two things break it. If many rows share one key, they all hash to one bucket and its overflow chain grows long. And if the number of buckets stays fixed while the table grows, every bucket's chain grows with it. A static hash table needs a full rehash to grow, which is unacceptable for an index on a live table, so database hash indexes use dynamic hashing.

The hash function must also agree with the type's notion of equality. Two values that compare equal must hash identically, which is why databases attach hash support functions to data types and operator classes rather than hashing raw bytes.

Extendible hashing

Extendible hashing keeps a directory of 2 to the power d pointers, where d is the global depth, and uses the low d bits of the hash to pick a directory slot. Several slots can point to the same bucket. Each bucket has a local depth saying how many bits actually distinguish its keys. When a bucket overflows, it splits into two using one more bit; if its local depth already equals the global depth, the directory doubles first, which only copies pointers, not data.

Lookups always cost one directory access plus one bucket read, and splits touch only the overflowing bucket. The weakness is the directory: skewed hashes or many duplicates can force repeated doubling, and doubling a large directory is a pause.

Linear hashing

Linear hashing, introduced by Litwin in 1980, has no directory. It grows by splitting buckets in a fixed round-robin order, whichever bucket overflowed. The state is three numbers: the initial bucket count N, the round number L, and a split pointer next. A key's bucket is h mod (N times 2 to the L). If that bucket is below next, it has already been split this round, so the key uses h mod (N times 2 to the L plus 1) instead, which lands either in the original bucket or in its new image at the end of the table.

When the load factor passes a target, bucket next is split: half of its keys move to a new bucket appended at the end, and next advances. When next reaches N times 2 to the L, the round is over, L increases and next resets to zero. Only one bucket's keys move per split, so growth is smooth. The cost is that the bucket that overflowed may not be the one that is split, so overflow pages are a normal, expected part of the structure.

import zlib


class LinearHash:
    """Toy linear hashing: split one bucket at a time when load exceeds a target."""

    def __init__(self, n0=4, cap=4, max_load=0.75):
        self.n0, self.level, self.next = n0, 0, 0
        self.cap, self.max_load = cap, max_load
        self.buckets = [[] for _ in range(n0)]
        self.count = 0

    def _h(self, key):
        return zlib.crc32(key.encode())

    def _addr(self, h):
        b = h % (self.n0 << self.level)
        if b < self.next:                      # already split this round
            b = h % (self.n0 << (self.level + 1))
        return b

    def insert(self, key):
        self.buckets[self._addr(self._h(key))].append(key)
        self.count += 1
        if self.count / (len(self.buckets) * self.cap) > self.max_load:
            self._split()

    def _split(self):
        old = self.buckets[self.next]
        self.buckets.append([])
        self.buckets[self.next] = []
        self.next += 1
        if self.next == self.n0 << self.level:   # round finished
            self.level, self.next = self.level + 1, 0
        for k in old:                              # rehash only the split bucket
            self.buckets[self._addr(self._h(k))].append(k)

    def lookup(self, key):
        return key in self.buckets[self._addr(self._h(key))]

    def overflowing(self):
        return sum(1 for b in self.buckets if len(b) > self.cap)

Worked example: watching a linear hash grow

Insert the keys user-1 to user-2000 into the class above, with 4 initial buckets, a capacity of 4 entries per bucket (a stand-in for a page) and a target load of 75 percent. Every lookup afterwards finds its key. This is the real output of that run:

Three lessons come out of it. First, the bucket count tracks the key count almost exactly (2000 keys divided by 667 buckets of 4 is 0.75), with no pause to rebuild. Second, the longest bucket stays small, so a lookup reads the bucket page and at most a short overflow chain. Third, overflow is normal: at 2,000 keys, 145 of 667 buckets hold more than one page's worth. In the middle of a round, buckets not yet split carry keys for twice the hash range of the split ones, so they fill first and spill into overflow pages until the split pointer reaches them.

Inside a PostgreSQL hash index

PostgreSQL's hash access method is a linear-hashing design on 8 kB pages. Its documentation describes four kinds of page: the meta page (page zero) holding control information, primary bucket pages, overflow pages, and bitmap pages that track freed overflow pages for reuse. Each index tuple stores only the 4-byte hash value, not the column value, so the index size does not depend on key length and there is no limit on the size of the indexed value. The flip side is that every scan is lossy: the executor must recheck the actual value in the table row, because two different keys can share a hash code.

Growth works as in the simulator. When a bucket needs to be added, exactly one existing bucket is split, and the documentation notes that this expansion happens in the foreground, so an insert that triggers a split takes longer. VACUUM removes dead entries and squeezes tuples onto fewer overflow pages; freed overflow pages are recycled within the index but never returned to the operating system, and the number of buckets never decreases. The only way to shrink a hash index is REINDEX.

History matters because old advice lingers. Before PostgreSQL 10, hash indexes were not WAL-logged: they were not crash-safe and were not replicated to standbys, and the documentation warned against them. Since version 10 they are WAL-logged, crash-safe and replicated. Advice that hash indexes are unsafe dates from before that.

CREATE INDEX sessions_token_hash ON sessions USING hash (token);

-- Equality is the only operator a hash index can serve.
EXPLAIN (ANALYZE, BUFFERS)
SELECT user_id FROM sessions WHERE token = 'c8f1d0b2-...';

-- Size against a B-tree on the same long text column.
CREATE INDEX sessions_token_btree ON sessions (token);
SELECT relname, pg_size_pretty(pg_relation_size(oid))
FROM pg_class WHERE relname LIKE 'sessions_token_%';

-- Inspect the linear-hashing state (requires the pageinspect extension).
CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT maxbucket, highmask, lowmask, ntuples, ffactor
FROM hash_metapage_info(get_raw_page('sessions_token_hash', 0));
SELECT hash_page_type(get_raw_page('sessions_token_hash', 1));
SELECT * FROM hash_page_stats(get_raw_page('sessions_token_hash', 1));

maxbucket is the highest bucket number in use, and highmask and lowmask are the two masks used to map a hash code to a bucket, the bitmask equivalent of the two modulo operations in the simulator.

What a hash index cannot do

The PostgreSQL documentation is explicit about the limits, and most other systems share them.

• Equality only. WHERE token = $1 can use it; ranges, ORDER BY, LIKE 'abc%' and BETWEEN cannot.
• Single column only. No multicolumn hash indexes, so a query on (tenant_id, token) needs a B-tree or a hash on one column plus a filter.
• No uniqueness checking. A primary key or UNIQUE constraint needs a B-tree. If you need uniqueness on a very long value, an exclusion constraint using hash (EXCLUDE USING hash (token WITH =)) is an option, but it is checked differently from a unique index and cannot be the target of a foreign key, so test it first.
• No index-only scans. The index holds hash codes, not values, so the table row must always be visited. A B-tree can return covered columns from the index alone (index-only scans).
• Bitmap and backward scans are allowed. A hash index can be combined with other indexes in a bitmap scan.

Hash indexes in other systems

MySQL's InnoDB has no user-created on-disk hash index. It has the adaptive hash index (AHI), an in-memory hash built automatically over frequently accessed B-tree pages to shortcut the tree descent. It speeds up some read-heavy, point-lookup workloads but can become a contention point under concurrency, and in MySQL 8.4 the default of innodb_adaptive_hash_index changed from ON to OFF. Benchmark your own workload before enabling it. MySQL's MEMORY engine supports explicit USING HASH indexes.

Outside SQL, hash tables are often the primary index. Bitcask-style log stores keep an in-memory hash map from every key to its file offset, giving one disk seek per read at the cost of keeping all keys in RAM. Redis grows its main dictionary by incremental rehashing: it keeps old and new tables and moves a few buckets on each operation, which avoids a long pause, the same goal linear hashing has on disk. Do not confuse any of these with hash joins, which build a temporary hash table during one query; see Hash join.

Failure modes

• Many duplicates. Every row with the same key lands in one bucket. A hash index on a status column with five values degenerates into five long overflow chains. PostgreSQL's documentation recommends hash indexes for unique or nearly unique data.
• Bloat that never shrinks. After a large delete, the bucket count and freed pages remain. Watch the index size and plan a REINDEX CONCURRENTLY (PostgreSQL 12 or later) after big purges.
• Insert latency spikes from splits. Splits run in the foreground, so a bulk load into a table with a hash index pays for bucket growth inline. Building the index after the load avoids this.
• Planner surprises. A query written as a range, a function of the column or a different type than the index's operator class silently cannot use the hash index. Confirm with EXPLAIN.
• Old advice applied to new versions. Avoiding hash indexes because they were not crash-safe applies only before PostgreSQL 10.

Operating and choosing

A hash index is worth considering when all of these are true: the column is queried only by equality, values are unique or nearly so, the values are long (UUID strings, URLs, tokens, content hashes), and the index is large compared with memory, where the PostgreSQL documentation notes the reduced page access matters most. Otherwise a B-tree is the safer default, because it serves equality almost as well and also supports ranges, sorting, uniqueness, multiple columns and index-only scans.

Decide by measurement: build both indexes on a copy of production data, compare sizes and the buffers read by the real queries, then drop the loser. For a broader view of PostgreSQL index types, see PostgreSQL indexes in depth.

What to do next

1. Run the linear hashing simulator, then change the capacity, target load and key distribution (try many duplicates) and watch overflow change.
2. Find equality-only lookups on long text or UUID columns in your slow-query log; they are the hash index candidates.
3. On a copy of the data, build a hash index next to the existing B-tree and compare size and buffers read with EXPLAIN (ANALYZE, BUFFERS).
4. Confirm the server is PostgreSQL 10 or later before using hash indexes in production.
5. Inspect the meta page with pageinspect to see bucket count and occupancy.
6. If you run MySQL 8.4, check whether the adaptive hash index is on, and benchmark both settings before changing it.