June 4, 2026

databasesstorage-enginesinternalsmysqlpostgresrocksdbcassandraclickhouseredis

Database Storage Engines — Physical Layout, Logical Design, and the Papers Behind Them

Every database sits on top of a storage engine — the layer that decides how rows become bytes on disk, how concurrent readers and writers are isolated, and how the database survives a crash. The engine shapes every performance tradeoff you will ever hit: write throughput, read latency, space amplification, and recovery time.

This post covers four major architectures — B+ Tree (InnoDB, PostgreSQL), LSM Tree (RocksDB, Cassandra), Columnar (ClickHouse, Parquet), and In-Memory (Redis) — with enough internals to make tuning decisions legible.

The Papers That Started It All

Paper	Year	Contribution
Bayer & McCreight — Organization and Maintenance of Large Ordered Indexes	1972	Invented the B-Tree
Gray & Reuter — Transaction Processing: Concepts and Techniques	1992	ACID, locking, WAL
Mohan et al. — ARIES: A Transaction Recovery Method	1992	Write-ahead logging, redo/undo recovery
Stonebraker & Rowe — The Design of POSTGRES	1987	MVCC via tuple versioning, no in-place updates
O'Neil et al. — The Log-Structured Merge-Tree (LSM-Tree)	1996	Foundation for all LSM engines
Chang et al. — Bigtable: A Distributed Storage System for Structured Data	2006	SSTable format, compaction, column families
Stonebraker et al. — C-Store: A Column-Oriented DBMS	2005	Columnar compression and late materialisation
Melnik et al. — Dremel: Interactive Analysis of Web-Scale Datasets	2010	Nested record encoding in columnar format
Abadi et al. — Column-Stores vs. Row-Stores: How Different Are They Really?	2008	Quantified columnar vs row-store OLAP tradeoffs

1. B+ Tree Storage Engine

The B+ Tree is the default for relational databases. It was designed for disk-based random access and has dominated OLTP for fifty years because it balances reads, writes, and data locality in one structure.

Inspired by: Bayer & McCreight (1972) for the tree itself; ARIES (Mohan et al., 1992) for durability; Stonebraker & Rowe (1987) for PostgreSQL's specific MVCC design.

InnoDB (MySQL)

Pages — The Unit of Everything

InnoDB organises every .ibd table file into fixed 16 KB pages. A page is the unit of I/O — InnoDB always reads and writes one full page at a time, aligning with the OS virtual memory system. Each page has a small header (checksum, page type, LSN for crash recovery, prev/next pointers for the leaf chain) and a footer that duplicates the LSN for torn-write detection.

Inside a B+ Tree, internal pages carry routing keys and child page pointers. Leaf pages carry the actual row data, sorted by primary key, linked in a doubly-linked chain for range scans. A table with 100 million rows and a branching factor of ~400 per page needs only 3–4 levels, so most point lookups touch 3–4 pages.

B+ Tree:
                      [root]
               /        |        \
        [internal]  [internal]  [internal]    ← routing keys + child pointers
         /    \       /    \       /    \
       [L]←→[L]←→[L]←→[L]←→[L]←→[L]        ← leaf pages: full rows, doubly linked

Leaf page layout is sparse-indexed internally: a small page directory at the end of the page holds one slot per ~~8 records pointing into the record chain. A lookup binary-searches the directory (~~log(N/8) steps) then walks the chain for the last few records (~O(8)). This avoids storing a separate dense index for every row on the page.

The Buffer Pool

The buffer pool is InnoDB's page cache in RAM — the single most impactful performance lever. Every read and write goes through it.

A hash table maps (tablespace_id, page_number) → buffer frame pointer. A cache hit returns the frame in nanoseconds; a miss triggers a 16 KB pread() from the .ibd file.
The LRU list has a midpoint: new pages enter at the midpoint (the "old" half), not the head. Only pages accessed again within innodb_old_blocks_time (default 1 s) get promoted to the hot "young" half. This prevents a full-table scan from evicting hot OLTP pages.
The flush list tracks dirty pages ordered by LSN so the page cleaner thread can flush them in WAL order.

When the buffer pool is full and a miss occurs, InnoDB evicts a victim from the old sublist tail. If dirty, it flushes first. The larger the buffer pool, the fewer evictions and disk reads.

