Skip to main content

Hash Indexes and LSM-Trees

Adapted from: Martin Kleppmann, Designing Data-Intensive Applications (O'Reilly, 2017), Chapter 3 — rewritten and condensed for teaching.

Graph-Like Data Models looked at storage and retrieval from the application developer's side — the format you hand a database and the language you use to ask for it back. This lesson flips to the database's own point of view: on the most fundamental level, a database only has two jobs — when you give it data, store it; when you ask for it later, hand it back. Everything in this lesson is really just different answers to how.

You'll probably never write your own storage engine from scratch — but picking the right one for your workload, and tuning it well, both require a rough mental model of what's happening under the hood. That's exactly what this lesson and the next one build.

The World's Simplest Database​

Here's a fully working key-value store in two Bash functions:

#!/bin/bash
db_set () {
    echo "$1,$2" >> database
}

db_get () {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

db_set key value appends a key,value line to a file. db_get key finds the most recent line for that key and returns its value. It actually works:

$ db_set 123456 '{"name":"London","attractions":["Big Ben","London Eye"]}'
$ db_set 42 '{"name":"San Francisco","attractions":["Golden Gate Bridge"]}'
$ db_get 42
{"name":"San Francisco","attractions":["Golden Gate Bridge"]}

Updating a key doesn't overwrite anything — it just appends another line, so db_get has to find the last matching line to get the current value:

$ db_set 42 '{"name":"San Francisco","attractions":["Exploratorium"]}'
$ cat database
123456,{"name":"London","attractions":["Big Ben","London Eye"]}
42,{"name":"San Francisco","attractions":["Golden Gate Bridge"]}
42,{"name":"San Francisco","attractions":["Exploratorium"]}

db_set is, surprisingly, already quite good — appending to a file is one of the cheapest operations a filesystem offers. Many real databases use exactly this idea internally: an append-only log. (Here, "log" doesn't mean human-readable application logs — it means any append-only sequence of records, human-readable or not.) Real engines add concurrency control, reclaiming disk space, and crash safety on top, but the core idea is identical to db_set.

db_get, on the other hand, is a disaster at scale: it scans the entire file, every time, looking for matches. That's O(n) — double the number of records, double the lookup time. To fix this, we need a different data structure: an index.

An index is extra metadata derived from the primary data — it doesn't change what's stored, only how fast you can find it. And every index has a cost: it must be updated on every write, so indexes speed up reads at the cost of slowing down writes. This is why databases don't index everything by default — you (or a DBA) choose indexes deliberately, based on your application's actual query patterns.

Practice: build the toy database​

Piston's sandbox doesn't have a Bash runtime, but the exact same idea translates directly into Python. Implement db_set and db_get using plain file append and a linear scan for the last matching key — this is the real append-only-log mechanism, just in a different language.

Check: the append-only log​

Quiz

The world's simplest database

1 / 3

Why is db_set (the append-only write) already fast, without any special optimization?

Pick an answer to see if you are right.

Hash Indexes​

The simplest index for key-value data: keep an in-memory hash map from every key to a byte offset in the append-only data file. On every write, update the hash map with the new offset. On every read, look up the offset in the hash map, seek straight to that byte in the file, and read the value — no scanning required.

This is, essentially, exactly what Bitcask (Riak's default storage engine) does. It offers very fast reads and writes, on one condition: all keys must fit in RAM (the hash map lives entirely in memory). Values can be far larger than available memory, since each read only costs one disk seek — and if that part of the file is already in the OS's filesystem cache, not even that.

This shape fits workloads where a modest number of distinct keys get updated extremely often — e.g. the key is a cat video's URL, and the value is its play count, incremented every time someone hits play. Lots of writes, but a feasible number of distinct keys to keep in memory.

Compaction and Segment Merging​

An append-only file obviously can't grow forever, so real implementations break the log into segments: close a segment once it hits a size threshold, and start a new one. Compaction then throws away all but the most recent value for each key within a segment — and since compaction usually shrinks segments a lot (a key might be overwritten many times within one segment), it's natural to merge several compacted segments together at the same time, writing the result to a fresh file. Old segments are read normally while this happens in the background, and get deleted only once the merge completes.

Each segment keeps its own in-memory hash map. A lookup checks the newest segment's map first, then the next-newest, and so on — merging keeps the segment count low, so this stays fast.

Making It Work in Practice​

A handful of unglamorous details separate this idea from a real, safe implementation:

ConcernApproach
File formatA binary format (length-prefixed strings) instead of CSV — faster, and sidesteps escaping
DeletesA special tombstone record marks a key deleted; merging discards any older value once it sees the tombstone
Crash recoveryRebuilding a segment's hash map by rereading the whole segment is slow — Bitcask snapshots each segment's hash map to disk for fast reload
Partial writesChecksums let a crash-corrupted, half-written record be detected and skipped
ConcurrencyOne writer thread (writes are strictly sequential anyway); segments are immutable once closed, so many threads can read concurrently with no coordination
Why append-only, when overwriting in place seems simpler?

Three real reasons: (1) sequential writes (appending, merging) are dramatically faster than random writes, especially on spinning disks and — to a lesser extent — SSDs. (2) Concurrency and crash recovery get much simpler when segments are append-only/immutable — there's no scenario where a crash leaves a file half-old, half-new mid-record. (3) Merging naturally defragments old data over time, instead of it slowly fragmenting the way in-place updates do.

Where Hash Indexes Fall Short​

Two real limits:

  1. The hash map must fit in memory. An on-disk hash map is possible in theory, but performs poorly in practice — random I/O, expensive resizing, fiddly collision handling.
  2. Range queries are inefficient. There's no way to cheaply ask "give me every key between kitty00000 and kitty99999" — a hash map has no sense of ordering, so you'd have to look up each key individually.

Check: hash indexes​

Quiz

Hash indexes and Bitcask

1 / 3

In a Bitcask-style hash index, what does the in-memory hash map actually store?

Pick an answer to see if you are right.

SSTables and LSM-Trees​

Take the segment format from before and add one requirement: the key-value pairs must be sorted by key, with each key appearing only once per (already-compacted) segment. This format is called a Sorted String Table, or SSTable.

Sorting unlocks three big wins over plain hash-indexed segments:

  1. Merging is simple and cheap, even for files bigger than memory. It's exactly mergesort's merge step: read all input segments side by side, always copy the lowest current key to the output, and repeat. When the same key appears in multiple segments, keep the value from the newer segment and discard the rest (since segments are ordered in time, this is always well-defined).

  2. You don't need every key in memory to find one. If you're looking for handiwork and you already know handbag sits at offset 1000 and handsome sits at offset 2000, sorting guarantees handiwork — if it exists — is somewhere between those two offsets. So the in-memory index only needs to be sparse: one key every few kilobytes of segment file is enough, since scanning a few kilobytes is cheap.

  3. Compression becomes natural. Since a read already has to scan a small range of consecutive records anyway, that range can be grouped into a block and compressed before writing — smaller files and less I/O bandwidth used per read.

How Do You Get Sorted Data From Unsorted Writes?​

Writes arrive in arbitrary order, but building a sorted structure in memory is easy — a balanced tree (red-black, AVL) lets you insert in any order and read back sorted. This in-memory tree is called a memtable, and it's the missing piece of the puzzle:

  1. A write goes into the memtable first.
  2. Once the memtable crosses a size threshold (typically a few MB), flush it to disk as a new SSTable file — cheap, since the tree is already sorted. Writes continue into a fresh memtable while the old one is being flushed.
  3. A read checks the memtable first, then the newest on-disk segment, then the next-newest, and so on.
  4. A background process periodically merges and compacts segments, same as before.

The one gap: a crash loses whatever's in the memtable but not yet flushed. The fix is familiar — keep a separate, unsorted write-ahead log that every write hits immediately, purely to rebuild the memtable after a crash. Once a memtable is safely flushed to an SSTable, its corresponding log can be discarded.

The LSM-Tree Family​

This exact scheme — memtable + flushed SSTables + background merging — is what LevelDB and RocksDB implement, and it's the design Cassandra and HBase both inherited from Google's Bigtable paper (which is where the terms SSTable and memtable originated). The underlying technique was formally described earlier as the Log-Structured Merge-Tree (LSM-Tree), building on log-structured filesystem research — which is why storage engines built this way are generally called LSM storage engines. Lucene (the indexing engine behind Elasticsearch and Solr) uses a near-identical SSTable-like structure for its term dictionary, mapping search terms to lists of matching document IDs.

Performance Tricks​

Looking up a key that doesn't exist is the worst case for an LSM-tree — you have to check the memtable and every segment, oldest included, before you can be sure. Bloom filters — a compact, memory-efficient structure that can definitively say "this key is not in the set" — short-circuit most of those wasted checks.

Two common strategies govern when and how SSTables get merged:

  • Size-tiered compaction — merge smaller, newer SSTables into larger, older ones (used by HBase; Cassandra supports this too).
  • Leveled compaction — split the key range into smaller SSTables and progressively move older data into separate "levels," allowing incremental compaction with less disk space overhead (used by LevelDB and RocksDB — hence LevelDB's name).

Despite the subtlety packed into a real implementation, the core idea — a cascade of sorted segments, merged in the background — stays simple, scales well past available memory, supports efficient range queries (since data is sorted), and sustains high write throughput (since disk writes stay sequential).

Practice: simulate compaction​

Compaction's core job is simple: given a segment (a sequence of key-value writes in the order they happened), keep only the most recent value per key. Implement it directly.

Check: SSTables and LSM-trees​

Quiz

SSTables, memtables, and LSM-trees

1 / 3

Why does requiring segment files to be sorted by key (an SSTable) allow the in-memory index to be sparse, instead of needing every key in memory?

Pick an answer to see if you are right.

Key takeaways
  • Every database ultimately does two things: store data you give it, and retrieve it later — everything else is implementation detail in service of doing both quickly.
  • An index is metadata derived from primary data that speeds up reads at the cost of slowing down writes — which is why indexes are chosen deliberately, not applied everywhere by default.
  • A hash index (Bitcask-style) offers very fast reads/writes but requires all keys to fit in memory and can't do efficient range queries.
  • Sorting segments into SSTables fixes both limits: merging becomes a cheap mergesort-style pass, the in-memory index can be sparse, and reads compress naturally — at the cost of needing an in-memory memtable (backed by a write-ahead log) to accumulate sorted writes before flushing.
  • LSM-trees — a cascade of SSTables merged in the background — power LevelDB, RocksDB, Cassandra, HBase, and Lucene's term dictionaries, and scale gracefully even when the dataset far exceeds available memory.

Further Reading​