Storage Engines

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.

B-trees: update in place

A B-tree storage engine finds the exact on-disk page a key belongs on and overwrites it directly. Reads are simple — there’s always exactly one, current copy of each key, reachable in ~4–5 page reads. Writes involve random I/O: the page being updated could be anywhere on disk, and a small update still rewrites a whole page (plus a WAL entry).

Databases: PostgreSQL, MySQL/InnoDB, SQLite, SQL Server, Oracle — essentially every traditional OLTP relational database.

LSM-trees: append, then merge

An LSM-tree (Log-Structured Merge-tree) never updates a page in place. Writes append to an in-memory memtable; when it fills, it’s flushed to disk as an immutable, sorted SSTable. A background compaction process merges SSTables, discarding overwritten and deleted keys. A read may have to check the memtable and several SSTables (newest first) to find the current value — helped by per-SSTable Bloom filters that cheaply rule out “this key isn’t here”.

Databases: Cassandra, ScyllaDB, RocksDB / LevelDB, MyRocks (RocksDB under MySQL), TiKV (TiDB), HBase, InfluxDB, and Kafka Streams / Flink state stores.

Which engine for which workload

Metrics, logs, event sourcing, IoT ingestion, time-series, a write-heavy queue — LSM. The workload is “append enormous volume, rarely update, read recent ranges”. Sequential writes and cheap ingest are exactly what LSM is built for. This is why Cassandra and InfluxDB dominate observability and sensor data.

A typical web/OLTP app — user accounts, orders, inventory, lots of point reads and in-place updates, latency-sensitive — B-tree. Predictable single-page reads and no compaction to fall behind. Postgres/InnoDB is the safe default and you should need a specific reason to leave it.

Very high sustained write rate on commodity SSDs, willing to tune — LSM (often MyRocks or RocksDB directly). Companies have migrated large MySQL fleets from InnoDB to MyRocks specifically to cut write amplification and fit more data per node.

Analytics / aggregations over huge scans — neither; that’s a column store (ClickHouse, DuckDB, Parquet, Redshift, BigQuery). It stores each column contiguously so a SUM(amount) reads only that column. Worth knowing this third family exists.

The operational gotchas

Tombstones (LSM). A delete isn’t a delete — it writes a tombstone marker that shadows the key until compaction removes it. Cassandra anti-pattern: a queue table where rows are inserted and quickly deleted accumulates millions of tombstones, and a range scan has to read through all of them. SELECTs time out on a table that looks empty.

Bloat and vacuum (B-tree / Postgres). MVCC keeps old row versions until VACUUM reclaims them. A table with heavy UPDATE/DELETE churn and vacuum not keeping up grows on disk and indexes bloat, slowly degrading every query.

SSD endurance. Both engines wear flash, but write amplification directly shortens drive life. On write-heavy fleets this is a real hardware-cost line item, and a reason teams care about the amplification numbers.

-- Same INSERT, very different disk behavior underneath depending on engine:
INSERT INTO events (id, payload) VALUES (42, '{"type": "click"}');
-- B-tree: locate page for key 42, modify in place, WAL.
-- LSM:    append to memtable; flush + compact later.