Two families of on-disk storage
Every database persists rows through one of two dominant engine families:
| B-tree (page-oriented) | LSM (log-structured) | |
|---|---|---|
| Examples | Postgres heap + indexes, InnoDB, SQLite | RocksDB, LevelDB, Cassandra, Scylla |
| Write path | Find page → update in place | Append to memtable → flush SSTable |
| Read path | Tree descent, few seeks | Maybe check memtable + many SSTables |
| Compaction | Page merge/split | Background merge of sorted runs |
B-tree mechanics (interview depth)
Data lives in fixed pages (often 8 KiB). B+ trees keep keys sorted in internal nodes; leaves point to records (or hold them in clustered indexes). Inserts that overflow a page split it — random inserts cause scattered splits and write amplification.
Strengths: predictable point and range reads, mature concurrency on pages. Weakness: random write hotspots on the same leaf pages.
LSM mechanics
Writes go to an in-memory memtable (often a skip list or red-black tree), then flush to immutable SSTables on disk. Reads check memtable + SSTables from newest to oldest; Bloom filters skip absent keys.
Compaction merges SSTables in the background — trades read amplification now for write throughput earlier. Write amplification = bytes written to disk / bytes of user data (can be 10–30× under heavy update loads).
Write → memtable → flush → L0 SSTables → compaction → L1, L2, ...
Read → memtable → L0 → L1 → ... (newest wins for a key)
Choosing at system-design depth
| Workload | Favor |
|---|---|
| OLTP with mixed reads/writes, range scans | B-tree RDBMS |
| Write-heavy ingest, time-series, KV | LSM |
| Read-heavy, rarely updated | Either; B-tree simpler |
Cassandra is LSM under the hood; Postgres is B-tree — explaining why Cassandra ingest scales differently is a senior signal.
Column-oriented preview
Analytical stores (Parquet, ClickHouse) add a third axis — column files instead of row pages. Covered in Search & Columnar OLAP.
Not covered here
Generic OS block I/O and filesystem journaling — see OS → Persistence & I/O. Query plan reading — see SQL roadmap.
Where this goes next
WAL, Pages & Buffer Pool covers crash recovery and the in-memory cache layer sitting above whichever engine you chose.
Further Reading
Hands-On Tasks (Optional)
Low-setup exercises — schema drills, paper walkthroughs, or optional local installs. No autograding; the goal is interview fluency on how data is stored.
- Match engine to workload15m
For each workload — (a) heavy random point reads, (b) write-heavy time-series ingest, (c) range scans on sorted keys — pick B-tree or LSM and name one real product. Write one sentence on write amplification for your LSM pick.