Clustered Index and Secondary Indexes

InnoDB's primary key is a clustered index: the leaf pages are the rows, physically sorted by PK. There is no separate heap — the table is the tree. This gives excellent locality for PK lookups and range scans.

Secondary indexes store (secondary_key, primary_key) at their leaf nodes. A secondary index lookup therefore does a double lookup: first find the PK in the secondary index, then traverse the clustered index again to fetch the full row. If the queried columns are all in the secondary index (covering index), the second lookup is skipped.

MVCC — Undo Log

Each row carries two hidden columns: DB_TRX_ID (transaction that last wrote it) and DB_ROLL_PTR (pointer into the undo log). When a transaction reads a row written by a newer transaction, it follows DB_ROLL_PTR through the undo log chain to reconstruct the version visible to its snapshot. Old versions live in the undo tablespace, not in the data pages.

Leaf page (current version):
  DB_TRX_ID=1050 | DB_ROLL_PTR ──► undo entry (txn 900) ──► undo entry (txn 700)

Reader with snapshot before txn 1050 → follows chain, reads txn 700 version

Write Path

On an INSERT, InnoDB: writes a redo record to the in-memory log buffer, modifies the target leaf page in the buffer pool (splitting the page if full), writes an undo log entry for MVCC, and on commit fsyncs the redo log buffer to disk. The data page stays dirty in the buffer pool and is flushed asynchronously by the page cleaner. The redo log guarantees the write is recoverable even before the page reaches disk.

On a page split (leaf full), InnoDB allocates a new page, redistributes records, updates parent pointers — potentially cascading up but rarely reaching the root. UUID primary keys cause frequent random splits because inserts land at arbitrary positions; auto-increment PKs append to the rightmost leaf and split predictably.

Read Path

On a SELECT, InnoDB traverses the B+ Tree from the root (almost always in the buffer pool) to the target leaf. Each internal page lookup is a buffer pool hash check — usually a hit. For the leaf page: hash check → hit (no I/O) or miss (16 KB pread). After reading the leaf, InnoDB binary-searches the page directory, walks the record chain to the matching row, checks MVCC visibility via DB_TRX_ID against the transaction's read snapshot (following the undo chain if needed), and extracts the column bytes.

For range scans, InnoDB follows the doubly-linked leaf chain after finding the start position, prefetching pages ahead via linear read-ahead when it detects sequential access.

Tuning Parameters

Parameter	Default	What it controls
`innodb_buffer_pool_size`	128 MB	Most impactful. Set to 70–80% of RAM. More = more pages cached = fewer disk reads.
`innodb_buffer_pool_instances`	8 (if >1 GB)	Partition pool into N independent LRUs to reduce mutex contention. Match to CPU cores (up to 8).
`innodb_redo_log_capacity`	100 MB	Larger = fewer checkpoints = better write throughput. Set to hold at least 1 hour of writes.
`innodb_log_buffer_size`	16 MB	In-memory buffer for redo records before fsync. Increase for large transactions.
`innodb_flush_log_at_trx_commit`	1	1 = fsync on every commit (fully ACID). 2 = write to OS buffer, fsync every second. 0 = flush every second (can lose 1 s on crash).
`innodb_flush_method`	`fsync`	`O_DIRECT` bypasses OS page cache (avoids double-caching). Recommended for SSDs.
`innodb_io_capacity`	200	Background flush IOPS budget. Set to actual disk IOPS (SSD: 2000–10000).
`innodb_old_blocks_time`	1000 ms	Pages must be re-accessed within this window to move to the young (hot) LRU half. Increase to protect hot pages during large scans.
`innodb_change_buffer_max_size`	25	% of buffer pool for the change buffer. Defers secondary index writes for cold pages; merges on read.
`innodb_fill_factor`	100	% of page to fill during index builds. Set to ~80 for random-insert workloads to reduce future splits.

PostgreSQL

Heap — No Clustered Index

PostgreSQL stores all rows in an unsorted heap file — literally a pile of 8 KB pages, one file per table. Every index (including the primary key) is a separate B-Tree file. Index leaf nodes store (key, ctid) where ctid is the physical (page_number, slot_number) address of the row in the heap.

