Storage Engines — DB Notes

How a database actually lays data out on disk — the two dominant designs are B-trees and LSM-trees, and they make opposite trade-offs.

An index tells you what structure makes lookups fast; a storage engine decides how writes actually land on disk underneath that structure. The two dominant designs — B-trees and LSM-trees — make opposite trade-offs between write and read performance.

Fig. 3 — What happens to a write, B-tree vs. LSM-tree

Click a stage to see what happens there.

B-trees: update in place

A B-tree storage engine finds the exact on-disk page a key belongs on and overwrites it directly. This keeps reads simple — there’s always exactly one, current copy of each key — but writes involve random I/O: the page being updated could be anywhere on disk. Most traditional relational databases (PostgreSQL, MySQL/InnoDB, SQLite) default to this design.

LSM-trees: append, then merge

An LSM-tree (Log-Structured Merge-tree) never updates a page in place. Writes are appended to an in-memory memtable; once that fills up, it’s flushed to disk as an immutable, sorted SSTable. A background compaction process later merges SSTables together, discarding overwritten or deleted keys. Databases like Cassandra, RocksDB, and LevelDB use this design.

-- Same INSERT, very different disk behavior underneath depending on engine:
INSERT INTO events (id, payload) VALUES (42, '{"type": "click"}');