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. And for that you need at least a rough 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 up from scratch — starting with the most primitive "database" imaginable and growing from there.
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 have to 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), i.e. time grows linearly with the size of the database.
To read fast, you need an index — a separate helper structure alongside the data, something like a book's table of contents. And right away the central trade-off of this whole world appears: an index speeds up reads but slows down writes — because every insert has to update the index too. That's exactly why databases don't index everything; they ask the developer to choose which indexes are needed for their queries.
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 (plus updating the little table in memory), and a read is a single jump straight to the right spot in the file.
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 ("give me all keys from A to B") won't work — a hash table knows nothing about the order of keys.
LSM-tree: sorted pieces
Both ceilings are removed by one idea — keep each segment sorted by key. Such a sorted file is called an SSTable (sorted string table). Here's how an engine works on this idea:
- A new write first lands in the MemTable — a small sorted tree right in RAM (plus it's quickly appended to a short on-disk log, in case the power cuts out and memory is lost).
- 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.
- A read looks for the key first in the MemTable, then in the freshest SSTable, then in the previous one — and so on down, until it finds it.
- Background compaction merges SSTables together. Merging two sorted files is easy (like the merge step in merge sort), and duplicates of the same key collapse to the latest version.
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 before you can say "no such key." A Bloom filter saves you here — a compact structure that quickly answers "definitely not there" or "maybe there" for a key, and in the "definitely not" case saves a pile of 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 here is the opposite. The database is split not into variable-size pieces but into pages of the same size (usually 4–8 KB), 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 themselves. Each page has hundreds of links to children, so the tree comes out very "flat": four levels are enough for hundreds of gigabytes, and finding a key is just three or four jumps across the disk. 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. A funny irony: an in-place engine still carries a log around — the very trick 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; under a heavy write stream it starts fighting writes for the disk, and you have to watch separately that compaction doesn't fall behind.
- 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 — background compaction occasionally steals the disk from ordinary queries.
- Transactions. In a B-tree it's convenient to put a lock right on a range of keys in the tree — one reason relational databases with their transaction isolation are built on B-trees.
A practical rule: a "write a lot, read mostly recent" workload (events, metrics, a feed) is LSM territory; "read a lot by keys and ranges, need transactions" is B-tree territory. But the real answer comes only from measuring on your own workload.
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. Faster at writes and why — that's the right question, and the answer lies in the storage engine.
- 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 quietly piles up pieces until the disk runs out or reads sag.
- Being scared of the word WAL. It's not exotic — it's exactly what lets a database survive a power cut; replication and backups rest on it too.
What to read next: OLTP and OLAP — how the shape of queries determines both the engine and the whole storage architecture; PostgreSQL index types — the B-tree from the user's side; modeling in ClickHouse — MergeTree in practice.