A read therefore does two I/Os: one to find the ctid in the index, one to fetch the row from the heap. However, if all needed columns are in the index (index-only scan), and the visibility map confirms the heap page is fully visible to all transactions, the heap read is skipped entirely.

PostgreSQL has a CLUSTER command to physically reorder a table by an index, but the ordering drifts as rows are inserted and updated. There is no auto-clustering on writes.

MVCC — No Undo Log

PostgreSQL's defining choice: old row versions live directly in the heap. On UPDATE, the old tuple is kept in place with t_xmax set to the updating transaction. A new tuple is written to the heap with t_xmin set to the same transaction. Both versions coexist until VACUUM removes the dead one.

Heap page after UPDATE by txn 1050:
  slot 3: [t_xmin=700, t_xmax=1050, col='old']  ← dead; visible only to snapshots < 1050
  slot 4: [t_xmin=1050, t_xmax=0,   col='new']  ← live

A reader checks t_xmin and t_xmax against its snapshot — no undo log traversal. Fast for reads. The cost is dead tuple accumulation: VACUUM must scan and reclaim them, and all indexes must be updated on every UPDATE because the ctid of the live tuple changes.

HOT (Heap-Only Tuple) is an optimisation: if an updated row fits on the same page and the updated columns are not indexed, the new tuple links back to the old via a redirect chain and indexes are not touched.

Shared Buffer Cache and OS Page Cache

PostgreSQL's shared buffer cache (shared_buffers) is its in-memory page pool, but unlike InnoDB, PostgreSQL also relies heavily on the OS page cache as a second tier. Data read from disk passes through both: kernel page cache → shared buffer frame. This double-buffering is a known inefficiency but means that even data not in shared_buffers may still be served from RAM by the OS.

The cache uses a clock sweep for eviction: a "hand" sweeps through buffer descriptors, decrementing a usage_count (0–5) on each pass and evicting the first frame with count=0. Simpler than InnoDB's partitioned LRU, but no midpoint protection — large sequential scans use a separate ring buffer strategy to avoid polluting the cache.

The visibility map (_vm file, 2 bits per heap page) tracks whether all tuples on a page are visible to every transaction. Index-only scans check the VM first; if a page is all-visible, the heap page is never read. The VACUUM process sets VM bits, so regular autovacuum directly improves query performance.

The free space map (_fsm file) tracks available free bytes per page so inserts can find a suitable page without scanning the heap.

TOAST

Values larger than ~2 KB are automatically moved to a separate TOAST table (compressed and chunked). The main row stores a pointer. TOAST is fetched only when that column is actually accessed — large text/JSON fields cost nothing to I/O if they are not in the SELECT.

Write and Read Path

On INSERT, PostgreSQL finds a heap page with enough free space (via FSM), writes the WAL record to WAL buffers, inserts the tuple into the page (updating the slot array and free-space pointers), and marks the buffer dirty. On commit, WAL buffers are flushed to pg_wal/ (fsync if synchronous_commit=on). Dirty heap pages are written later by bgwriter and checkpointer.

On SELECT with an index: traverse the index B-Tree to get ctid, check the visibility map, then read the heap page at the physical offset encoded in ctid. Check t_xmin/t_xmax against the transaction snapshot — usually answered from cached hint bits in the tuple header without consulting pg_xact. If TOAST columns are needed, fetch them from the TOAST table.

Tuning Parameters

Parameter	Default	What it controls
`shared_buffers`	128 MB	Primary page cache. Set to ~25% of RAM — leave the rest for the OS page cache.
`effective_cache_size`	4 GB	Planner hint for total available memory (shared_buffers + OS cache). Set to ~75% of RAM. Affects index vs seqscan cost estimates.
`work_mem`	4 MB	Memory per sort/hash per query node. Each parallel worker gets its own. Start at 16–64 MB; watch total = connections × workers × work_mem.
`maintenance_work_mem`	64 MB	Memory for VACUUM, CREATE INDEX. Increase to 1–2 GB for large tables.
`synchronous_commit`	`on`	`on` = fsync WAL before returning. `off` = return before fsync (3–5× throughput, can lose last ~200 ms of commits on crash).
`checkpoint_timeout`	5 min	Time between checkpoints. Increase to 15–30 min to reduce checkpoint I/O frequency.
`max_wal_size`	1 GB	WAL accumulation before forcing a checkpoint. Increase to 4–16 GB for write-heavy loads.
`random_page_cost`	4.0	Planner's cost of a random page read. Set to 1.1 for SSD — makes the planner use index scans instead of seqscans.
`effective_io_concurrency`	1	Concurrent I/Os the OS can serve. Set to 200 for SSD. Controls prefetch depth for bitmap heap scans.
`autovacuum_vacuum_scale_factor`	0.2	Fraction of table with dead tuples before autovacuum triggers. Reduce to 0.01–0.05 for large tables.
`autovacuum_vacuum_cost_delay`	2 ms	Throttle between VACUUM I/O bursts. Reduce to 0–1 ms for SSDs.

