Storage Engines

What is it: A storage engine is the component responsible for how data is physically stored and retrieved on disk. Different engines optimize for different workloads.

B+Tree based (PostgreSQL heap, InnoDB): Data stored in heap files (pages containing row data). Indexes are separate B+Tree files. Random reads: O(log n). Random writes: update heap page + update index pages. Good for OLTP with mixed reads and writes, complex queries, ACID transactions. InnoDB (MySQL's default engine) uses a clustered index — the primary key B+Tree stores all row data in its leaf nodes (not heap files). Secondary indexes store the primary key as the value — a secondary index lookup always does a second lookup on the primary index.

graph TD subgraph bt["B+Tree engine: write updates in place"] w1["WRITE"] --> heap["heap page (update in place)"] heap --> idx["update every index"] end subgraph lsm["LSM engine: write is a sequential append"] w2["WRITE"] --> mem["memtable (in-memory)"] mem -->|"memtable full"| sst0["SSTable L0 (immutable)"] sst0 -->|"compaction"| sst1["SSTable L1 (merged, larger)"] sst1 -->|"compaction"| sst2["SSTable L2 ..."] end

LSM tree based (Cassandra, RocksDB, LevelDB): Writes go to an in-memory memtable + commit log. When the memtable is full, it is flushed to disk as an immutable SSTable (Sorted String Table). SSTables are periodically merged and compacted into larger files at deeper levels. Reads may need to check memtable + multiple SSTable levels (mitigated by bloom filters: each SSTable has a bloom filter that quickly answers "does this key exist here?" with no false negatives). Write-optimized: all writes are sequential appends. Read performance depends on compaction — freshly written data may require many SSTable merges on read. Used for high-write workloads where reads can tolerate slightly higher latency.

MyISAM (MySQL legacy): No transaction support. No foreign keys. Table-level locking only (all writes lock the entire table). Faster for pure read workloads (no MVCC overhead). Abandoned for most use cases in favor of InnoDB. Mentioned for historical context.

Choosing a storage engine: Default to B+Tree / PostgreSQL for OLTP (users, orders, financial data). Default to LSM / Cassandra for write-heavy append-only workloads (logs, time-series, activity feeds). The key insight: B+Tree is read-optimized (sorted data, O(log n) random reads); LSM is write-optimized (sequential writes, compaction defers read cost).

Common pitfall

Assuming an LSM engine's fast writes come for free is the trap — the cost is deferred, not eliminated, into compaction, and write amplification from repeated compaction passes can reach 10-30x the original write volume. A write-heavy LSM store that looks fast in a short benchmark can still saturate disk I/O under sustained load once compaction has to keep pace with incoming writes — the read/write cost that a B+Tree pays upfront, an LSM tree pays later, in the background, and it's easy to under-provision for that background cost specifically because it's invisible in a quick test.