5. Storage Engines: B-Trees vs LSM Trees

A storage engine sits below your query layer and decides how data lives on disk. The choice — B-tree or LSM-tree — drives performance characteristics that ripple through every higher layer.

5.1 The simplest "database"

db_set() { echo "$1,$2" >> database; }
db_get() { grep "^$1," database | tail -n 1 | cut -d, -f2; }

This append-only log has the world's best write performance (sequential append) and worst read performance (full scan). Real engines build on this insight: optimize writes via append, optimize reads via auxiliary structures.

5.2 Indexes

An index is a separate data structure that points into the primary data, enabling faster lookup. Every index speeds reads and slows writes (writes must update both data and index).

Hash indexes

In-memory hash map: key → file offset. Constant-time lookups. Used by Bitcask (Riak's predecessor).

Limits: must fit in RAM; no range queries; large keyspace impossible.

B-trees

The dominant index for the past 40 years. The default for Postgres, MySQL/InnoDB, Oracle, SQL Server, SQLite.

Structure: a balanced tree of fixed-size pages (typically 4 KB). Each internal node holds a sorted set of keys + pointers to children. Leaves hold key→value (or key→row pointer). Tree depth ~log_B(N), where B is fan-out (often 100s). A 4-level tree of 4KB pages with branching ~500 holds ~125M keys — every lookup is 4 disk reads.

Operations:

• Lookup: binary search at each level. O(log N).
• Range scan: leaves are linked → traverse sequentially.
• Insert: find leaf, insert, possibly split (and propagate splits upward).

Why B-trees can be slow on writes

• Every write modifies a 4KB page, even if the change is a few bytes → write amplification.
• Splits cause cascading writes.
• Random writes scatter across disk.

Crash safety: a partial page write corrupts the tree. Mitigated by a write-ahead log (WAL): log the change before mutating the page; replay on crash.

LSM-trees (Log-Structured Merge)

Built around the insight: sequential disk writes are 100× faster than random writes.

Operations:

• Write: append to in-memory sorted structure (memtable, e.g., a skiplist) + WAL.
• When memtable is full → flush to disk as an immutable sorted file (SSTable: Sorted String Table).
• Read: check memtable, then SSTables newest → oldest. Bloom filter per SSTable skips ones that definitely don't contain the key.
• Compaction: background process merges SSTables, drops overwritten/deleted keys.

LSM lineage: Google Bigtable paper (2006) → LevelDB (open source, Google) → RocksDB (Meta fork) → embedded into Cassandra, HBase, CockroachDB, TiDB, MyRocks, Kafka Streams (state stores), and many more.

B-tree vs LSM trade-offs

Property	B-tree	LSM
Write throughput	Lower (random writes)	Higher (sequential append)
Read latency	Lower (one tree walk)	Higher (multiple SSTables to check)
Space amplification	Lower (~1.1×)	Higher during compaction (2-10×)
Write amplification	Moderate (page rewrites)	High (compaction rewrites)
Range queries	Excellent	Good
Compression	Modest	Excellent (sorted, immutable SSTables)
Predictable latency	Yes	No (compaction stalls)
Best for	Reads, mixed workloads, low-latency OLTP	Heavy writes, time-series, append-mostly

Rule of thumb: write-heavy with looser read latency → LSM. Read-heavy or strict tail-latency → B-tree.

LSM compaction strategies

1. Size-tiered (Cassandra default): merge SSTables of similar size when N accumulate. Better write performance, more space amplification, can have hot bursts.
2. Leveled (LevelDB / RocksDB default): organize SSTables in levels; each level is N× the previous. Better read performance and space efficiency, more write amplification.

Google's experience: leveled compaction is usually right for OLTP-on-LSM.

5.3 Other index types

Secondary indexes

Index on non-PK columns. Two strategies:

• Local (per-shard) secondary index: each shard indexes its own data. Reads must scatter to all shards.
• Global secondary index: separate index, partitioned by the indexed column. Faster reads, but writes need a distributed transaction (or eventual consistency — DynamoDB GSIs are eventually consistent).

Multi-column / composite

Index on (a, b, c) supports queries on a, (a, b), (a, b, c) — but not b or c alone. Order matters.

Covering index

Index includes all columns needed by the query → no need to fetch the row. Massive speedup for read-heavy queries.

Partial / filtered index

Index only rows matching a predicate (e.g., WHERE status = 'active'). Smaller, faster.

Geospatial

• R-trees: bounding-box hierarchies for 2D / 3D ranges. Used by PostGIS.
• Geohash / S2 / H3: encode lat/lon to a 1D key, range-scan. S2 is Google's, H3 is Uber's. (See chapter 35, Uber.)

Full-text

Inverted index: term → list of doc IDs. (See chapter 25.)

5.4 Heap files vs clustered indexes

• Heap file (Postgres default): rows live unordered in a separate data file; index points to them. Multiple indexes are equally fast; clustering is via CLUSTER (one-shot).
• Index-organized table / clustered index (MySQL InnoDB, SQL Server default): the primary key index is the table. The PK order is the disk order. Range scans by PK are sequential. Secondary indexes hold the PK as the pointer, not a row offset → secondary lookup costs an extra PK lookup.

This is why MySQL devs care so much about PK choice (autoincrement vs UUID): UUIDs scatter inserts across the index → write amplification. ULID / KSUID (time-prefixed UUIDs) restore ordering.

5.5 In-memory engines

Memory is now cheap enough that whole working sets fit in RAM.

• Redis: in-memory KV with optional persistence (RDB snapshots + AOF log).
• Memcached: pure cache, no persistence.
• VoltDB, MemSQL/SingleStore: in-memory OLTP DBs.
• SAP HANA, kdb+: in-memory analytics.

Why faster: not "no disk I/O" (DBs cache hot pages already), but avoiding the overhead of encoding to a disk-friendly format. Pure in-memory data structures.

5.6 OLTP vs OLAP

	OLTP	OLAP
Pattern	Many small reads/writes by key	Few huge aggregates
Latency	< 100 ms	seconds–minutes OK
Volume per query	rows	millions–billions of rows
Storage layout	row-oriented	column-oriented
Engine examples	Postgres, MySQL, Spanner, DynamoDB	BigQuery, Snowflake, Redshift, ClickHouse, Druid

Row-oriented

Each row stored together. Good when you need most columns of a row.

Column-oriented

Each column stored together. Good when you read few columns from many rows.

• Compression: a column has fewer distinct values → much better compression (run-length, dictionary, bit-packing).
• Vectorized execution: process whole columns in CPU SIMD registers.
• Why analytics use it: aggregating one column over a billion rows touches one column, not the whole row.

Google's contribution: Dremel (2010 paper) → BigQuery. Distributed columnar with nested data (Protobuf-style).

5.7 Materialized views

Cached query result, refreshed periodically or on write. Trade write cost & staleness for read speed.

Variants:

• Simple cache (Redis with TTL)
• Postgres MATERIALIZED VIEW (refresh on demand)
• "Stream-table" join in Kafka Streams / Flink
• Pre-computed aggregates in Druid / ClickHouse

5.8 What an interviewer wants you to know

• B-trees for read-optimized OLTP.
• LSM-trees for write-heavy systems (Cassandra, RocksDB, Bigtable, Kafka).
• Indexes speed reads, slow writes, cost storage. Pick the smallest set that satisfies your query patterns.
• Column stores for analytics; row stores for OLTP.
• Compaction is the LSM tax; understand size-tiered vs leveled.

Key takeaways

• Sequential disk writes are ~100× random; LSM-trees exploit this and dominate write-heavy workloads.
• B-trees still win for low-latency reads and predictable behavior.
• Pick the index for your query pattern. Composite, covering, partial — each is a tool.
• Row vs column storage is the OLTP vs OLAP divide.