2. LSM Tree Storage Engine

LSM (Log-Structured Merge-tree) was invented to solve the random-write bottleneck of B-Trees: instead of seeking to an arbitrary page and modifying it, every write is a sequential append. All random writes become sequential — as fast as the storage medium allows.

Inspired by: O'Neil et al. — The Log-Structured Merge-Tree (1996). SSTable format and compaction come from Chang et al. — Bigtable (2006). LevelDB (Jeff Dean & Sanjay Ghemawat, 2011) was the first open-source implementation; RocksDB is Facebook's high-performance fork.

How Sorting Works — MemTable to SSTable

Every write goes into a MemTable first — an in-memory sorted structure (skip-list in RocksDB) that maintains key order on every insert at O(log n).

MemTable skip-list after inserts (apple, mango, cherry, banana):

Level 3: HEAD ─────────────────────── mango ── TAIL
Level 2: HEAD ──────── cherry ─────── mango ── TAIL
Level 1: HEAD ── apple ── cherry ──── mango ── TAIL
Level 0: HEAD ── apple ── banana ── cherry ── mango ── TAIL
                 seq=1     seq=2      seq=3     seq=4

When the MemTable hits its size limit (e.g., 64 MB), it freezes and a background thread flushes it to disk by iterating in sorted order and writing one sequential SSTable file. Every byte written to an SSTable is written once, sequentially — no random I/O.

Write path:
  client.Put(key, value)
    → WAL append (sequential, crash-safe)
    → MemTable insert (O(log n), sorted in memory)
    → [when full] flush → L0 SSTable (immutable, sorted, sequential write)
    → background compaction: L0 → L1 → L2 → ...

SSTable Internal Structure and the Sparse Index

An SSTable is an immutable, sorted file. Internally it is divided into ~4 KB data blocks, each holding a sorted run of key-value pairs (compressed). The index block — the sparse index — stores only the last key of each data block, plus that block's file offset.

SSTable file:
┌──────────────────────────────────────┐
│ Data Block 0: [alice→v1][bob→v2][carol→v3]   ← sorted, compressed (~4 KB)
│ Data Block 1: [dave→v4][eve→v5][frank→v6]
│ Data Block 2: [grace→v7][hank→v8][ivan→v9]
├──────────────────────────────────────┤
│ Index Block (sparse):                │
│   "carol" → offset=0,    size=4096  │  ← last key of block 0
│   "frank" → offset=4096, size=4096  │  ← last key of block 1
│   "ivan"  → offset=8192, size=4096  │  ← last key of block 2
├──────────────────────────────────────┤
│ Bloom Filter Block                   │  one per SSTable — "is key in this file?"
├──────────────────────────────────────┤
│ Footer                               │  offsets to index + bloom filter blocks
└──────────────────────────────────────┘

To find key "eve":

Load the index block (small, usually cached in memory)
Binary search: "carol" < "eve", "frank" ≥ "eve" → key is in data block 1
Read and decompress data block 1 from offset 4096
Scan within the block → find eve

The index is sparse because it only needs one entry per block, not per key. For a 256 MB SSTable with 4 KB blocks, the index has ~~65 K entries (~~2 MB total) — easily held in memory.

Bloom Filters

A key may exist in the MemTable, an immutable MemTable being flushed, or any SSTable at any level. Checking all of them naively is expensive. Each SSTable carries a Bloom filter — a compact bit-array that answers "definitely not in this file" with zero false negatives.

