What it is
A storage engine is the single-node component that turns get and put into disk operations: how a write becomes durable,
how a key is found, and how space is reclaimed. Three designs cover almost every database you will name in an interview. A
B-tree updates pages in place; an LSM-tree appends writes and merges them in the background; Bitcask appends to a
log and keeps every key in an in-memory hash index.
Important
Key takeaway: The engine decides the read/write amplification trade-off, and the wrong choice caps your p99 no matter how well the distributed layer is designed. Append-dominated writes (events, metrics, versioned records) want an LSM-tree; read-heavy OLTP with range scans wants a B-tree; a key set that fits in RAM with point reads wants Bitcask.
When you care
Any “which database” answer eventually hits “and what is the storage engine underneath?”, and the follow-up “why is this write path fast?” is answered here. In most interviews, naming the engine and giving one sentence on why it matches the write pattern is enough. Go deeper (compaction strategy, bloom filter math) only when the interviewer pulls.
Note
Interview signal: “LSM, because every write is a fresh versioned record, so the write path is a sequential append and the cost moves to background compaction” is the one-sentence answer. Naming the read-side price (read amplification, mitigated by bloom filters) in the same breath is what makes it senior.
The three engines
| Engine | Write model | Read model | Good for | Watch out for |
|---|---|---|---|---|
| LSM-tree (RocksDB, Cassandra, LevelDB) | Append to a log and an in-memory table; flush to immutable sorted files; merge in the background | A point read checks the memory table, then a bloom filter and index per file | Write-heavy workloads, large datasets, compressible values | Read amplification (several files per read); compaction I/O competing with foreground traffic |
| B-tree (InnoDB, PostgreSQL) | Update the page in place; write-ahead log for durability | O(log n) traversal; excellent range scans | Read-heavy, range queries, OLTP | Write amplification from random in-place updates; page splits and fragmentation under heavy writes |
| Bitcask (Riak’s default) | Append to a log; an in-memory hash maps every key to its disk offset | One disk seek: hash lookup, then read at the offset | A key set that fits in RAM; the fastest point reads | All keys must fit in memory; no range queries; needs a merge to reclaim space |
The write-ahead log
Both B-trees and LSM-trees put a write-ahead log (WAL) in front of everything. A write is first appended to the log (a sequential write, forced to disk), and only then applied to the in-memory structure. If the process crashes, the log is replayed to rebuild what was only in memory. The log is why a database can acknowledge a write without having updated its main data structure yet.
The durability knob is when the log is forced to disk: on every write (safest, slowest), in small groups (group commit, the usual compromise, many writes share one flush), or periodically (fast, with a window of possible loss). Say which you are choosing when you claim “durable”.
How an LSM-tree works
Writes are sequential appends. Reads pay for it by looking in more than one place.
- Write. Append to the WAL; insert into the memtable (a sorted in-memory structure).
- Flush. When the memtable is full, write it out as an immutable sorted file (an SSTable) at the top level. Sequential, fast.
- Compaction. Background jobs merge files, discard overwritten versions and deleted keys (tombstones), and keep the number of files small.
- Read. Check the memtable; then, for each file, ask its bloom filter whether the key could be there, and only read the file’s index and block if the answer is “maybe”. Merge the versions found and return the newest.
Compaction is the maintenance cost, and it has two main strategies:
| Strategy | How | Trade-off |
|---|---|---|
| Leveled (RocksDB default) | Each level has a size limit; files within a level cover disjoint key ranges | Better reads (a key lives in at most one file per level); higher write amplification |
| Size-tiered (Cassandra default) | Merge files of similar size together | Better write throughput; worse reads (a key may be in several files) |
The practical rule: leveled for read-heavy, size-tiered for write-heavy. An engine serving roughly three reads per write sits near the middle, so leveled with a generous compaction I/O budget is the usual call.
Worked example: why bloom filters pay for themselves. A point read for a key that does not exist would otherwise probe every file. With, say, 5 candidate files and a bloom filter at about 10 bits per key (roughly a 1% false-positive rate and no false negatives), the expected number of unnecessary file reads falls from 5 to 5 × 0.01 = 0.05. At a million reads a second, that is the difference between saturating the disks and barely touching them, which is why bloom filters are the LSM-tree’s standard read optimization. The cost is memory (about 10 bits per key per file) and a small false-positive rate.
Warning
Production reality: Compaction is where LSM engines get hurt. A burst of writes can build a backlog of files faster than compaction merges them; reads slow down (more files per read), and eventually the engine throttles writes to catch up. Watch the compaction backlog and the number of files per level, and give compaction its own I/O budget instead of letting it fight foreground traffic.
Choosing
| Workload | Engine | Because |
|---|---|---|
| Write-heavy ingest (time series, events, logs, metrics) | LSM-tree | Sequential appends; cost moves to the background |
| Mixed with versioned or append-only records | LSM-tree | Overwrites and deletes are just new records; compaction collapses them |
| Read-heavy OLTP, range scans, predictable latency | B-tree | One traversal, no multi-file merge |
| Billions of small keys that fit in RAM, point reads only | Bitcask | One seek per read, unbeatable throughput |
| Many secondary indexes | Be careful with either | Each index multiplies write amplification |
Bitcask’s limit is arithmetic: an index entry of about 64 bytes per key means a billion keys need roughly 64 GB of RAM, so 100 billion keys need about 6.4 TB, which is why it fits only small key sets.
Caution
Common mistake: Treating an LSM-tree as “faster” without the read-side cost, or a B-tree as “slower” without the workload. The engines move cost between reads and writes; neither removes it. Choose by which side your workload is dominated by.
Related
- Walkthrough: Designing a Distributed Database — the distributed layer that sits on top of the engine choice.
- Walkthrough: Designing a Distributed Key-Value Store — an append-heavy store where the LSM-tree’s write path is the natural fit.
- Reference: Database Indexing — B-tree vs LSM-tree from the query side: which index serves which access pattern.