B-trees and LSM-trees in plain words: how a database stores data

← Back to the section

You probably won't write your own database. But choosing between PostgreSQL and Cassandra, tuning ClickHouse, explaining to a colleague why an extra index slowed down writes — that you'll do. For that you need a picture of what a database does on disk.

The good news: inside almost any database sits one of two storage engines — a B-tree or an LSM-tree. Understand these two, and the behavior of most databases stops being magic. Let's build both from the most primitive "database" imaginable.

The simplest database in the world

Here's a "database" made of two lines of Bash:

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

db_set appends a "key,value" pair to the end of a file. db_get finds the last occurrence of a key. Primitive — but this toy teaches us something.

Writing here is surprisingly good. Appending a line to the end of a file is the cheapest operation for a disk (the head doesn't jump around the platter; everything is written in sequence). Real databases use exactly this trick and call it a log — a sequence of records you can only append to.

Reading, though, is terrible. To find a key, db_get scans the whole file from start to finish. The more data, the slower: that's O(n) — time grows linearly with the size of the database.

To read fast, you need an index — a helper structure alongside the data, like a book's table of contents. And right away the central trade-off appears: an index speeds up reads but slows down writes — every insert has to update it too. That's why databases don't index everything: the developer picks the indexes their queries need.

Step one: a hash index

The simplest index for our log is to keep, in memory, a table of "key → the position in the file where its latest value sits." Then a write stays a cheap append, and a read is a single jump straight to the right spot.

To keep the file from growing forever, the log is cut into pieces (segments), and every so often a background compaction runs: it throws out stale versions of keys and merges segments into a smaller one.

This is exactly how the real Bitcask engine works. But the approach has two ceilings: all the keys must fit in RAM, and range queries ("all keys from A to B") won't work — a hash table knows nothing about key order.

LSM-tree: sorted pieces

Both ceilings are removed by one idea — keep each segment sorted by key. Such a file is called an SSTable (sorted string table). Here's how an engine works on it:

1. A new write first lands in the MemTable — a small sorted tree right in RAM (plus it's appended to a short on-disk log, in case the power cuts out).
2. When the MemTable grows to a few megabytes, it's flushed to disk whole as a new SSTable file. That's another cheap sequential write.
3. A read looks for the key first in the MemTable, then in the freshest SSTable, then in the previous one — and so on down.
4. Background compaction merges SSTables together: two sorted files are easy to merge, and duplicates of the same key collapse to the latest version.

The whole mechanics of step four fit into one loop:

live example

public class Compaction {
    public static void main(String[] args) {
        String[] older = {"b=1", "c=1", "f=1"};
        String[] newer = {"a=2", "c=2", "e=2"};
        StringBuilder merged = new StringBuilder();
        int i = 0, j = 0;
        while (i < older.length || j < newer.length) {
            char left = i < older.length ? older[i].charAt(0) : '\uffff';
            char right = j < newer.length ? newer[j].charAt(0) : '\uffff';
            if (left < right) merged.append(older[i++]).append(' ');
            else if (right < left) merged.append(newer[j++]).append(' ');
            else { merged.append(newer[j++]).append(' '); i++; }
        }
        System.out.println("old:    " + String.join(" ", older));
        System.out.println("fresh:  " + String.join(" ", newer));
        System.out.println("merged: " + merged.toString().trim());
    }
}

One pass, no memory needed — that's why merging lives in the background.

This is the LSM-tree (log-structured merge-tree). It powers RocksDB and LevelDB, Cassandra and HBase; the same "sorted pieces + background merge" principle underlies Lucene's search index (and therefore Elasticsearch) and the MergeTree engine in ClickHouse.

One subtle spot: looking up a missing key is expensive — you have to check the MemTable and all SSTables down to the oldest. A Bloom filter saves you here — a compact structure that quickly answers "definitely not there" or "maybe there" for a key, and in the first case saves pointless disk reads.

B-tree: fixed-size pages and the WAL

The B-tree was invented back in the 1970s and is still the default standard: it underlies the indexes of PostgreSQL, MySQL, Oracle, and almost every relational database. The approach is the opposite. The database is split not into variable-size pieces but into pages of the same size (usually 4 to 16 KB: 8 KB in PostgreSQL, 16 KB in MySQL), and these pages are overwritten in place rather than appended to the end.

The pages form a tree. At the root are boundary keys and links to "children"; each child is responsible for its range of keys; at the very bottom, in the leaves, sit the values. Each page has hundreds of links to children, so the tree comes out very "flat", and finding a key is three or four jumps across the disk. Let's count the capacity, at three hundred links per page:

live example

public class TreeHeight {
    public static void main(String[] args) {
        long keys = 1;
        for (int level = 1; level <= 4; level++) {
            keys *= 300;
            System.out.println("levels: " + level + " -> " + keys + " records");
        }
    }
}

Four levels are enough for billions of records. If an insert doesn't fit in a page, the page is split into two and the parent's link is fixed up.

Overwriting in place is dangerous: if the power cuts out at the exact moment a page is being split, the index can be left "torn." So every change is first appended to the write-ahead log (WAL) and only then applied to the pages themselves. After a crash, the database replays the log and restores consistency. An irony: an in-place engine still carries a log around — the very one we started with.

Comparison: what you pay for

• Writes. LSM is usually faster because everything is written sequentially. In a B-tree every write is both a WAL write and a rewrite of a whole page (even if three bytes changed). How many extra bytes actually go to disk per byte of useful data is called write amplification. That said, LSM has amplification too — compaction rewrites data many times over and under a heavy write stream starts fighting writes for the disk.
• Reads. A B-tree is more predictable: a key lives in exactly one place, and the path to it is the same three or four jumps. In an LSM a key can end up in several pieces at different stages of compaction, so its "tail" latencies (see percentiles) are more temperamental — compaction occasionally steals the disk from ordinary queries.
• Transactions. In a B-tree it's convenient to lock a range of keys right in the tree — one reason relational databases with their transaction isolation are built on B-trees.

A practical rule: "write a lot, read mostly recent" (events, metrics, a feed) is LSM territory; "read a lot by keys and ranges, need transactions" is B-tree territory. Only a measurement on your workload settles it.

Where this applies

Understanding the engine turns the "magical" properties of databases into plain consequences. Why does Cassandra handle a huge write stream? Sequential SSTables. Why do extra indexes in PostgreSQL slow down inserts? Each index is one more B-tree to update. Why must data in ClickHouse be sorted by the table key? MergeTree is a relative of LSM, and sorting is its index. Why doesn't PostgreSQL start instantly after a crash? It replays the WAL.

Where beginners stumble:

• Comparing databases by marketing, not by engine. "NoSQL is faster" is a phrase about nothing: the question is faster at writes or at reads, and why.
• Forgetting that an index isn't free. Five indexes on a table means five trees updated on every insert.
• Not watching compaction. An unattended LSM database piles up pieces until the disk runs out or reads sag.
• Being scared of the word WAL. It's not exotic: the log is what lets a database survive a power cut, and replication and backups rest on it.

In short

• Appending to the end of a file is the cheapest write; both engines start from a log.
• LSM: MemTable in RAM, flushed whole as a new SSTable, segments merged in the background; a shared key collapses to its fresh version.
• A missing key makes LSM check every segment; the Bloom filter saves it.
• B-tree: pages of 8 KB (PostgreSQL) or 16 KB (MySQL) rewritten in place, hundreds of links per page — four levels for billions of records.
• Rewriting in place rests on the WAL: the log first, the pages after.
• You always pay: LSM with tail latencies and compaction fighting for the disk, a B-tree with write amplification.

What to read next

• OLTP and OLAP — the shape of queries decides which engine you need.
• PostgreSQL index types — the B-tree from the user's side.
• WAL in PostgreSQL — what makes the log grow.
• Modeling in ClickHouse — MergeTree in practice.