30-Second Glance
- A hash index is an in-memory
key → byte-offsetmap over append-only segment files:O(1)point lookups, zero index I/O on writes. - Writes are always sequential appends; reads are one hash lookup + one disk seek. Bitcask (Riak) is the canonical example.
- Every key must fit in RAM, so it suits high-write KV workloads with small keys — not range scans or large-than-memory datasets.
- Crash recovery = replay segment files to rebuild the map; compaction merges segments and reclaims space from overwritten keys.
How It Works
A hash index is the simplest durable index you can build. The storage engine keeps an in-memory hash map from each key to the byte offset of its latest value in an append-only log file. A write appends key + value to the current segment and updates the map entry. A read looks up the offset in the map and does a single random read (one seek + read) from the file. There is no tree to rebalance, no pages to split, no write-time index maintenance beyond the map update.
The canonical implementation is Bitcask (default engine of Riak). Each Bitcask store is a directory of segment files with one active file open for appends. Once the active segment hits a size threshold (commonly tens to hundreds of MB), it is closed and a new one opened. A background compaction pass merges closed segments: it copies only the latest value per key into a new compacted segment and deletes the inputs, reclaiming space consumed by overwritten and deleted keys (tombstones).
Concrete Numbers
| Quantity | Typical value | Why it matters |
|---|---|---|
| Lookup cost | O(1) map probe + 1 disk seek |
~5–10 ms on HDD, ~50–150 µs on SSD per point read |
| Write cost | 1 sequential append, no seeks | Saturates disk sequential bandwidth (~100–500 MB/s) |
| Per-key RAM overhead | ~16–32 bytes (key + offset + map overhead) | 10M keys ≈ 300 MB RAM; bounds total dataset keyspace |
| Segment size | 64 MB – 1 GB before roll | Larger = fewer files, slower compaction; smaller = faster recovery |
| Recovery time | Proportional to total log size | Must scan every segment to rebuild the map — minutes for 100s of GB |
The RAM bound is the load-bearing constraint. If keys average 20 bytes and map overhead is ~24 bytes, 100M keys need ~4 GB just for the index. Values can live on disk (even GBs each), but the keyspace must fit in memory. This is why hash indexes dominate small-key KV stores (sessions, feature flags, dedup tables) and vanish from analytics.
Crash Safety and Concurrency
Bitcask durability comes from the log, not the map. The map is disposable and rebuilt on startup by scanning segments newest-to-oldest. To avoid a full scan on every restart, engines checkpoint a "hint file" of key → offset pairs per segment, cutting recovery to one sequential read of hints plus the tail of the active segment.
Concurrency is trivially correct: only one writer appends to the active segment (single-writer lock or atomic append), and readers never block because files are immutable once closed. Deletes are tombstone appends — the key is removed from the map immediately but its old bytes are reclaimed only at compaction. This is the same tombstone pattern you will see again in LSM Trees and SSTables.
Limitations
- No range queries. Hashing destroys ordering, so
WHERE age BETWEEN 20 AND 30requires a full scan. If the interview asks for range or prefix scans, pivot to B-Tree Indexes. - Keyspace must fit in RAM. No partial loading — every key needs a map entry.
- Compaction stalls. Merging large segments costs sequential I/O and temporarily doubles disk usage; on HDDs this visibly hurts tail latency.
- Too many files. Without merging, open file handles and startup scan time grow unboundedly — hence the mandatory compaction loop.
Trade-offs
| Approach | Pros | Cons | Use when |
|---|---|---|---|
| Hash index (Bitcask-style) | O(1) reads/writes; simplest crash recovery; max sequential-write throughput | All keys in RAM; no range scans; compaction I/O | Point-lookup KV, small keys, write-heavy (sessions, caches, ledgers) |
| B-Tree index | Range scans; bounded RAM; mature (InnoDB) | Page splits, random-write I/O, write amplification | General OLTP with range predicates — see B-Tree Indexes |
| LSM-tree | High write throughput without RAM bound; sorted + compacted | Read amplification, compaction debt, tuning burden | Write-heavy sorted datasets (metrics, feeds) — see LSM Trees and SSTables |
Interview One-Liners
- Q: Why are hash-index writes so fast? A: Every write is a sequential append plus an in-memory map update — no seeks, no page splits, no tree rebalancing.
- Q: What bounds the dataset size of a Bitcask-style engine? A: RAM: one hash entry per distinct key must stay resident, so key count × ~16–32 bytes must fit in memory.
- Q: How does crash recovery work if the index is in-memory? A: Rebuild it by scanning segment files (or compact hint files) newest-to-oldest; the log is the source of truth.
- Q: Why can't hash indexes do range queries? A: Hashing destroys key order, so adjacent keys scatter across buckets — a range predicate degrades to a full scan.
- Q: What does compaction do and what does it cost? A: Merges segments keeping only each key's latest value, reclaiming overwritten space at the cost of bulk sequential I/O and temporary 2× disk usage.
- Q: Hash index vs LSM-tree in one line? A: Hash gives O(1) point lookups with a RAM-resident keyspace; LSM gives sorted range scans with a disk-resident index at the cost of compaction and read amplification.