← DDIA

Chapter 03 · Storage & Retrieval

Storage & Retrieval

The world's simplest database is two lines of bash. Here's why it fails, and what replaces it.

Writes are easy. Reads without an index aren't. Every storage engine is a different bet on which one you'd rather pay for.

Three acts: 1. log 2. engine 3. workload

The log

Bitcask in ~40 lines: append writes, index reads.

db (append-only) 42, "world" @ 0 88, "hello" @ 15 hash index query O(n) scan · newest first O(1) seek by hash

Writes append. Reads seek by hash. Works until the index outgrows RAM, or you need a range scan.

The engine

B-tree · LSM-tree · how LSM stays fast.

pages of sorted keys, rewritten in place. Random I/O per write.

30 60 → page @ 0x18 10 22 page @ 0x7A 40 55 57 page @ 0x33 70 88 insert 57 disk · physical layout 0x18 0x33 0x7A random I/O · in-place rewrite needs a WAL

writes hit an in-memory memtable. When full, it flushes as a whole SSTable, sequentially appended.

W writes memtable · in RAM SORTED disk · sequential append SSTable-01 03 12 27 · 48 61 82 sequential · flush appended at end

background merge folds overlapping SSTables into one. Dedupe, reclaim, one sequential file.

merge worker · reads N, writes 1 SSTable-A 03, 12, 27, 48, 61 SSTable-B 05, 27, 33, 61, 74, 89 SSTable-C 08, 27, 40, 55, 74, 91 SSTable-D 03, 05, 08, 12, 27, 33, 40… disk · before → after SSTable-A SSTable-B SSTable-C merge · dedupe · one sequential file

Takeaway

LSM-trees turn random writes into sequential ones. That's the whole trick.

Row vs Column

Same rows, two physical layouts. Same data, opposite workloads.

ROW STORE WHERE id = 2
1 Ali US 120
2 Bea EU 180
3 Cai US 95
4 Dev US 210

OLTP · fetch full rows.

COLUMN STORE AVG(salary) WHERE region='US'
id 1, 2, 3, 4
name Ali, Bea, Cai, Dev
region US, EU, US, US
salary 120, 180, 95, 210

OLAP · scan few columns of many rows.

── Reference ──

Three engines · two layouts · five things to remember.

Storage engines, side by side
Engine Best for Read cost Write cost Space Examples
Hash index Point lookups, small keyspace O(1) if index in RAM; disk seek on miss O(1) append + index update Whole index must fit in RAM Bitcask, Riak's Bitcask backend
B-tree Balanced OLTP O(log n) disk seeks O(log n) + WAL fsync Fragmentation, ~70% fill factor PostgreSQL, MySQL/InnoDB, SQL Server
LSM-tree Write-heavy; range scans O(log n) across levels; bloom filters help O(1) memtable append; batched flush Write amplification 5–30× before compaction RocksDB, LevelDB, Cassandra, HBase
Row-oriented vs column-oriented
Row-oriented Column-oriented
Layout Whole row contiguous on disk One column across many rows contiguous
Best for OLTP: fetch a whole record OLAP: aggregate over one column
Compression Low (heterogeneous types adjacent) High (values in a column repeat)
Write pattern Update one row, touch one page Update one row, touch many files (usually rewritten in bulk)
Examples PostgreSQL, MySQL, MongoDB Parquet, ORC, Vertica, Redshift, BigQuery

Hash index → point lookups only; whole index in RAM.

B-tree → in-place updates; balanced tree; random I/O.

LSM-tree → append-only; sequential writes; background compaction.

Row-oriented → OLTP: one whole record at a time.

Column-oriented → OLAP: one column across many records.