Skip to content
Course contents

Hash Indexes and Where They Run Out

Keep a map from key to file offset and reads become one seek. Then count how much memory that map needs, and try a range query.

Lesson 2 of 59 min read

By the end of this lesson you can

  • Describe how an in-memory hash index turns an O(n) scan into a single seek
  • Name the two limits that make hash indexes unsuitable as a general-purpose index
  • Explain how segments and tombstones handle compaction and deletion

The two-line database scans the whole file because it does not know where anything is. So let us tell it.

Keep a hash map in memory: key → byte offset in the log. On write, append the record and update the map. On read, look up the offset and seek straight to it.

log     0: k1,alpha    14: k2,beta    27: k1,gamma

index   k1 → 27
        k2 → 14

Writes stay sequential appends. Reads become one hash lookup plus one disk seek — O(1) instead of O(n). For a first attempt that is an enormous improvement, and it is not a strawman: this is essentially how Bitcask, the storage engine behind Riak, works.

Segments, compaction, and merging

The log still grows forever, so break it into fixed-size segments. When the active segment reaches its limit, close it and start a new one. Closed segments are immutable, which makes them safe to compact in a background thread while writes continue elsewhere.

Compaction keeps the newest value per key within a segment. Then merging combines several compacted segments into one, resolving conflicts by preferring the newer segment.

A read now checks the newest segment’s index first, then the next, and so on until the key is found. Each segment carries its own in-memory index.

Crash recovery is straightforward too, because the indexes are derived data. On restart you could rebuild every segment index by reading the segments — correct but slow for large files — so engines snapshot each index to disk and rebuild only what is missing.

Limit one: the index must fit in memory

Every key lives in a hash map in RAM. Not the values — just the keys and their offsets — but that is still one entry per distinct key, forever.

A hundred million distinct keys, at a conservative 60 bytes per entry once you count the key, the offset and the map’s own overhead, is around 6GB of RAM that must be there before you serve a single request. Ten billion keys is not a tuning problem; it is a different architecture.

Worse, the failure mode is a cliff. Everything is fast right up to the moment the index no longer fits, and then the machine starts swapping and performance collapses.

The idea

A hash index requires memory proportional to the number of distinct keys, not to how much data you have. That is fine for a fixed key space and fatal for one that grows with your users.

Limit two: range queries are impossible

This one is structural, and it is the reason hash indexes never became the default.

A good hash function scatters keys deliberately. user_1000 and user_1001 sit in unrelated buckets. So:

SELECT * FROM events WHERE ts BETWEEN '2026-01-01' AND '2026-01-31'

has no better strategy than checking every possible key in the range, one hash lookup at a time — or scanning everything, which is where we started.

Range scans are not a niche feature. Time ranges, alphabetical listings, “the next 50 rows”, ORDER BY with a LIMIT, prefix search, every paginated list in every application — all of them are range queries. An index that cannot serve them cannot be the primary index of a general-purpose database.

Check yourself

A team stores IoT readings keyed by `{deviceId}:{timestamp}` with a hash index, and it works well for a year. Which requirement breaks it first?

What to take away

A hash index fixes the read path with one seek, and it does so by requiring every key in memory and giving up ordering. Keep the segments, keep the compaction, keep the tombstones — but if the keys were kept sorted, both limits would ease at once. That is the next lesson.

Finished this one?

skip for now