You will not be writing your own DBMS. But you will be choosing between PostgreSQL and Cassandra, tuning ClickHouse, and explaining why an index slowed down writes. All of that takes a rough understanding of what the database does on disk. Inside almost any DBMS sits one of two storage engines: a B-tree or an LSM-tree. Let's build up both from scratch.
The simplest database in the world
A classic example from the first part of Kleppmann's book — a "database" made of two Bash functions:
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 key's latest occurrence. Writes here are surprisingly good: appending to a file is the cheapest disk operation there is, and real databases use the same trick under the name log: an append-only sequence of records. Reads, though, are terrible: O(n) — the whole database gets scanned.
To read fast you need an index — an extra structure kept alongside the data. And here is the fundamental trade-off of this whole world: an index speeds up reads but slows down writes, because it must be updated on every insert. That is why databases do not index everything by default and instead ask the developer to pick indexes to match the queries.
Step one: a hash index
The simplest index over a log is an in-memory hash map: key → byte offset in the file where the latest value lives. Writes stay append-only (plus a map update); a read is one jump to the offset. To keep the file from growing forever, the log is split into segments, and compaction runs in the background: stale versions of keys get dropped, segments get merged.
This is exactly how the real-world Bitcask engine works. The limitations: all keys must fit in memory, and range queries ("all keys from A to B") are hopeless — a hash knows nothing about order.
The LSM-tree: sorted segments
Both limitations fall to one idea: keep segments sorted by key. Such a file is called an SSTable (sorted string table). The engine works like this:
- A write goes into the MemTable — a balanced tree in memory (plus a short on-disk log as insurance against crashes).
- When the MemTable grows to a few megabytes, it is flushed to disk whole as a new SSTable — again a sequential write.
- A read checks the MemTable, then the newest SSTable, then the previous one — and so on.
- Background compaction merges SSTables: merging sorted files is a cheap mergesort, and duplicate keys collapse to the latest version.
That is the LSM-tree (log-structured merge-tree) — the heart of RocksDB and LevelDB, Cassandra and HBase; the same "sorted segments + background merging" principle underlies Lucene's term dictionary (that is, Elasticsearch) and ClickHouse's MergeTree.
The subtle spot is looking up a key that is absent: you would have to check the MemTable and every SSTable down to the oldest. The cure is a Bloom filter — a compact probabilistic structure that answers "definitely not here" or "possibly here" per key and saves disk reads.
The B-tree: pages and the WAL
The B-tree dates back to the 1970s and is the de facto standard: it powers the indexes of PostgreSQL, MySQL, Oracle, and nearly every relational database. The approach is the opposite: the database is broken not into variable-size segments but into fixed-size pages (usually 4–8 KB) that are read and overwritten in place.
Pages form a tree: the root holds boundary keys and references to children, each child owns its key range, and the leaves hold the values. The branching factor is hundreds of references per page, so the tree is very flat: four levels cover hundreds of gigabytes, and a lookup is O(log n) with three or four disk hops. Inserting into a full page splits it in two and updates the parent.
Overwriting in place is a dangerous operation: a crash mid-split can leave the index torn. So every modification is first appended to the write-ahead log (WAL) and only then applied to the pages; after a crash the database restores consistency from the log. A familiar irony: the engine built on in-place overwrites still carries a log around.
The comparison: what you pay for
- Writes. LSM is usually faster: everything is written sequentially. In a B-tree every write costs the WAL plus a whole page (even if three bytes changed). The measure of that cost is write amplification: how many bytes actually hit the disk per byte of useful data. LSM has amplification too — compaction rewrites data repeatedly; under heavy write load it competes with writes for disk bandwidth, and compaction lag needs its own monitoring.
- Reads. The B-tree is more predictable: a key lives in exactly one place, and the path to it is a fixed three or four hops. In an LSM engine a key may sit in several segments at different compaction stages, and its tail latencies (see percentiles) are noticeably moodier — background compaction periodically steals the disk from queries.
- Transactionality. In a B-tree a lock on a key range can be attached directly to the tree — one reason relational databases with their transaction isolation stand on B-trees.
The practical rule: a "write a lot, read the recent" workload (events, metrics, feeds) is LSM territory; "read a lot by keys and ranges, transactions" belongs to the B-tree. Numerically, though, only a test on your own workload settles it.
Where this applies
Knowing the engine turns "magic" database properties into plain consequences. Why does Cassandra swallow a huge write stream? Sequential SSTables. Why do indexes slow down inserts in PostgreSQL? Each one is another B-tree to update. Why must ClickHouse data be sorted by the table key? MergeTree is LSM's relative — the sort order is its index. Why doesn't PostgreSQL start instantly after a crash? It is replaying the WAL.
Where beginners stumble:
- Comparing databases by marketing, not by engine. "NoSQL is faster" is meaningless; faster at writes and why — that is the question, and the answer lives in the storage engine.
- Forgetting that an index is not free. Five indexes on a table are five trees updated on every insert.
- Not watching compaction. An LSM database without compaction monitoring quietly piles up segments until the disk runs out or reads degrade.
- Being scared of the word WAL. It is not exotic — it is the reason the database survives a power cut, and replication and backups are built on it.
What to read next: OLTP and OLAP — how the access pattern shapes both the engine and the whole storage architecture; PostgreSQL index types — the B-tree from the user's side; ClickHouse modeling — MergeTree in practice. The primary source is Martin Kleppmann, "Designing Data-Intensive Applications," chapter 3.