Hash Indexing
O(1) for equality, useless for ranges — and what happens when a bucket fills up.
Skip to the animationA hash index computes a record's bucket address directly from its key — constant-time equality lookup, at the cost of losing every trace of ordering.
One computation instead of a search
A B+ tree finds a record by descending several levels, comparing as it goes. A hash index applies a function: h(k) gives the bucket, and one page read finds the record. No comparisons, no tree, no depth.
The whole design then hangs on what happens when two keys land in the same bucket, and on what happens when the data outgrows the number of buckets.
Collisions and overflow
Different keys hashing to the same bucket is normal and harmless while the bucket has room. It only becomes a cost when the bucket is full, at which point static hashing chains an overflow page.
Each overflow page added to a chain is another read for every lookup in that bucket. As chains grow, the one-read guarantee erodes toward a linear scan — while other buckets may be sitting empty. This is the characteristic failure of static hashing: not collisions, but the inability to grow.
Rehashing with a bigger function fixes the distribution but requires relocating every record in the index — a disruptive, expensive rebuild.
Dynamic hashing
- Extendible hashing
- A directory of pointers to buckets, using the first d bits of the hash. When a bucket overflows, only that bucket splits; the directory doubles only when it must. Growth is incremental, and the one-read property is preserved.
- Linear hashing
- Splits buckets in a fixed round-robin order rather than the one that actually overflowed, and needs no directory at all. Slightly worse distribution, no directory to maintain.
The thing it can never do
A good hash function deliberately scatters similar keys — that is what keeps buckets evenly filled. It also destroys ordering completely.
WHERE id BETWEEN 5 AND 20— no starting point and no ordering, so every bucket must be scanned.ORDER BY id— the index provides no help whatsoever.WHERE name LIKE 'sm%'— prefixes hash nowhere near each other.MIN(id)— no notion of smallest.
A B+ tree handles all of these and is only O(log n) for equality — with a branching factor in the hundreds, that log is 3 or 4. Paying a factor of three on equality to get ranges, ordering and prefixes for free is why B+ trees are the default index everywhere, and hash indexes are a deliberate specialist choice.
Advantages and disadvantages
Advantages
- O(1) equality lookup — usually a single page read.
- No tree to descend, rebalance, or keep in memory.
- Ideal for joins and lookups on keys that are only ever compared for equality.
Disadvantages
- Useless for ranges, ordering, prefixes or minimum and maximum.
- Static hashing degrades badly once buckets overflow, and rehashing is expensive.
- Performance depends entirely on the hash function distributing keys evenly.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.