Hash Indexes

Concept. A hash index computes hash(key) and uses it to choose the page that stores the key's index entry. It supports O(1) average equality lookups (WHERE id = 42). It cannot support range scans (WHERE id BETWEEN 10 AND 100) because the hash does not preserve key order.

Intuition. When you query "find Mickey's user row" (WHERE user_id = 1), a hash index returns the page in one IO. But for "find users with user_id between 100 and 200," the hash is no help.

Prerequisites. Index Fundamentals introduces what (key, page#) pairs are and how pointers work.

How a Hash Index Finds a Row

A hash index (subclass of index) stores the same (search_key, page#) pairs, but the bucket (set of pages) for each pair is chosen by a hash function.

Hash index. Three index pages on the right hold (search_key, page#) entries; five data pages on the left hold the actual rows. The lookup computes hash(Dan) = 1, selects index page 1, and follows the Dan entry to data pages 0, 1, and 4.

Figure 1. A hash index on People.name stores (search_key, page#) entries in buckets chosen by hash(value). Here, hash(Dan) = 1 selects index page 1. Its Dan entry points to data pages 0, 1, and 4. The lookup requires 4 IOs: one index-page read and three data-page reads.

What Hash Indexes Are Good At, and What They Break On

The hash function both makes point lookups (for a specific lookup) fast. Hashing scatters neighbouring keys to random buckets, so any query that needs range lookups in order gets no help at all.

Works

WHERE user_id = 42
WHERE order_id = 'ABC-123'
WHERE session_key = 'xyz789'

Any predicate that resolves to a single key: equality, primary-key lookup, session ID, cache key.

No help

WHERE age > 21
ORDER BY created_at
WHERE name LIKE 'A%'
WHERE price BETWEEN 10 AND 50

Any predicate that spans a range of keys, requires sorted order, or matches a prefix. Reach for a B+Tree instead.

Algorithm

Algorithm · Hash Index: Build & Lookup

Build(table, key_column):
    B = choose_bucket_count()             // often a prime
    index = array[B] of lists

    for row in table:                     // one pass over the table
        key = row[key_column]
        bucket = hash(key) % B
        index[bucket].append((key, row_pointer))

    return index

Lookup(index, search_key):                // O(1) average
    bucket = hash(search_key) % B
    for (key, pointer) in index[bucket]:  // scan only this bucket
        if key == search_key:
            return pointer                // found
    return null                           // not found

Hash choice matters. A poor hash clusters keys into a few buckets and degrades lookup to O(N), so production databases use well-studied hashes (e.g., MurmurHash).