Get("eve"):
  1. Check MemTable → miss
  2. For each SSTable (newest first):
       bloom.MayContain("eve")? → NO  → skip this file entirely (no disk read)
                                  YES → binary-search index → read data block → scan
  3. Return first match

At 1% false positive rate, a Bloom filter uses ~10 bits per key. A 100M-key SSTable needs ~120 MB of filter — much cheaper than loading data. The block cache (RocksDB's equivalent of the buffer pool) keeps index blocks and Bloom filters in memory so they never cost a disk read.

How Compaction Merging Works

Compaction merges multiple SSTables into one (or more) new SSTables, sorting the output and discarding stale/deleted versions. It is an N-way merge sort.

Before compaction (L0 — files may overlap):

SSTable A (oldest):  [alice:seq=1] [bob:seq=3]   [carol:seq=5]
SSTable B:           [bob:seq=7]   [dave:seq=9]  [eve:seq=11]
SSTable C (newest):  [alice:seq=12][carol:seq=14][frank:seq=15]

Compaction — N-way merge with a min-heap:

Open one sorted iterator per SSTable.
Push each iterator's first entry into a min-heap keyed by (key ASC, seq DESC).

Heap step-by-step:
  Pop alice:seq=12 (C) → write to output (newest alice)
  Pop alice:seq=1  (A) → SKIP (same key, older)
  Pop bob:seq=7    (B) → write to output (newest bob)
  Pop bob:seq=3    (A) → SKIP
  Pop carol:seq=14 (C) → write to output (newest carol)
  Pop carol:seq=5  (A) → SKIP
  Pop dave:seq=9   (B) → write to output
  Pop eve:seq=11   (B) → write to output
  Pop frank:seq=15 (C) → write to output

After compaction (L1 — no overlaps, one entry per key):

[alice:seq=12] [bob:seq=7] [carol:seq=14] [dave:seq=9] [eve:seq=11] [frank:seq=15]

Tombstones (delete markers) are kept through all levels until the bottom level, where no older copy can exist and the tombstone is finally dropped.

Leveled Compaction

L0: [A: alice–carol] [B: bob–eve] [C: alice–frank]   ← overlapping, 4 files → trigger
      ↓ compact all L0 files + overlapping L1 files
L1: [alice–frank]                                     ← sorted, non-overlapping, ≤10 MB
      ↓ L1 full → compact one L1 SSTable into L2
L2: [alice–dave] [eve–zara]                           ← sorted, non-overlapping, ≤100 MB
      ↓
L3: [alice–bob] [carol–eve] [frank–mango] [nate–zara] ← ≤1 GB

At L1 and below, key ranges within a level never overlap — a point read needs at most one SSTable per level (binary search on file key ranges) plus its Bloom filter.

3. Columnar Storage Engine

Columnar engines store all values of each column together rather than all columns of each row together. A query reading 2 of 50 columns touches 4% of the data a row-store would read.

Inspired by: Stonebraker et al. — C-Store (2005), Abadi et al. — Column-Stores vs. Row-Stores (2008), Melnik et al. — Dremel (2010). ClickHouse (Yandex, open-sourced 2016) brought real-time columnar OLAP to large-scale production.

The Example Table

row │ date       │ region │ product │ price │ qty
────┼────────────┼────────┼─────────┼───────┼────
 1  │ 2024-01-01 │ US     │ Widget  │  9.99 │ 10
 2  │ 2024-01-01 │ US     │ Widget  │  9.99 │  5
 3  │ 2024-01-01 │ EU     │ Gadget  │ 19.99 │  2
 4  │ 2024-01-02 │ US     │ Widget  │  9.99 │  8
 5  │ 2024-01-02 │ EU     │ Widget  │  9.99 │  3
 6  │ 2024-01-02 │ EU     │ Gadget  │ 19.99 │  1
 7  │ 2024-01-03 │ US     │ Gadget  │ 19.99 │  4
 8  │ 2024-01-03 │ US     │ Widget  │  9.99 │  6

Columnar storage splits this into one contiguous sequence per column:

date.bin:    [2024-01-01][2024-01-01][2024-01-01][2024-01-02]...
region.bin:  [US][US][EU][US][EU][EU][US][US]
product.bin: [Widget][Widget][Gadget][Widget][Widget][Gadget][Gadget][Widget]
price.bin:   [9.99][9.99][19.99][9.99][9.99][19.99][19.99][9.99]
qty.bin:     [10][5][2][8][3][1][4][6]

The N-th value in every file corresponds to the same row — position is the identity. There are no row IDs. For SELECT AVG(qty) WHERE region = 'US', only region.bin and qty.bin are read. date.bin, product.bin, and price.bin are never touched.

Dictionary Encoding

For low-cardinality columns (region, product, status), replace each string with a small integer code and store only the codes.

product column:
  Raw:        [Widget, Widget, Gadget, Widget, Widget, Gadget, Gadget, Widget]
  Dictionary: {Widget=0, Gadget=1}
  Codes:      [0, 0, 1, 0, 0, 1, 1, 0]
  Bit-packed: 00100011  ← 8 values packed into 1 byte (1 bit each, since 2 distinct values)

  Raw storage: 8 × ~6 bytes = 48 bytes
  Encoded:     dictionary (14 bytes) + codes (1 byte) = 15 bytes  →  3× compression

ClickHouse's LowCardinality(String) type enables this. Equality filters on codes compare integers instead of strings — much faster for both filtering and grouping.

Run-Length Encoding (RLE)

RLE replaces consecutive repeated values with (value, count) pairs. It is only effective when data is sorted — the same value appears in long runs. This is why the sort key matters so much.

Without sorting:

region: [US, US, EU, US, EU, EU, US, US]
RLE:    [(US,2), (EU,1), (US,1), (EU,2), (US,2)]  → 5 pairs, worse than 8 raw values

After sorting by (date, region):

region: [EU, US, US, EU, EU, US, US, US]
RLE:    [(EU,1), (US,2), (EU,2), (US,3)]  → 4 pairs

product (sorted): [Gadget, Widget, Widget, Widget, Gadget, Widget, Widget, Gadget]
Dict codes:       [1, 0, 0, 0, 1, 0, 0, 1]
RLE on codes:     [(1,1), (0,3), (1,1), (0,2), (1,1)]  → 5 pairs vs 8 codes

RLE + dictionary combined is the standard: store small integer codes with run-length compression on top.

Bitmap Encoding

For low-cardinality equality filters, store one bit per row for each distinct value:

region column (original order):
  Bitmap for US: 1 1 0 1 0 0 1 1  →  0b11010011  →  1 byte
  Bitmap for EU: 0 0 1 0 1 1 0 0  →  0b00101100  →  1 byte

WHERE region='US' AND product='Widget':
  Bitmap(region='US'):   11010011
  Bitmap(product='Widget'): 11011001
  AND:                   11010001  →  rows 1, 2, 4, 8

This AND operation is a single 64-bit instruction per 64 rows. SIMD instructions process 256 or 512 bits at once, enabling billions of rows per second for simple filter queries. Roaring Bitmaps (used in ClickHouse, Druid, Pinot) extend this with adaptive compression for sparse bitmaps.

Delta Encoding

For sorted numeric or timestamp columns, store only the differences between consecutive values:

date column (as Unix seconds, sorted):
  Raw:    [1704067200, 1704067200, 1704067200, 1704153600, 1704153600, ...]
  Deltas: [0, 0, 0, 86400, 0, 0, 86400, 0]  ← values fit in 17 bits, not 32
  RLE:    [(0,3), (86400,1), (0,2), (86400,1), (0,1)]  ← excellent after sorting

Delta encoding shrinks the bit width of values, enabling aggressive bit-packing before general compression (LZ4/Zstd).

How the Sort Key Works

The sort key physically orders rows within each data part. This is the single most impactful schema decision:

CREATE TABLE sales (
    date    Date,
    region  LowCardinality(String),
    product LowCardinality(String),
    price   Float64,
    qty     UInt32
) ENGINE = MergeTree()
ORDER BY (date, region, product);

After sorting by (date, region, product), the sparse primary index stores the first key value of every 8192-row granule. A query filtering on date = '2024-01-02' AND region = 'EU' binary-searches the index to find the matching granule range and reads only those granules — skipping the rest without touching disk.

primary.idx (one entry per 8192 rows):
  Granule 0: (2024-01-01, EU, Gadget)   covers rows 0–8191
  Granule 1: (2024-01-05, US, Widget)   covers rows 8192–16383

Query: date='2024-01-02' AND region='EU'
  Binary search → Granule 0 only (2024-01-02 < 2024-01-05)
  → read ~8192 rows instead of 800M

A marks file (.mrk) maps each granule entry to its byte offset in each column file, so the engine seeks directly to the right compressed block.

Write Path — From INSERT to Disk

Columnar engines never modify existing data files. Every write creates a new data part (an immutable directory of column files), merged in the background.

INSERT INTO sales VALUES (...)
  ↓
1. Accumulate rows in an in-memory columnar block
   (anti-pattern: tiny inserts create many small parts → use batch inserts or async_insert)
  ↓
2. Sort the block by the ORDER BY key (in memory)
  ↓
3. For each column:
   encode (dictionary + RLE + delta) → split into compressed blocks → write to column.bin
   write one mark per block to column.mrk (byte offsets for seek)
  ↓
4. Write primary.idx (first key of each granule)
  ↓
5. Atomic rename: tmp_part/ → part/  (makes it visible instantly, no partial state)
  ↓
Background: merge small parts into larger parts (N-way merge sort, same as LSM compaction)
            → longer runs → better RLE → better compression

On disk each data part is a directory:

20240101_1_1_0/
  date.bin   date.mrk
  region.bin region.mrk
  product.bin product.mrk
  price.bin  price.mrk
  qty.bin    qty.mrk
  primary.idx
  checksums.txt

Materialized Views on Top of Columnar Storage

A columnar table has one sort order. Queries with a different leading filter column cannot use the sparse primary index — they must scan all granules. Materialized views solve this by keeping a pre-computed, physically separate projection with a different sort key or pre-aggregated data.

-- Source table sorted by (date, region, product)

-- MV 1: pre-aggregated daily totals — avoids reading raw rows for dashboards
CREATE MATERIALIZED VIEW sales_daily_mv TO sales_daily AS
SELECT date, region, SUM(qty) AS total_qty, SUM(price * qty) AS revenue
FROM sales GROUP BY date, region;

CREATE TABLE sales_daily (...) ENGINE = SummingMergeTree() ORDER BY (date, region);

-- MV 2: same data but with region as the leading sort key
CREATE MATERIALIZED VIEW sales_by_region_mv TO sales_by_region AS SELECT * FROM sales;

CREATE TABLE sales_by_region (...) ENGINE = MergeTree() ORDER BY (region, date, product);

How writes propagate:

INSERT INTO sales
  ├──► write new data part to sales/            (primary table)
  └──► for each MV: apply MV's SELECT, write result to MV's target table
       (synchronous — all succeed or all fail together)

Query routing:

WHERE date='2024-01-02' AND region='US'     → use sales (date is leading key)
WHERE region='EU'                           → use sales_by_region (region is leading key)
SUM(qty) GROUP BY date, region              → use sales_daily (pre-aggregated, tiny)

AggregatingMergeTree extends this further: each MV row stores a partial aggregate state (e.g., a HyperLogLog sketch for uniq()), and background merges combine partial states — enabling approximate distinct counts at near-zero query cost.

4. In-Memory Storage Engine

In-memory engines eliminate disk I/O from the read/write path. All data lives in RAM; durability is handled by an append-only log and/or periodic snapshots in the background.

Inspired by: DeWitt et al. — Main Memory Database Systems (1992). Redis (2009) and Memcached (2003) popularised the approach for caching workloads.

The primary data structure is a hash table keyed by the user key, pointing to typed value objects: strings, lists, hashes, sets, sorted sets (skip-lists), etc. A read or write resolves to a memory pointer — no page fetch, no lock manager, sub-microsecond latency.

Durability options (Redis):

RDB snapshot: fork the process, serialize the entire keyspace to a binary file. Point-in-time, compact. Recovery loads the file — fast but can lose up to the snapshot interval.
AOF log: append every write command as text. Replay on startup to reconstruct state. Durable to the last command (fsync-per-write mode) or last second (fsync-every-second). Larger file, slower recovery.
RDB+AOF hybrid (Redis 7.0+): AOF starts with an embedded RDB snapshot then appends only incremental commands. Fast recovery + good durability.

	In-Memory
Read / write latency	Sub-microsecond
Throughput	Millions of ops/sec per node
Durability	Asynchronous (last snapshot lag) or synchronous (fsync-per-write)
Capacity	Limited to available RAM
Recovery	Load RDB or replay AOF on startup

Popular implementations: Redis, Memcached, DragonflyDB, VoltDB (in-memory SQL with ACID).

Comparison

Engine	Physical unit	Logical model	Optimised for
B+ Tree (InnoDB)	16 KB pages, clustered B-Tree	Rows, SQL	OLTP — point reads, mixed writes
B+ Tree (PostgreSQL)	8 KB pages, heap + separate indexes	Rows, SQL	OLTP — rich query planning, MVCC
LSM Tree (RocksDB)	SSTable + WAL	Key-value, wide-column	Write-heavy, sequential I/O
Columnar (ClickHouse)	Data parts, column files	Rows (read as columns)	OLAP — aggregations over few columns
In-Memory (Redis)	Hash table + skip-list in RAM	Key-value, data structures	Ultra-low latency, cache

Write Amplification — B-Tree vs LSM Tree

Write amplification (WA) is bytes physically written per byte of user data. It determines SSD wear and disk I/O pressure.

B-Tree (InnoDB)

A single committed row touches disk in several places:

WAL (redo log): sequential fsync on commit — the only synchronous write
Doublewrite buffer: InnoDB writes the full 16 KB page to a safe area in ibdata1 before writing to the actual page location, protecting against torn writes — doubles the page write I/O
Data page: async 16 KB write by the page cleaner

With a warm buffer pool, many rows share one page flush. Effective WA ≈ 3–5× for typical OLTP. UUID primary keys hurt more: random inserts cause frequent page splits, each splitting into 2–3 page writes.

LSM Tree (RocksDB)

Writes are cheap upfront (WAL append + MemTable insert). The WA comes from compaction — data is rewritten once per level.

WA ≈ 1 (flush to L0) + size_ratio (L0→L1) + size_ratio (L1→L2) + ...
With size_ratio=10, 4 levels: WA ≈ 1 + 10 + 10 + 10 ≈ 30×

Compaction runs in the background and doesn't block foreground writes, but it competes for disk bandwidth.

HDD vs SSD Impact

HDD:
  Random write: 5–15 ms seek + 0.1 ms transfer per 16 KB
  Sequential write: 150–200 MB/s
  B-Tree random insert (cold page): ~30 ms (3 seeks: read leaf, write doublewrite, write page)
  LSM write: sequential → HDD-friendly, dramatically outperforms B-Tree for write-heavy loads

SSD (NVMe):
  Random write: 20–100 µs (100–200× faster than HDD)
  Sequential write: 1–7 GB/s
  B-Tree random insert: now only 50–200 µs → competitive
  LSM write: still sequential advantage, but write volume (WA 10–30×) causes SSD wear
  A 1 TB NVMe (600 TBW endurance) at WA=20: sustains ~30 TB of user writes before wearing out

Workload fit summary:
  Write-heavy + HDD  → LSM wins clearly (all I/O sequential)
  Read-heavy + HDD   → B-Tree wins (fewer seeks per read)
  Mixed + SSD        → B-Tree competitive; LSM for write-dominated
  Time-series + SSD  → LSM (append-only pattern = low actual WA, natural compaction)

Summary Table

Engine	Write amplification	Read amplification	Space amplification
B-Tree InnoDB	3–5×	3–4 page I/Os	Low (in-place, reuses pages)
B-Tree PostgreSQL	5–10× (all indexes updated on UPDATE)	1–2 I/Os + heap	Medium (dead tuples until VACUUM)
LSM leveled	10–30× (compaction per level)	~1 with bloom filters	Medium (stale until compaction)
LSM tiered	3–10× (fewer merge passes)	Higher (more files per level)	Higher
Columnar	2–5× (batch writes amortise)	columns/total (e.g., 2/50 = 4%)	Low (5–15× compression)
In-Memory	~1× (AOF only)	0 disk I/Os	1× (no compression by default)

The right engine is the one whose amplification profile matches your workload — not the one with the longest feature list.