Gowtham Potureddi

Posted on Sep 4

How Databases Store Data: Pages, B-Trees & LSM Trees

#python #sql #interview #dataengineering

Understanding how databases store data is the difference between guessing why a query is slow and knowing it — because every SELECT, INSERT, and UPDATE you write eventually turns into physical reads and writes against fixed-size database pages on disk, and the shape of the on-disk structure decides the cost. Beneath the SQL you type sits a storage engine: the component that lays rows out into pages, keeps an index over them, buffers hot pages in memory, and logs every change so a crash can't lose a committed transaction. Two on-disk index families dominate that layer — the read-optimized b-tree storage that Postgres and MySQL/InnoDB ship by default, and the write-optimized lsm tree that Cassandra, RocksDB, and ScyllaDB are built on — and the choice between them is the single most consequential storage decision an engineer makes.

This guide is the systems-interview walkthrough of that layer, the one you wish you had the first time an interviewer asked "what actually happens on disk when I run an UPDATE?" or "why is a B-tree fast for reads but an LSM tree fast for writes?" It works from the ground up: the fixed 8KB page and the heap files rows live in, the internal anatomy of a page layout (header, slot array, tuples, free space), B-trees traced from root to leaf, LSM trees from memtable to sstable to compaction, and finally the write-ahead log and buffer pool that together turn a memory-speed change into a durable one. Each section pairs a teaching block with a worked interview answer — code, a step-by-step trace, an output table, then a concept-by-concept breakdown of why it works.

When you want hands-on reps immediately after reading, drill the database practice library →, work the indexing practice library →, and sharpen query fluency on the SQL practice library →.

On this page

Why storage-engine internals decide every query's cost
Pages & the heap — the fundamental unit of storage
B-Tree storage — the read-optimized default
LSM Trees — memtable, SSTables, compaction
WAL, buffer pool & durability — how a write actually lands
Cheat sheet — storage-engine recipes
Frequently asked questions
Practice on PipeCode

1. Why storage-engine internals decide every query's cost

The stack beneath SQL is a chain of physical decisions, and the storage engine is where they all land

The one-sentence invariant: SQL is a declarative request, but the storage engine is where that request becomes physical reads and writes against fixed-size pages — so a query's cost is set not by how you phrase it but by how many pages the engine must fetch, how those pages are laid out on disk, and whether the change has to travel through a write-ahead log before it is safe. You can spend a career tuning SQL and never move the needle if you don't know that a WHERE id = 42 on a B-tree touches three or four pages while the same lookup against a heap with no index touches every page in the table. The storage engine is the layer that makes one of those O(log n) and the other O(n), and interviewers probe it because it is where "I know SQL" separates from "I know how a database works."

The stack from statement to disk block.

Query parser and planner. Turns your SQL string into a tree of relational operators, then picks a physical plan — index scan versus sequential scan, hash join versus nested loop. The planner's whole job is to minimise pages fetched, so it is reasoning about the storage layer even though you never see it.
Storage engine (access methods). Given "fetch the row where id = 42," the engine walks an index or scans a heap, translating logical row identity into a (page_id, slot) address. This is the layer this whole guide is about.
Buffer pool. A cache of pages in RAM. The engine never reads a row straight off disk — it asks the buffer pool for the page, which serves it from memory if it is resident or reads it from disk (a page fault) if not.
Disk / block device. The page is read or written as one aligned I/O against the underlying storage — an 8KB page maps cleanly onto filesystem and SSD block boundaries so the OS and hardware move it as a unit.

The one fixed unit everything is built on: the page.

A page is the atomic unit of I/O between disk and memory — typically 8KB in Postgres, 16KB in MySQL/InnoDB, configurable in others. The engine never reads "a row"; it reads the page the row lives on, and everything else — heaps, B-trees, the buffer pool, the WAL — is built out of pages.
Fixed size is the design decision that makes the rest tractable. Aligned, uniform pages give predictable buffer-pool slotting (every frame holds exactly one page), simple free-space accounting, and I/O that lines up with hardware block sizes. Variable-length units would make caching and free-space maps far harder.

The two dominant on-disk index families.

B-tree — read-optimized. A shallow, balanced tree of pages that keeps data sorted and supports point lookups and range scans in O(log n) page fetches. Updates happen in place. This is the default in Postgres, MySQL/InnoDB, SQL Server, Oracle, and SQLite.
LSM tree — write-optimized. Buffers writes in an in-memory sorted structure, then flushes them to immutable sorted files on disk, merging those files in the background. Writes never seek; reads may touch several files. This is the engine behind Cassandra, ScyllaDB, RocksDB, LevelDB, and HBase.

What interviewers actually probe.

Can you describe the page as the unit of I/O, and name a real page size (8KB Postgres, 16KB InnoDB)? — required baseline.
Can you explain why B-trees favour reads and LSM trees favour writes in terms of random versus sequential I/O and write amplification? — the core senior signal.
Do you know the durability path — that a committed change is logged to the WAL and fsync'd before the data page is necessarily written back? — senior signal.
Can you map a real system to its engine ("Postgres = B-tree heap, Cassandra = LSM") and defend the fit against a workload? — decision-maker signal.

Worked example — counting page fetches, not rows

Detailed explanation. The single most useful mental reframe for storage internals is to stop counting rows and start counting page fetches, because page fetches are what cost time — a random page read off an SSD is ~100 microseconds and off a spinning disk is ~10 milliseconds, while comparing two integers in RAM is nanoseconds. A query that "returns one row" can cost anywhere from one page fetch to millions depending on the access path.

Sequential scan. Reads every page of the table in order. Cost = number of pages in the heap, regardless of how many rows match.
Index scan. Walks the B-tree from root to leaf (a few pages), then fetches the heap page each matching row lives on. Cost = tree height + number of matching heap pages.
The crossover. For a highly selective predicate (few matching rows), the index scan wins massively. For a predicate matching most of the table, the sequential scan wins because random heap fetches cost more than one big sequential read.

Question. A users table has 10 million rows packed ~100 rows per 8KB page (so ~100,000 pages). Estimate the page fetches for SELECT * FROM users WHERE id = 42 under (a) no index and (b) a B-tree index on id.

Input.

Fact	Value
Rows	10,000,000
Rows per page	~100
Heap pages	~100,000
B-tree height for 10M keys	3–4 levels
Matching rows	1

Code.

-- (a) no index: planner has no choice but a sequential scan
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM users WHERE id = 42;
-- Seq Scan on users  (cost=0.00..179000 rows=1)
--   Buffers: shared read=100000        <- ~100k page fetches

-- (b) with a B-tree index on id
CREATE INDEX idx_users_id ON users (id);
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM users WHERE id = 42;
-- Index Scan using idx_users_id on users  (cost=0.43..8.45 rows=1)
--   Buffers: shared read=4              <- 3 index pages + 1 heap page

Step-by-step explanation.

Without an index the planner can only sequentially scan the heap: it reads all ~100,000 pages, checking every row's id, and returns the one match. The engine touched 100,000 pages to return one row.
With a B-tree index, the engine reads the root page, follows a child pointer to an internal page, follows another pointer to a leaf page — 3 page fetches to locate the row's heap address (its ctid).
It then fetches the single heap page that row lives on — a 4th page fetch — and returns the row.
The ratio is 100,000 versus 4: a five-order-of-magnitude difference in physical work for the identical SQL statement. The only thing that changed is the on-disk structure the engine could use.
This is why "the index is what makes the query fast" is imprecise. The index is what lets the engine fetch a handful of pages instead of all of them. Page fetches are the currency.

Output.

Access path	Page fetches	Relative cost
Sequential scan (no index)	~100,000	1× (baseline)
B-tree index scan	~4	~25,000× cheaper

Rule of thumb. When you reason about query cost, translate the plan into page fetches, not rows returned. Every storage structure in this guide exists to reduce that number for some workload — and each trades a cost elsewhere to do it.

Worked example — mapping real systems to their storage engine

Detailed explanation. Interviewers frequently hand you a system and ask "what storage engine does that use, and why does it fit?" Having a mental map of the major databases and their engine keyed to workload is the fastest way to sound like someone who has operated these systems rather than only read about them.

OLTP relational (Postgres, MySQL, SQL Server, Oracle). B-tree over a heap (or clustered B-tree). Read-and-point-update heavy; needs sorted range scans and secondary indexes.
Wide-column / high-ingest (Cassandra, ScyllaDB, HBase). LSM tree. Write-heavy, append-mostly, time-series and event data where ingest rate dominates.
Embedded key-value (RocksDB, LevelDB). LSM tree. Used inside Kafka Streams state stores, CockroachDB, TiDB, and MyRocks precisely because they are write-optimized.

Question. For each workload — an e-commerce orders table, a metrics/time-series ingest pipeline, and a Kafka Streams state store — name the storage-engine family and justify it in one line.

Input.

Workload	Read/write mix	Latency need
E-commerce orders	read-heavy, point updates	low read latency
Metrics ingest	write-heavy, append-mostly	high write throughput
Kafka Streams state	mixed, embedded	fast local writes

Code.

Workload → engine mapping (say this out loud in an interview)
============================================================
E-commerce orders    -> B-tree (Postgres/InnoDB)
   "Reads dominate, point lookups by id and range scans by date;
    in-place updates are cheap; a shallow B-tree gives O(log n) reads."

Metrics / time-series -> LSM tree (Cassandra / ScyllaDB)
   "Ingest rate is the bottleneck. Buffer writes in a memtable,
    flush sequential SSTables, never seek on write. Pay the read
    amplification back with compaction and bloom filters."

Kafka Streams state  -> LSM tree (RocksDB embedded)
   "Local state updates are frequent and write-heavy; RocksDB's
    LSM absorbs them in memory and flushes sequentially to local SSD."

Step-by-step explanation.

The orders table is read-heavy: dashboards, order-status lookups, customer history. Reads must be cheap and support range scans by date — a B-tree keeps keys sorted so both point lookups and ranges are O(log n).
In-place updates (an order changing status) are cheap on a B-tree: find the leaf, rewrite the tuple. The write cost is acceptable because writes are a minority of the traffic.
Metrics ingest inverts the ratio: millions of writes per second, reads mostly recent-window range scans. An LSM tree turns every write into an in-memory append plus a sequential log write — no random seek — which is why it sustains far higher write throughput.
The read cost of LSM (checking several SSTables) is paid back with bloom filters and compaction, an acceptable trade when writes dominate.
RocksDB inside Kafka Streams is the embedded case: a per-partition local key-value store hammered by state updates. Its LSM design absorbs the write rate on local SSD, which a B-tree would struggle with under the same write pressure.

Output.

Workload	Engine family	Example systems
E-commerce orders	B-tree	Postgres, MySQL/InnoDB
Metrics / time-series	LSM tree	Cassandra, ScyllaDB
Kafka Streams state	LSM tree	RocksDB

Rule of thumb. Match the engine to the read/write ratio: read-heavy with point lookups and ranges wants a B-tree; write-heavy, high-ingest wants an LSM tree. If you can name the system and the engine and the reason in one breath, you have answered the question at senior level.

Data engineering interview question on storage-engine selection

A systems interviewer often opens with: "You're designing the storage for two services — an orders service that does mostly point reads and status updates, and a telemetry service ingesting a million sensor events per second. Walk me through which storage engine each should use, what the on-disk structure looks like, and the specific cost each trade-off buys you."

Solution Using a B-tree for reads and an LSM tree for ingest, justified by page-level cost

Decision framework — pick the engine from the workload's cost curve
==================================================================

ORDERS SERVICE (read-heavy, point updates)  -> B-tree heap (Postgres)
  Reads:  point lookup  = O(log n) page fetches (root->internal->leaf)
          range scan     = O(log n) to first leaf, then walk leaf chain
  Writes: in-place update = find leaf, rewrite tuple (1 page dirtied)
          worst case      = page split when a leaf overflows
  Why:    reads dominate; a shallow tree keeps every read to ~4 pages.

TELEMETRY SERVICE (write-heavy, high ingest) -> LSM tree (Cassandra)
  Writes: append to memtable (RAM) + append to WAL (sequential)
          = O(1), zero random seeks
  Reads:  check memtable, then SSTables newest->oldest, gated by
          bloom filters = O(number of levels) in the worst case
  Compaction merges SSTables in the background to cap read + space amp.
  Why:    ingest rate is the bottleneck; sequential writes win.

Step-by-step trace.

Workload	Operation	B-tree cost	LSM cost
Orders	point read	~4 page fetches	memtable + N SSTables (worse)
Orders	status update	1 leaf rewrite in place	append + later compaction
Telemetry	ingest event	random-ish leaf write + splits	append to memtable (O(1))
Telemetry	recent-window read	good if indexed by time	good; recent data in top level
Both	crash safety	WAL logs change first	WAL (commit log) logs first

For the orders service the B-tree's read profile is decisive: every point lookup and range scan stays within a handful of pages, and updates are a cheap in-place rewrite because they are the minority of traffic. For the telemetry service the LSM tree's write profile is decisive: a million events per second become a million in-memory appends plus one sequential log stream, and the read cost is deferred to background compaction that the write path never waits on.

Output:

Metric	Orders (B-tree)	Telemetry (LSM)
Dominant operation	point read / range scan	high-rate ingest
Write path	in-place, may split	append to memtable + WAL
Read path	O(log n) page fetches	memtable + SSTables (bloom-gated)
Amplification paid	write amp on heavy insert	read + space amp, offset by compaction
Chosen engine	B-tree (Postgres)	LSM (Cassandra)

Why this works — concept by concept:

Page fetches as currency — both engines are judged by how many pages an operation touches. The B-tree minimises read fetches; the LSM minimises write fetches by never seeking. Naming the metric is what makes the trade-off precise instead of hand-wavy.
In-place vs append — a B-tree mutates the data page where the row lives (random write), while an LSM only ever appends (sequential write) and reconciles later. Random writes are the expensive kind on both SSD and disk, which is the root reason LSM wins on write throughput.
Deferred vs immediate cost — the LSM pays the read/space cost later, in background compaction, off the critical path; the B-tree pays a possible page-split cost now, on the write. Matching "which cost can I defer?" to "which operation dominates?" is the selection heuristic.
Cost — B-tree: reads O(log n) page fetches, writes O(log n) with occasional O(page) splits, space overhead from partially-full pages. LSM: writes O(1) amortised, reads O(levels) gated by bloom filters, plus compaction I/O in the background. Pick the engine whose cheap operation is your dominant operation.

Systems
Topic — database
Database internals and storage-engine problems

Practice →

DS Topic — data-structures Data-structure problems behind indexes and trees

Practice →

2. Pages & the heap — the fundamental unit of storage

The fixed-size page is the atom of storage, and the heap is the unordered pile of pages your rows land in

The mental model in one line: a database stores rows inside fixed-size pages — 8KB in Postgres — and the simplest table is a heap file, an unordered collection of those pages where a row is addressed by (page_id, slot); the page's internal layout (a header, a slot array of line pointers growing down, and tuples growing up toward a shrinking pool of free space) is the physical structure every higher-level index ultimately points into. Once you can draw a single page from memory, heaps, B-trees, and even LSM SSTables stop being abstract — they are all just arrangements of this one unit.

Why a fixed-size page at all.

Aligned I/O. An 8KB page lines up with filesystem blocks and SSD pages, so reading or writing one is a single aligned operation the OS and hardware move as a unit — no straddling of block boundaries.
Predictable buffer-pool slotting. Because every page is the same size, the buffer pool is an array of identical frames; any page can go in any frame, eviction is uniform, and there is no fragmentation of the cache itself.
Simple free-space accounting. A free-space map can record "page 812 has 2KB free" in a compact form precisely because pages are uniform. Variable-size storage units would make this bookkeeping far harder.
The trade. Fixed pages waste a little space (a row rarely fills a page exactly) and force oversized values into overflow storage, but the operational simplicity is worth it.

Anatomy of a page (the Postgres model).

Page header. A small fixed block at the very start (24 bytes in Postgres) holding a checksum, free-space pointers (pd_lower, pd_upper), and the WAL position of the last change to the page (pd_lsn) — the link to durability we return to in section 5.
Slot array (line pointers). Immediately after the header, an array of small pointers grows downward. Each slot points to a tuple's offset and length within the page. The slot number is stable even when the tuple moves inside the page, which is why an index can point at (page, slot) and survive intra-page reorganisation.
Free space. The empty middle band. The slot array grows down into it from the top; the tuples grow up into it from the bottom. When they meet, the page is full.
Tuples (the rows). The actual row data, added from the end of the page growing upward. Each tuple has its own small header (visibility info — transaction ids for MVCC — plus a null bitmap) followed by the column values.

Heap files — the default table storage.

Unordered pages of rows. A heap is just a sequence of pages with no ordering guarantee between them. New rows go into any page with free space (guided by the free-space map); there is no relationship between a row's key and which page it lands on.
Row identity = (page_id, slot). Postgres exposes this as the ctid system column — e.g. (0,1) means page 0, slot 1. Every index entry ultimately stores a key plus this physical address so it can jump from a key to the heap tuple.
Reads without an index are sequential scans. With no ordering and no index, finding a row means scanning every page — O(pages). This is exactly why indexes exist.
Heap vs index-organized. Postgres always stores the table as a heap and keeps indexes separate. MySQL/InnoDB instead stores the table inside the primary-key B-tree (a clustered / index-organized table), so there is no separate heap — the leaf pages of the PK index are the rows.

Failure modes and edge cases.

Oversized rows (TOAST / overflow). A value larger than roughly a quarter of a page can't fit inline. Postgres transparently compresses it and/or stores it out-of-line in a TOAST table, leaving a pointer in the main tuple; InnoDB uses overflow pages similarly.
Bloat. Under MVCC, an UPDATE writes a new tuple version and marks the old one dead; a DELETE marks the tuple dead. Dead tuples occupy space until VACUUM reclaims it, so a heavily-updated heap can bloat far beyond its live-row size.
Page-level fragmentation. Free space scattered across many partly-full pages hurts scan efficiency; VACUUM and occasional VACUUM FULL / pg_repack compact it.

Worked example — where a single row physically lives (`ctid`)

Detailed explanation. The fastest way to make pages concrete is to look at a real row's physical address. Postgres exposes the ctid of every row — the (page, slot) pair — as a hidden system column, so you can watch a row move between pages as it is updated. This is the exact address every index entry stores.

ctid is (block_number, item_number) — the page id and the slot in that page's slot array.
An UPDATE changes the ctid because MVCC writes a new tuple version, often on a different page, and leaves the old version behind until VACUUM cleans it.
pageinspect lets you crack a page open and read its header and slot array directly.

Question. Show the physical location of a row before and after an update, and explain why the ctid changes.

Input.

Step	Action
1	Create a table, insert one row
2	Read its `ctid`
3	Update the row
4	Read its `ctid` again

Code.

CREATE TABLE accounts (id BIGINT PRIMARY KEY, balance BIGINT);
INSERT INTO accounts VALUES (1, 100);

-- Where does row id=1 physically live?
SELECT ctid, id, balance FROM accounts WHERE id = 1;
--  ctid  | id | balance
-- -------+----+---------
--  (0,1) |  1 |     100        <- page 0, slot 1

-- Update it; MVCC writes a NEW tuple version
UPDATE accounts SET balance = 250 WHERE id = 1;

SELECT ctid, id, balance FROM accounts WHERE id = 1;
--  ctid  | id | balance
-- -------+----+---------
--  (0,2) |  1 |     250        <- same page, NEW slot (old version at (0,1) is dead)

-- Crack the page open and count line pointers
CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT lp, lp_off, lp_len, t_ctid
FROM heap_page_items(get_raw_page('accounts', 0));
-- lp | lp_off | lp_len | t_ctid     <- two line pointers now: the dead
--  1 |   8152 |     40 | (0,2)      <- old version points forward to (0,2)
--  2 |   8112 |     40 | (0,2)      <- the live version

Step-by-step explanation.

The insert places the row on page 0, slot 1 — ctid = (0,1). The slot array now has one line pointer; the tuple sits at the high end of the page (offset 8152 in an 8KB page) growing downward from the tail.
The UPDATE does not overwrite the tuple in place. Postgres MVCC writes a new version of the row (balance 250) into a free slot — slot 2 — and marks the old version dead. The row's live ctid becomes (0,2).
heap_page_items shows two line pointers on the page: the old version's pointer now carries a t_ctid of (0,2) — a forward pointer (the "HOT chain") telling scanners where the current version lives.
The old version at slot 1 is dead space; it stays until VACUUM reclaims the line pointer and its bytes for reuse. This is the source of heap bloat under heavy updates.
Because indexes store the key plus ctid, an update that moves a row to a new page normally forces the index to be updated too — unless the update is a HOT (heap-only tuple) update that keeps the new version on the same page and lets the index entry stay valid.

Output.

Moment	`ctid`	Page state
After insert	(0,1)	1 live tuple
After update	(0,2)	1 live + 1 dead tuple
After VACUUM	(0,2)	1 live tuple, slot 1 reclaimed

Rule of thumb. A row's identity to the storage engine is its (page, slot) address, not its primary key — the primary key is just an index into that address. When you see ctid change on an update, you are watching MVCC create a new tuple version, which is the mechanism behind both Postgres's concurrency and its bloat.

Worked example — reading a page header and computing fill factor

Detailed explanation. Every page tracks its own free space in the header via two pointers: pd_lower (end of the slot array) and pd_upper (start of the tuple region). The gap between them is the free space. Understanding these lets you reason about how many rows fit per page and why fillfactor matters for update-heavy tables.

pd_lower grows down as slots are added; pd_upper grows up as tuples are added. Free bytes = pd_upper - pd_lower.
fillfactor tells Postgres to leave a percentage of each page empty on insert, reserving room for future HOT updates to stay on the same page.
Rows per page ≈ (page size − header) / (tuple size + slot pointer).

Question. Estimate rows per 8KB page for a 40-byte tuple, and explain how a fillfactor of 80 changes it and why you'd set it.

Input.

Parameter	Value
Page size	8192 bytes
Page header	24 bytes
Special space	0 (heap)
Tuple size (incl. header)	40 bytes
Line pointer	4 bytes
Per-row footprint	44 bytes

Code.

-- Usable space per page and rows-per-page estimate
-- usable = 8192 - 24 (header) = 8168 bytes
-- per row = 40 (tuple) + 4 (line pointer) = 44 bytes
-- rows/page at 100% fill = floor(8168 / 44) = 185 rows

-- Set fillfactor so updates can stay on-page (HOT updates)
ALTER TABLE accounts SET (fillfactor = 80);
-- Now inserts stop at ~80% full: floor(8168 * 0.80 / 44) = ~148 rows/page,
-- leaving ~1600 bytes/page free for in-page new tuple versions.

-- Inspect the actual header pointers of page 0
SELECT lower, upper, special, pagesize
FROM page_header(get_raw_page('accounts', 0));
--  lower | upper | special | pagesize
-- -------+-------+---------+----------
--     28 |  8152 |    8192 |     8192     <- free = upper - lower = 8124 bytes

Step-by-step explanation.

Usable space is the page minus its 24-byte header (a heap page has no special-space region), so 8168 bytes are available for slots plus tuples.
Each stored row costs its 40-byte tuple plus a 4-byte line pointer in the slot array — 44 bytes total. Dividing 8168 by 44 gives ~185 rows on a completely full page.
Setting fillfactor = 80 tells Postgres to stop inserting new rows once a page is ~80% full, capping it near 148 rows and reserving ~1600 bytes.
That reserved space lets an UPDATE write the new tuple version on the same page (a HOT update), which avoids touching the indexes and avoids scattering the row across pages — a big win for update-heavy tables.
The page_header output confirms the live pointers: lower = 28 (header plus one 4-byte slot) and upper = 8152 (first tuple), so free space is 8152 − 28 = 8124 bytes on this nearly-empty page.

Output.

Setting	Rows/page	Free bytes/page	Best for
fillfactor 100	~185	~0	append-only / read-only tables
fillfactor 80	~148	~1600	update-heavy tables (enables HOT)

Rule of thumb. Pack read-only tables tight (fillfactor 100) to minimise pages scanned; leave slack on update-heavy tables (fillfactor 70–90) so updates stay on-page as HOT updates and don't bloat the indexes. The header's lower/upper pointers are the ground truth for how full a page really is.

SQL interview question on heap storage and row location

A senior interviewer might ask: "A colleague says SELECT * FROM orders WHERE id = 900000 on a 50-million-row Postgres heap 'should be instant because it's just one row.' It takes 4 seconds. Using what you know about heap files and pages, explain why, prove it, and fix it — and explain what physically changes after your fix."

Solution Using a B-tree index to replace a full heap scan, proven with page counts

-- 1. Reproduce: no index on id means a sequential scan of the whole heap
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE id = 900000;
-- Seq Scan on orders (actual time=0.9..3980 rows=1)
--   Filter: (id = 900000)
--   Rows Removed by Filter: 49999999
--   Buffers: shared read=500000        <- half a million 8KB pages read

-- 2. Confirm how big the heap is (pages, not rows)
SELECT relpages, reltuples
FROM   pg_class
WHERE  relname = 'orders';
-- relpages | reltuples
-- ---------+-----------
--   500000 |  50000000     <- 500k pages, 100 rows/page

-- 3. Fix: build a B-tree index on the lookup key
CREATE INDEX CONCURRENTLY idx_orders_id ON orders (id);

-- 4. Re-check the plan: now an index scan, a handful of pages
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders WHERE id = 900000;
-- Index Scan using idx_orders_id on orders (actual time=0.05..0.06 rows=1)
--   Index Cond: (id = 900000)
--   Buffers: shared hit=4              <- 3 index pages + 1 heap page

Step-by-step trace.

Step	State	Page fetches	Time
1. Seq scan	no index; scan whole heap	~500,000	~4 s
2. Diagnose	`pg_class` confirms 500k pages	—	—
3. Build index	`CREATE INDEX CONCURRENTLY`	one-time build	seconds–minutes
4. Index scan	root→internal→leaf→heap	~4	~0.06 ms

The colleague's intuition — "one row, so it's cheap" — confuses the result size with the work done. Without an index the engine has no way to know which page holds id = 900000, so it must read all 500,000 pages and filter 49,999,999 non-matching rows. The B-tree gives the engine a sorted map from key to (page, slot), collapsing the search to the tree height plus one heap page.

Output:

Metric	Before (heap scan)	After (index scan)
Access path	Seq Scan	Index Scan
Pages read	~500,000	~4
Rows filtered	49,999,999	0
Latency	~4 s	~0.06 ms
What changed on disk	nothing (same heap)	new B-tree index file added

Why this works — concept by concept:

Heap = unordered pages — a heap file has no ordering between key and page, so the only key-agnostic access path is a full sequential scan. The 4-second cost is 500,000 page fetches, not "one row."
Index maps key → ctid — the B-tree stores each key alongside the row's (page, slot) address, so the engine navigates directly to the one heap page instead of reading them all. The index doesn't make the row smaller; it makes the search touch a handful of pages.
CONCURRENTLY avoids a write lock — CREATE INDEX CONCURRENTLY builds the index without blocking writes to the table, at the cost of a slower two-pass build — the production-safe way to add the index to a live table.
The heap is unchanged — building the index adds a separate structure; the rows still live in the same heap pages. The fix changes the access path, not the table storage. (An InnoDB clustered table would differ — there the PK is the row storage.)
Cost — the index adds ~O(rows) build time once, plus storage for the tree and a small write cost to maintain it on every insert/update. In return, point lookups drop from O(pages) to O(log n) page fetches — the trade almost always worth making for a selective lookup key.

Systems
Topic — database
Heap files, pages, and row-storage problems

Practice →

DS Topic — data-structures Data-structure problems on layout and addressing

Practice →

3. B-Tree storage — the read-optimized default

A B-tree is a shallow, balanced tree of pages that keeps keys sorted so reads touch only a handful of pages

The invariant in one line: a B-tree (technically a B+tree) stores keys in sorted order across a balanced tree whose every node is exactly one page — a root, a few levels of internal nodes holding keys and child pointers, and leaf nodes holding keys plus row pointers (or the rows themselves) — and because each node's high fan-out packs hundreds of keys per page, the tree stays only 3–4 levels deep even for billions of rows, so any point lookup or range scan costs O(log n) page fetches. This shallowness is the entire reason B-trees dominate read-heavy relational storage.

The structure — every node is a page.

Root page. The single entry point, held near-permanently in the buffer pool. It holds separator keys and pointers to the next level. For a small table the root can also be a leaf.
Internal (branch) pages. Hold separator keys and child pointers only — no row data. Their job is pure navigation: "keys < 500 go left, keys in [500,900) go middle, keys ≥ 900 go right."
Leaf pages. Hold the actual index entries — each a key plus a pointer to the heap tuple (Postgres) or the full row inline (a clustered index like InnoDB's PK). In a B+tree, all data lives at the leaf level; internal nodes are just a routing index.
The leaf chain. Leaves are linked left-to-right in key order (a doubly-linked list of pages). This is what makes range scans cheap — find the first leaf, then walk the chain sequentially.

Why the tree stays shallow — fan-out.

Fan-out = keys per page. An 8KB internal page holding, say, 8-byte keys plus pointers fits hundreds of children. With a fan-out of ~500, one level indexes 500 nodes, two levels 250,000, three levels 125 million, four levels 62 billion.
Height = log_fanout(n). That is why a table with billions of rows is still only 3–4 pages deep to any leaf. The tree height is the number of page fetches for a point lookup.
Balanced by construction. B-trees stay balanced through splits and merges, so every leaf is the same distance from the root. There is no degenerate-tree case as there is with an unbalanced binary tree.

Reads — the B-tree's home turf.

Point lookup. Root → internal → leaf → (heap). O(log n) page fetches; typically 3–4 index pages plus one heap page in Postgres.
Range scan. Descend to the first key in range, then walk the linked leaf chain in order, reading each leaf sequentially. Cost = tree height + number of leaves in range — excellent because leaves are ordered and adjacent.
Sorted output for free. Because leaves are in key order, an index scan can satisfy ORDER BY key without a separate sort.

Writes — where the B-tree pays.

In-place update. Change a non-indexed column: find the leaf/heap page, rewrite the tuple. One page dirtied. Cheap.
Insert and page splits. Inserting a key into a full leaf forces a page split: allocate a new page, move half the entries over, and insert a separator key into the parent — which can itself split, cascading up to the root. A split turns one write into several and is the B-tree's main write cost.
Random write I/O. Because keys route to wherever they sort, a stream of random-key inserts dirties scattered leaf pages all over the tree — random writes, the expensive kind. This is the write-amplification story that motivates LSM trees.
Clustered vs secondary. A clustered index (InnoDB PK) stores rows in the leaves, so the table is the tree; a secondary index stores key + a pointer back to the row. Secondary-index lookups may need a second hop to fetch the row.

Failure modes.

Write amplification under heavy inserts. Random-key insert storms cause frequent splits and scattered dirty pages, degrading write throughput — the workload where an LSM tree wins.
Index fragmentation / bloat. Repeated splits and MVCC dead entries leave leaves partly full; the tree occupies more pages than its live keys need, hurting scan and cache efficiency. REINDEX rebuilds it.
Right-edge contention. Monotonically increasing keys (a BIGSERIAL) always insert at the rightmost leaf, concentrating splits and lock contention there — a known hotspot for high-insert tables.

Worked example — tracing a point lookup root → leaf

Detailed explanation. The clearest way to internalise a B-tree is to trace one lookup by hand, counting page fetches at each level. Take a B-tree on id for a 100-million-row table with a fan-out that yields a height of 4, and find id = 7,350,000.

Each level is one page fetch. Root, then one internal, then one leaf — the height determines the count.
The leaf yields a ctid (Postgres) which then costs one more fetch into the heap.
Separator keys route the descent. At each node you binary-search the in-page keys to pick the child pointer.

Question. Trace the page fetches for SELECT * FROM events WHERE id = 7350000 on a height-4 B-tree over a heap.

Input.

Level	Node type	Holds	Action
0	root	separators + child ptrs	pick child for 7.35M
1	internal	separators + child ptrs	pick child
2	internal	separators + child ptrs	pick leaf
3	leaf	key + ctid	find key, read ctid
heap	data page	the row	fetch tuple

Code.

CREATE INDEX idx_events_id ON events (id);   -- B+tree, height ~4 for 100M rows

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM events WHERE id = 7350000;
-- Index Scan using idx_events_id on events
--   Index Cond: (id = 7350000)
--   Buffers: shared hit=5              <- 4 index pages + 1 heap page
--   actual time=0.031..0.032 rows=1

Step-by-step explanation.

Fetch 1 — root. Binary-search the root's separator keys. Say the root splits the key space at 50M; 7.35M < 50M, so follow the first child pointer.
Fetch 2 — internal level 1. This node covers [0, 50M) with separators every ~10M. 7.35M falls in the [0, 10M) child; follow that pointer.
Fetch 3 — internal level 2. Covers [0, 10M) with finer separators; 7.35M lands in a child covering ~[7.3M, 7.4M); follow to the leaf.
Fetch 4 — leaf. The leaf holds sorted keys ~[7.3M, 7.4M) each with a ctid. Binary-search finds id = 7350000 and reads its ctid, say (84213, 12).
Fetch 5 — heap. Fetch heap page 84213, read slot 12, return the row. Total: 4 index pages + 1 heap page = 5 fetches to find one row in 100 million — the payoff of O(log n) with a huge fan-out.

Output.

Fetch	Node	Result
1	root	route to [0, 50M)
2	internal	route to [0, 10M)
3	internal	route to leaf ~[7.3M, 7.4M)
4	leaf	ctid = (84213, 12)
5	heap	the row

Rule of thumb. A B-tree point lookup costs tree-height index fetches plus one heap fetch — almost always 4–6 total, no matter how large the table. If you ever see a point lookup reading thousands of pages, the planner chose a scan, not the index; check EXPLAIN.

Worked example — a range scan walking the leaf chain

Detailed explanation. Range scans are where the sorted leaf chain earns its keep. WHERE created_at BETWEEN a AND b descends once to the first qualifying leaf, then walks the linked leaves in order until it passes b — reading sequential, adjacent pages rather than random ones.

One descent, then a sequential walk. Cost = height (to reach the first leaf) + number of leaves spanning the range.
Ordered results. The scan emits rows already sorted by the index key, so ORDER BY created_at needs no extra sort step.
Contrast with a hash index. A hash index can do equality in O(1) but cannot do ranges — it has no ordering. Ranges are the reason B-trees are the default over hash indexes.

Question. Trace the work for SELECT * FROM events WHERE created_at BETWEEN '2026-09-01' AND '2026-09-02' ORDER BY created_at on a B-tree over created_at, where the range spans ~30 leaf pages.

Input.

Parameter	Value
Index	B-tree on `created_at`
Tree height	4
Leaves in range	~30
Rows in range	~6,000
Order requested	by `created_at` (matches index)

Code.

CREATE INDEX idx_events_created_at ON events (created_at);

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM events
WHERE  created_at BETWEEN '2026-09-01' AND '2026-09-02'
ORDER  BY created_at;
-- Index Scan using idx_events_created_at on events
--   Index Cond: (created_at >= '2026-09-01' AND created_at <= '2026-09-02')
--   Buffers: shared hit=34            <- ~4 to descend + ~30 leaf pages
--   (no Sort node: index already returns rows in created_at order)

Step-by-step explanation.

The engine descends the tree once — 4 page fetches — to locate the first leaf whose keys reach 2026-09-01. This is the same root→internal→leaf navigation as a point lookup.
From that leaf it reads entries in order, following each leaf's forward link to the next leaf in the chain. These leaves are adjacent in key order, so the reads are effectively sequential.
For each index entry in range it fetches the row (from the heap, or inline if clustered), emitting rows in ascending created_at order.
It stops the moment a key exceeds 2026-09-02, so it never reads leaves outside the range. Total index work ≈ 4 (descent) + 30 (leaf walk) = ~34 page fetches for 6,000 rows.
Because the leaf order is created_at order, the ORDER BY is satisfied for free — the plan has no Sort node. A hash index or a heap scan would have needed an explicit sort of all 6,000 rows.

Output.

Work item	Cost
Descend to first leaf	~4 page fetches
Walk leaf chain	~30 page fetches
Sort step	none (index is ordered)
Total index pages	~34

Rule of thumb. B-trees make range scans and ORDER BY on the index key nearly free because the leaf chain is stored in sorted order. When a query filters or sorts on a column, a B-tree on that column turns both operations into a single ordered walk — the reason it is the default index type.

Data engineering interview question on B-tree write amplification

A senior interviewer might ask: "Your ingestion table uses a random UUID primary key and inserts are slowing down as it grows, with rising I/O and index bloat. Explain in B-tree terms exactly why random-key inserts hurt, then redesign the key so the B-tree behaves — and show the difference in page-split and write behaviour."

Solution Using an ordered key to convert random splits into sequential appends

-- PROBLEM: random UUIDv4 PK scatters inserts across the whole B-tree
CREATE TABLE ingest_v4 (
    id   UUID PRIMARY KEY DEFAULT gen_random_uuid(),  -- random!
    body JSONB,
    ts   TIMESTAMPTZ NOT NULL DEFAULT now()
);
-- Each insert routes to a random leaf -> dirties scattered pages,
-- triggers frequent splits, defeats buffer-pool locality.

-- FIX A: time-ordered key (UUIDv7 / ULID) so inserts append at the right edge
CREATE TABLE ingest_v7 (
    id   UUID PRIMARY KEY DEFAULT uuidv7(),   -- time-ordered (PG 18) 
    body JSONB,
    ts   TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- FIX B: plain BIGSERIAL when you don't need a UUID at all
CREATE TABLE ingest_seq (
    id   BIGSERIAL PRIMARY KEY,               -- monotonic; appends
    body JSONB,
    ts   TIMESTAMPTZ NOT NULL DEFAULT now()
);

-- Measure index bloat / fragmentation after a load
SELECT indexrelname,
       pg_size_pretty(pg_relation_size(indexrelid)) AS index_size
FROM   pg_stat_user_indexes
WHERE  relname LIKE 'ingest_%';

Step-by-step trace.

Aspect	Random UUIDv4 PK	Ordered key (UUIDv7 / BIGSERIAL)
Insert target leaf	random across the tree	always the right-most leaf
Dirty pages per burst	many, scattered	few, adjacent
Page splits	frequent, tree-wide	rare, localised at the edge
Buffer-pool locality	poor (cold random leaves)	excellent (hot right edge)
Index size after load	bloated (partly-full leaves)	compact (leaves fill densely)
Write amplification	high	low

With a random key, every insert picks a uniformly random point in the key space, so a burst of N inserts touches N different leaf pages scattered across the tree — each possibly cold (a buffer-pool miss and a random write), and each pushing its leaf toward a split. With a time-ordered key, every insert sorts to the current maximum, so it lands on the same right-most leaf that is already hot in the buffer pool; that leaf fills densely and splits only when full, and the split is a clean edge split rather than a mid-tree cascade.

Output:

Metric	Random UUIDv4	Ordered key
Dominant write pattern	random	sequential (append)
Split frequency	high	low
Leaf fill	partial (bloat)	dense
Insert throughput	degrades as tree grows	stable
When still to prefer random	need unguessable, non-sequential ids	—

Why this works — concept by concept:

Keys route inserts to leaves — a B-tree places each row at the leaf where its key sorts. A random key therefore distributes inserts uniformly, guaranteeing scattered leaf writes; an ordered key funnels them to one place.
Right-edge appends stay hot — a monotonic key always inserts at the maximum, so the target leaf and its parent are already cached and dirty. Sequential writes to a hot page are dramatically cheaper than random writes to cold pages.
Splits localise — with ordered keys the only leaf that splits is the right edge, and it splits cleanly (old page stays full, new page takes the next run). Random keys split leaves all over the tree, each potentially cascading a separator up to the parent.
The UUID trade — UUIDv4 is chosen for unguessability and client-side generation, but its randomness is exactly what hurts the B-tree. UUIDv7/ULID keep global uniqueness and time-ordering, recovering the append behaviour; use them when you need UUID semantics without the write penalty.
Cost — random inserts trend toward O(log n) page fetches plus a random-write miss and frequent splits per insert; ordered inserts amortise to near O(1) amortised writes on a hot leaf. This is precisely the write-amplification gap that LSM trees close for genuinely write-dominated workloads.

Index
Topic — indexing
B-tree indexing and lookup-cost problems

Practice →

DS Topic — data-structures Balanced-tree and search-structure problems

Practice →

4. LSM Trees — memtable, SSTables, compaction: the write-optimized alternative

An LSM tree turns every write into an in-memory append plus a sequential log, deferring the sorting and merging to background compaction

The mental model in one line: a log-structured merge tree absorbs writes into an in-memory sorted structure (the memtable) plus a sequential write-ahead log, flushes the full memtable to an immutable sorted file on disk (an sstable) with no random seeks, serves reads by checking the memtable then the SSTables newest-to-oldest (using bloom filters to skip files that can't hold the key), and periodically merges SSTables in the background (compaction) to reclaim space and cap read cost — trading higher read and space amplification for dramatically higher write throughput. Where a B-tree writes in place and reads cheaply, an LSM writes sequentially and reads with more work — the mirror-image trade.

The write path — append everywhere.

Memtable. An in-memory sorted structure (usually a skip list or balanced tree) that holds recent writes in key order. A write is just an insert into this structure — O(log n) in RAM, no disk seek.
WAL / commit log. Before (or as) the write hits the memtable, it is appended to an on-disk log so an in-memory memtable can survive a crash. This append is sequential — the cheap kind of write.
Flush. When the memtable reaches a size threshold it becomes immutable and is written out sequentially as a new SSTable; a fresh memtable takes over. The flush is one big sequential write, not scattered random writes.
No in-place mutation. Updates and deletes are new entries, not overwrites: an update writes a newer key/value, and a delete writes a tombstone — a marker that the key is gone. Older versions linger in older SSTables until compaction removes them.

SSTables — immutable sorted files.

Sorted string tables. Each SSTable holds key/value pairs sorted by key, written once and never modified. Immutability is what makes them safe to read concurrently and cheap to write (pure sequential I/O).
Sparse index + block layout. An SSTable carries a small in-memory sparse index (every Nth key → file offset) so a read can seek near the key, plus a per-file bloom filter to answer "is this key possibly here?" without touching the file.
Levels. SSTables are organised into levels (L0, L1, L2, …). L0 holds freshly-flushed files (possibly overlapping key ranges); deeper levels hold larger, non-overlapping files — the layout compaction maintains.

The read path — newest wins.

Check the memtable first — the freshest data lives there.
Then SSTables newest-to-oldest — because a key may have several versions across files, the reader takes the first (newest) it finds and stops. Deletes surface as tombstones and mean "not present."
Bloom filters gate every file — before reading an SSTable, the reader consults its bloom filter; if it says "definitely not here," the file is skipped entirely. This is what keeps reads from scaling linearly with the number of SSTables.

Compaction — paying the read/space cost back.

What it does. Background threads merge multiple SSTables into fewer, larger ones, discarding superseded versions and dropping tombstones once no older data can reference the key. This bounds the number of files a read must consult and reclaims space.
The three amplifications. Every LSM tunes a trade among write amplification (bytes written to disk per byte of user data, inflated by re-writing during compaction), read amplification (files consulted per read), and space amplification (disk used per byte of live data, inflated by stale versions).
Leveled compaction (RocksDB default). Keeps non-overlapping files per level; low read and space amplification, higher write amplification — good for read-mix and space-tight workloads.
Size-tiered compaction (Cassandra default). Merges similarly-sized files together; low write amplification, higher space and read amplification — good for pure write-heavy ingest.

Where LSM wins and what it costs.

Wins on write-heavy, high-ingest, append-mostly workloads — time-series, event logs, metrics, message queues, Kafka Streams state. Sequential writes sustain throughput a B-tree's random writes can't.
Costs read amplification — a point read may check the memtable plus several SSTables; bloom filters and compaction mitigate it but never eliminate it. Range scans must merge across all levels.
Costs space and background I/O — stale versions and tombstones occupy space until compacted, and compaction itself consumes disk bandwidth and CPU that must be provisioned for.

Worked example — a key's life from write to compaction

Detailed explanation. The clearest way to understand an LSM is to follow one key through a write, an update, a flush, a delete, and a compaction — watching versions accumulate and then collapse. Take key user:42 in a RocksDB-style store.

Writes and deletes both append. Nothing is ever overwritten in place; every mutation is a new entry stamped with a sequence number.
Newest version wins on read until compaction physically removes the older ones.
A delete is a tombstone, not an erasure — it shadows older versions until compaction can safely drop them all.

Question. Trace the state of key user:42 across: set to A, flush, set to B, delete, then a compaction that merges the relevant SSTables.

Input.

Event	Operation	Lands in
t1	PUT user:42 = A	memtable
t2	flush	SSTable-1
t3	PUT user:42 = B	memtable → SSTable-2
t4	DELETE user:42	memtable → SSTable-3 (tombstone)
t5	compaction	merges SSTable-1..3

Code.

LSM state timeline for key "user:42"
====================================
t1  PUT user:42=A        memtable: {user:42=A(seq1)}
t2  flush                SSTable-1: [user:42=A(seq1)]        memtable: {}
t3  PUT user:42=B        memtable: {user:42=B(seq2)} -> flush -> SSTable-2: [user:42=B(seq2)]
t4  DELETE user:42       memtable: {user:42=TOMB(seq3)} -> flush -> SSTable-3: [user:42=TOMB(seq3)]

Read of user:42 BEFORE compaction:
  check memtable        -> miss
  check SSTable-3 (new) -> TOMBSTONE(seq3)  => key is DELETED, stop.
  (SSTable-2=B and SSTable-1=A are never consulted — newest wins)

t5  compaction merges SSTable-1 + SSTable-2 + SSTable-3:
  keep only newest per key = TOMB(seq3); no older data can reference it
  => tombstone dropped entirely; user:42 physically gone.
  Result SSTable-4: []   (space reclaimed)

Step-by-step explanation.

At t1 the write user:42 = A is an insert into the in-memory memtable, stamped with sequence number 1, plus an append to the WAL for durability. No disk seek.
At t2 the memtable flushes to SSTable-1 as a single sequential write; the memtable is emptied. user:42 = A now lives immutably on disk.
At t3 the update user:42 = B does not modify SSTable-1 — it writes a new version (seq 2) into the memtable, which later flushes to SSTable-2. Two versions of the key now exist across two files.
At t4 the delete writes a tombstone (seq 3) — a marker, not an erasure — which flushes to SSTable-3. A read now finds the tombstone first (newest file), returns "not found," and never even reads the B or A versions.
At t5 compaction merges the three SSTables, keeping only the newest entry per key. Since the newest is a tombstone and no older data outside these files can reference the key, the tombstone itself is dropped — the key is physically gone and its space reclaimed. Before compaction the key occupied three files; after, zero.

Output.

Moment	Versions on disk	Read result
After t2	A (SSTable-1)	A
After t3	A, B (2 files)	B (newest)
After t4	A, B, TOMB (3 files)	not found
After t5 (compaction)	none	not found; space reclaimed

Rule of thumb. In an LSM every write, update, and delete is an append; correctness comes from "newest sequence number wins," and space is reclaimed only by compaction. If deletes seem not to free space, it's because the tombstones haven't been compacted yet — a classic LSM operational surprise.

Worked example — bloom filters keep reads from scaling with SSTable count

Detailed explanation. The danger of an LSM read is that a key might live in any of many SSTables, so a naive reader would check them all — read amplification proportional to file count. Bloom filters break that: each SSTable carries a compact probabilistic filter that answers "definitely not present" or "possibly present," so the reader skips the vast majority of files for any given key.

A bloom filter never yields a false negative — if it says "not here," the key is truly absent from that file, so the read can safely skip it.
It may yield a false positive — "possibly here" occasionally sends the reader to a file that doesn't have the key; the false-positive rate is tuned by bits-per-key.
The effect — for a point lookup, the reader typically touches only the one SSTable that actually holds the key (plus rare false-positive probes), not all of them.

Question. A key user:42 lives in exactly one of 10 SSTables. Compute the expected file reads without bloom filters and with a bloom filter at a 1% false-positive rate.

Input.

Parameter	Value
SSTables to search	10
SSTables actually holding the key	1
Bloom false-positive rate	1% (0.01)
Bloom false-negative rate	0 (guaranteed)

Code.

Expected SSTable data-block reads for one point lookup
======================================================
No bloom filter:
  must probe every file until found (worst case all 10)
  expected reads ~ up to 10 file probes

With bloom filter (p = 0.01 false positive):
  true positive : 1 file (the one that has the key)  -> always read
  false positives: 9 other files * 0.01 = 0.09 files -> occasionally read
  expected reads ~ 1 + 0.09 = ~1.09 file probes

Tuning:
  bits/key = 10 -> ~1% FP     (RocksDB default ballpark)
  bits/key = 15 -> ~0.1% FP   (more RAM, fewer stray probes)

Step-by-step explanation.

Without bloom filters the reader has no way to know which SSTable holds user:42, so it must consult files newest-to-oldest until it finds the key — up to all 10 in the worst case, and on a missing key it would read all 10 every time.
With a bloom filter per SSTable, the reader first asks each filter "could user:42 be here?" These checks are in-memory and cheap.
The one SSTable that truly holds the key always answers "possibly here" (no false negatives), so it is read — 1 guaranteed file access.
Each of the 9 other filters answers "definitely not here" 99% of the time and "possibly here" 1% of the time, so on average 9 × 0.01 = 0.09 of them get read unnecessarily.
Expected file reads drop from up to 10 to about 1.09 — and crucially, a lookup for a non-existent key reads ~0.1 files instead of all 10, which is why bloom filters are the single most important LSM read optimisation.

Output.

Strategy	Expected file reads (key present)	Reads for missing key
No bloom filter	up to 10	10 (all files)
Bloom filter @ 1% FP	~1.09	~0.1

Rule of thumb. Bloom filters are what make LSM reads viable — they convert "check every SSTable" into "check the one that has it, plus a small false-positive tax." Size them by bits-per-key: more bits means fewer stray reads at the cost of RAM. Never reason about LSM read cost without them.

Systems interview question on LSM read amplification

A senior interviewer might ask: "Your Cassandra table has great write throughput but read latency has crept up and disk usage is double the live-data size. Explain in LSM terms what is happening, which amplification is biting, and how compaction strategy and bloom-filter tuning fix it — with the trade-offs each choice makes."

Solution Using compaction-strategy and bloom-filter tuning to trade the three amplifications

DIAGNOSIS — three amplifications, which one is biting?
=====================================================
Symptom: reads slow + disk 2x live data
  -> read amplification (too many SSTables per read) AND
     space amplification (stale versions not compacted)

CAUSE with size-tiered compaction (STCS, Cassandra default):
  - many similarly-sized SSTables accumulate before a merge
  - a point read may check many files; bloom FP probes add up
  - old versions/tombstones linger -> disk = ~2x live data

FIX A — switch to leveled compaction (LCS) for read-heavy tables
  ALTER TABLE events
    WITH compaction = {'class':'LeveledCompactionStrategy'};
  effect: non-overlapping files per level -> a read touches
          ~1 file per level; space amp ~1.1x
  cost:   higher WRITE amplification (more re-writes on merge)

FIX B — raise bloom-filter accuracy to cut stray file reads
  ALTER TABLE events WITH bloom_filter_fp_chance = 0.001;  -- from 0.01
  effect: ~10x fewer false-positive SSTable probes on reads
  cost:   more heap RAM for the larger filters

FIX C — tombstone/GC settings so deletes actually free space
  ALTER TABLE events WITH gc_grace_seconds = 3600;  -- from default 864000
  effect: tombstones become droppable sooner -> space reclaimed
  cost:   shorter window for hinted-handoff/repair to propagate deletes

Step-by-step trace.

Lever	Before	After	Which amp it fixes
Compaction strategy	size-tiered (STCS)	leveled (LCS)	read + space amp down
Files per read	many (all tiers)	~1 per level	read amp down
Space vs live data	~2×	~1.1×	space amp down
Bloom FP chance	0.01	0.001	read amp down
Write amplification	low	higher	trade paid here
gc_grace_seconds	864000 (10 days)	3600 (1 hour)	space amp (tombstones) down

The workload was tuned for pure write throughput (size-tiered compaction, loose bloom filters, long tombstone grace), but the access pattern shifted toward reads. Under STCS, similarly-sized SSTables pile up between merges, so a read fans out across many files and old versions inflate disk usage. Switching to leveled compaction reorganises SSTables into non-overlapping levels so a read consults roughly one file per level, and tightening the bloom-filter false-positive rate cuts the stray probes; both reduce read amplification. Shortening gc_grace_seconds lets tombstones be dropped sooner, collapsing the 2× space blowup — at the cost of a shorter safety window for delete propagation across replicas.

Output:

Metric	Before (STCS, loose)	After (LCS, tight)
Files consulted per read	many	~1 per level
Read latency	elevated	low
Disk vs live data	~2×	~1.1×
Write amplification	low	higher (accepted)
Best-fit workload	pure ingest	read/write mix

Why this works — concept by concept:

The three amplifications are a budget — write, read, and space amplification trade against one another; you can't minimise all three. Every LSM tuning choice spends one to buy another, so diagnosis starts with "which one is biting?"
Leveled vs size-tiered compaction — LCS keeps non-overlapping files per level (few files per read, tight space) by re-writing data more often (higher write amp); STCS merges like-sized files lazily (low write amp) but tolerates more files and stale space. Match the strategy to the read/write ratio.
Bloom filters bound read fan-out — tightening bloom_filter_fp_chance reduces the number of SSTables a read probes needlessly; the cost is RAM for larger filters. It attacks read amplification directly without touching the compaction schedule.
Tombstones hold space hostage — deleted data isn't freed until tombstones are compacted, and gc_grace_seconds gates when tombstones may drop (it exists so deletes propagate to all replicas). Shortening it reclaims space faster but narrows the correctness window for distributed deletes.
Cost — LCS raises write amplification (more background I/O and CPU) in exchange for O(levels) read fan-out and ~1.1× space; tighter bloom filters cost RAM; shorter grace costs delete-safety margin. The net moves the engine from "write-optimal" toward "balanced" — the right call once reads matter.

Systems
Topic — database
LSM tree, memtable, and SSTable problems

Practice →

DE Topic — data-processing High-ingest data-processing and compaction problems

Practice →

5. WAL, buffer pool & durability — how a write actually lands

A committed write is durable because its change is logged and fsync'd before the data page is guaranteed on disk, while the buffer pool serves reads from RAM

The invariant in one line: when you COMMIT, the database does not necessarily write your data page to disk — it writes the change to the write-ahead log and fsyncs that log, so a crash the instant after commit can be recovered by replaying the WAL, while the actual data pages live in the buffer pool (a cache of pages in RAM) and are flushed lazily at a checkpoint; this "log first, flush later" contract is what lets a database be both durable and fast. Both B-tree and LSM engines follow it — the WAL is the universal durability primitive; they differ only in what the data path does after logging.

The buffer pool — pages cached in RAM.

What it is. A large region of shared memory holding recently-used pages. Every read and write goes through it: the engine asks for a page, the buffer pool serves it from RAM (a hit) or reads it from disk into a free frame (a miss/page fault).
Dirty pages. When a transaction modifies a page in the buffer pool, that page becomes dirty — its in-memory copy is newer than the disk copy. Dirty pages are not written to disk immediately; that would make every write a random disk I/O.
Eviction. When the pool is full and a new page is needed, a replacement policy (a clock/LRU variant) evicts a page; if it is dirty it must be flushed first. Hot pages (the B-tree root, frequently-read leaves) stay resident, which is why most reads never hit disk.
Why reads are fast. A working set that fits in the buffer pool means point lookups and hot range scans are served entirely from RAM — the disk structure only matters on a cache miss.

Write-ahead logging — log the change before the data page.

The rule (WAL protocol). Before a modified data page may be written to disk — and before a transaction is reported committed — the log record describing the change must already be on durable storage. Log first, data later.
Why it works. The WAL is a sequential append, so logging is cheap even when the data pages it describes are scattered. On a crash, the on-disk data pages may be stale, but the WAL holds every committed change since the last checkpoint, so recovery can redo them.
Commit = WAL durable. COMMIT returns only after the transaction's WAL records are fsync'd to disk. That single fsync is the durability boundary; the data pages can still be sitting dirty in the buffer pool.
LSM parallel. An LSM's commit log is the same idea: the memtable (in RAM) is the "dirty data," and the commit log is the WAL that lets a crash replay writes the memtable hadn't yet flushed to an SSTable.

Checkpoints — bounding recovery.

What they do. Periodically, a checkpoint flushes all dirty buffer-pool pages to the data files and records a checkpoint position in the WAL. After a checkpoint, everything before that WAL position is safely on disk.
Why they matter. Recovery only needs to replay WAL from the last checkpoint forward, so checkpoints bound the replay window (and thus crash-recovery time). More frequent checkpoints mean faster recovery but more constant flushing I/O.
WAL retention. WAL segments before the last checkpoint can be recycled (or archived for point-in-time recovery / replication). A slow checkpoint or a lagging replica can cause WAL to accumulate.

The durability/latency trade — senior signals.

fsync is the cost. Durability requires a real flush to stable storage on commit, and fsync latency (especially on spinning disks) is the floor on commit latency. synchronous_commit = off trades a small window of potential data loss for far higher throughput.
Group commit. Under load, many transactions' WAL records are fsync'd together in one flush, amortising the fsync cost across the group — a key throughput optimisation.
Torn-page protection. A crash mid-write can leave a page half-written (a torn page). Postgres's full_page_writes logs a full image of a page the first time it is modified after a checkpoint, so recovery can restore it intact; InnoDB uses a doublewrite buffer for the same purpose.

Worked example — an UPDATE traced end-to-end

Detailed explanation. The best way to cement the durability contract is to trace one UPDATE from statement to durable commit, noting exactly when each piece of I/O happens — and when it doesn't. The surprise for most engineers is that at commit time the data page is often still dirty in RAM.

The data page change happens in the buffer pool — in RAM, marked dirty.
The WAL record is what gets forced to disk on commit — not the data page.
The data page reaches disk later, at a checkpoint or via background writer.

Question. Trace UPDATE accounts SET balance = 250 WHERE id = 1; COMMIT; through the buffer pool, WAL, and disk, marking every I/O.

Input.

Component	Role
Buffer pool	holds the data page for row id=1
WAL buffer / file	receives the change record
Data file	the heap on disk
Checkpointer	flushes dirty pages later

Code.

UPDATE accounts SET balance=250 WHERE id=1;  COMMIT;
====================================================
1. Locate page: buffer pool HIT (page already cached) — no disk read
2. Modify tuple in the buffer-pool page -> page marked DIRTY (in RAM only)
3. Write a WAL record describing the change into the WAL buffer:
     LSN 0/1A2B: UPDATE accounts tid=(0,1) balance 100 -> 250
4. (first change to this page since checkpoint?) also log a FULL PAGE IMAGE
5. COMMIT:
     - append COMMIT record to WAL buffer
     - fsync WAL up to this LSN  <-- THE durability boundary (one disk write)
     - return success to the client
   *** the data page is STILL dirty in RAM; not yet on disk ***
6. Later, at a CHECKPOINT (or by the background writer):
     - flush the dirty data page to the data file (random write)
     - record checkpoint LSN in the WAL
7. Crash before step 6? Recovery replays WAL from last checkpoint:
     - re-applies the UPDATE (redo) so the data page is reconstructed

Step-by-step explanation.

The engine needs the page holding row id=1. It is already in the buffer pool (a hit), so there is no disk read; the row is modified in the cached copy and the page is flagged dirty.
The change is described as a compact WAL record (old → new value, with the row's ctid and a log sequence number) and placed in the WAL buffer. If this is the first modification to the page since the last checkpoint, a full-page image is also logged for torn-page protection.
At COMMIT, a commit record is appended and the WAL is fsync'd up to that LSN. This single sequential fsync is the entire durability guarantee — the moment it returns, the transaction is safe even though the data page is still only in RAM.
Success is returned to the client. The dirty data page may sit in the buffer pool for seconds or minutes; nothing forces it to disk at commit time. Batching data-page writes this way is exactly what keeps write throughput high.
Eventually a checkpoint (or the background writer) flushes the dirty page to the data file as a random write and advances the checkpoint LSN. If the server crashes before that flush, recovery starts from the last checkpoint and replays the WAL — the redo re-applies the balance change, reconstructing the page. Because the WAL was fsync'd at commit, no committed change is ever lost.

Output.

Step	Disk I/O?	Kind
Modify page in buffer pool	no	RAM only
Log WAL record	buffered	—
COMMIT fsync WAL	yes	sequential (durability boundary)
Flush data page at checkpoint	yes (later)	random
Crash recovery	reads WAL	sequential redo

Rule of thumb. At commit, the only thing guaranteed on disk is the WAL fsync — the data page is flushed lazily. This is why WAL throughput (sequential) governs commit latency while data-page writes (random) are batched at checkpoints, and why a database can commit far faster than it could if every commit flushed its scattered data pages.

Worked example — the durability vs latency knob (synchronous_commit)

Detailed explanation. Because the commit fsync is the latency floor, databases expose a knob to relax it. In Postgres, synchronous_commit controls whether COMMIT waits for the WAL fsync. Turning it off makes commits return before the flush, trading a small, bounded window of possible data loss for much higher commit throughput.

synchronous_commit = on — commit waits for WAL fsync; zero committed-data loss on crash. The safe default.
synchronous_commit = off — commit returns immediately; a background flush happens within a short delay (e.g. up to wal_writer_delay). A crash can lose the last fraction of a second of committed transactions, but the database stays consistent (never corrupt) — only the tail is lost.
Group commit amortises fsync across concurrent commits regardless of the setting.

Question. A logging pipeline commits 50,000 small transactions/second and can tolerate losing <1 second of data on a crash. Show the setting and quantify the trade.

Input.

Requirement	Value
Commit rate	50,000 tx/s
Acceptable loss on crash	< 1 s of committed tx
Corruption tolerance	none (must stay consistent)
fsync latency (disk)	~1 ms

Code.

-- Per-session (or global) relax the commit fsync for this pipeline
SET synchronous_commit = off;

-- Now COMMIT does not wait for the WAL fsync; the wal writer flushes
-- in the background within ~wal_writer_delay (default 200 ms).
-- A crash can lose up to ~3 * wal_writer_delay of COMMITTED tx,
-- but the database is never left inconsistent.

-- Compare the throughput ceiling:
--   synchronous_commit=on  : commit latency floored by fsync (~1 ms)
--                            => a single session tops out ~1000 tx/s
--   synchronous_commit=off : commit returns without waiting on fsync
--                            => throughput limited by CPU/WAL bandwidth,
--                               not fsync latency (10-100x higher)

-- Keep it safe for the money-movement table by overriding per-txn:
BEGIN;
SET LOCAL synchronous_commit = on;   -- this txn WILL wait for fsync
UPDATE ledger SET balance = balance - 100 WHERE id = 1;
COMMIT;

Step-by-step explanation.

With synchronous_commit = on, each commit blocks on a ~1 ms fsync; a single connection is throughput-limited to roughly 1 / 1ms = 1000 serial commits per second, and hitting 50,000/s needs heavy concurrency plus group commit.
Setting synchronous_commit = off decouples commit from the fsync: the commit record is written to the WAL buffer and the client is told "committed" without waiting for the flush, which the WAL writer performs in the background within a bounded delay.
The bounded delay (a small multiple of wal_writer_delay) is exactly the maximum data-loss window — well under the 1-second tolerance — and crucially the database remains consistent: recovery replays whatever WAL made it to disk, so you lose only the un-flushed tail, never a torn or corrupt state.
Throughput is now limited by CPU and WAL bandwidth rather than fsync latency, so the pipeline can reach its 50,000 tx/s without a fleet of connections each stalling on fsync.
For rows that cannot lose a commit (a ledger), SET LOCAL synchronous_commit = on inside that transaction restores full durability just for it — the setting is per-transaction, so you pay the fsync cost only where it matters.

Output.

Setting	Commit waits for fsync?	Loss window on crash	Throughput
synchronous_commit=on	yes	none	fsync-bound (~1k tx/s/session)
synchronous_commit=off	no	< ~1 s (bounded)	CPU/WAL-bound (10–100×)
SET LOCAL on (per-txn)	yes for that txn	none for that txn	mixed

Rule of thumb. Durability and commit latency trade against each other at the WAL fsync. Use synchronous_commit = off for high-volume, loss-tolerant data (logs, metrics, events) and keep it on — per transaction if needed — for money-movement and anything where losing even the last second is unacceptable. The database stays consistent either way; only the tail of committed data is at risk.

SQL interview question on the write path and crash recovery

A senior interviewer might ask: "A junior engineer worries that because Postgres doesn't write the data page to disk at commit, a crash right after COMMIT will lose the transaction. Walk through what actually guarantees the commit survives, what recovery does on restart, and where the data page fits in — then explain the one setting that would make their fear real."

Solution Using WAL fsync at commit and checkpoint-bounded redo recovery

GUARANTEE — why a committed transaction survives a crash
========================================================
At COMMIT (synchronous_commit=on):
  1. change made to data page in buffer pool  (RAM, dirty)
  2. WAL record for the change written to WAL buffer
  3. COMMIT record appended to WAL buffer
  4. WAL fsync'd up to the commit LSN  <-- durable NOW
  5. client told "committed"
  => the data page may still be dirty in RAM; that is fine.

CRASH right after step 5:
  - data file may be stale (page never flushed)
  - but WAL on disk HAS the change (step 4 fsync'd it)

RECOVERY on restart:
  a. read the last CHECKPOINT record -> the redo start LSN
  b. REDO: replay every WAL record from that LSN forward,
     re-applying changes to data pages (using full-page images
     to repair any torn pages)
  c. UNDO: roll back transactions that never committed
  d. database is now exactly as of the last durable commit
  => the committed UPDATE is present. Nothing lost.

THE SETTING THAT MAKES THE FEAR REAL:
  synchronous_commit = off   (or fsync = off)
  -> COMMIT returns BEFORE the WAL fsync, so a crash can lose the
     last sub-second of committed transactions (still consistent).

Step-by-step trace.

Phase	What is durable	What is at risk
Before commit	nothing for this txn	whole txn
WAL fsync at commit	the change (in WAL)	nothing committed
After commit, pre-checkpoint	change in WAL; page dirty in RAM	nothing (WAL suffices)
Checkpoint	data page now on disk	nothing
Recovery (redo from checkpoint)	replays WAL to rebuild pages	uncommitted txns (undone)

The junior's fear confuses "the data page isn't on disk" with "the change isn't durable." Durability is provided by the WAL fsync, not by the data-page write: the sequential WAL flush at commit is the guarantee, and the random data-page write is deferred to a checkpoint precisely because deferring it is what keeps commits fast. On restart, redo replays the WAL from the last checkpoint to reconstruct any data pages that never made it to disk, so every committed transaction reappears. The only way the fear becomes real is disabling the commit-time flush (synchronous_commit = off or the dangerous fsync = off), which trades a bounded tail of committed data for throughput.

Output:

Scenario	Committed txn after crash?
synchronous_commit=on, crash after commit	survives (WAL redo)
crash before checkpoint	survives (WAL redo from checkpoint)
synchronous_commit=off, crash within delay	last <1 s may be lost (still consistent)
fsync=off, crash	may be lost or torn — unsafe, never in prod

Why this works — concept by concept:

WAL is the durability primitive — a committed change is safe the instant its WAL record is fsync'd, independent of the data page. Sequential WAL flushes are cheap; deferring the scattered data-page writes is what makes commits fast without sacrificing durability.
Checkpoints bound redo — recovery replays WAL only from the last checkpoint forward, so checkpoint frequency sets the trade between steady-state flush I/O and crash-recovery time. Everything before the checkpoint is already on disk.
Redo then undo — recovery first redoes all logged changes (bringing data pages up to the last durable WAL record), then undoes transactions that never committed, leaving the database exactly as of the last committed transaction.
Full-page images stop torn pages — logging a whole page image on its first change after a checkpoint lets recovery repair a page a crash left half-written; without it, a torn page would be unrecoverable. InnoDB's doublewrite buffer serves the same role.
Cost — one sequential fsync per commit (amortised across concurrent commits by group commit), plus periodic checkpoint flush I/O, plus WAL storage until the next checkpoint. In exchange you get crash durability with O(1) commit cost and bounded O(WAL-since-checkpoint) recovery — the trade every relational engine makes.

Systems
Topic — database
WAL, durability, and recovery problems

Practice →

Perf
Topic — optimization
Buffer-pool and I/O optimization problems

Practice →

Cheat sheet — storage-engine recipes

Page anatomy (Postgres 8KB heap page). Fixed 24-byte header (pd_lsn, checksum, pd_lower/pd_upper free-space pointers) → slot array of 4-byte line pointers growing down → free space in the middle → tuples growing up from the tail. Free bytes = pd_upper − pd_lower. A row's identity is its (page, slot) = ctid, and every index entry stores key + ctid. Inspect with pageinspect: SELECT * FROM page_header(get_raw_page('t', 0)); and heap_page_items(...).
Heap vs index-organized. Postgres = heap (unordered pages) + separate indexes; row found by ctid. MySQL/InnoDB = clustered (index-organized) table where the PK B-tree leaves are the rows, so secondary indexes store the PK, not a physical pointer. Heaps make secondary indexes cheap; clustered tables make PK range scans cheap.
B-tree vs LSM decision matrix. B-tree: reads O(log n) page fetches (3–4 levels for billions of rows), in-place updates, write amp from page splits and random writes — pick for read-heavy, point-lookup + range workloads (OLTP). LSM: writes O(1) append to memtable + WAL, reads check memtable + N SSTables (bloom-gated), read + space amp offset by compaction — pick for write-heavy, high-ingest, append-mostly (time-series, events, Kafka state).
Fillfactor recipe. fillfactor 100 for read-only/append-only tables (pack pages tight, fewer pages scanned); fillfactor 70–90 for update-heavy tables so UPDATEs stay on-page as HOT updates and skip index maintenance. Set with ALTER TABLE t SET (fillfactor = 80); VACUUM FULL t;.
Ordered keys beat random keys on a B-tree. Monotonic keys (BIGSERIAL, UUIDv7/ULID) append at the right-most leaf — hot page, dense fill, localised splits. Random UUIDv4 scatters inserts tree-wide — cold random writes, frequent splits, index bloat. Use UUIDv7 when you need UUID semantics without the write penalty.
Postgres page-inspection snippet. CREATE EXTENSION pageinspect; SELECT ctid, * FROM t LIMIT 5; shows physical addresses; SELECT relpages, reltuples FROM pg_class WHERE relname='t'; gives page count (translate query cost into page fetches, not rows).
LSM tuning knobs. Memtable size (bigger = fewer, larger flushes, more RAM at risk); compaction strategy (leveled = low read/space amp, high write amp, for read-mix; size-tiered = low write amp, higher read/space amp, for pure ingest); bloom-filter bits-per-key (~10 → ~1% FP; 15 → ~0.1% FP, more RAM). Watch that deletes free space only after tombstones compact (gc_grace_seconds in Cassandra).
The three amplifications. Write amp = bytes written to disk per user byte (inflated by compaction re-writes / B-tree splits); read amp = files or pages consulted per read; space amp = disk used per live byte (stale versions, dead tuples, partly-full pages). You cannot minimise all three — every engine and tuning choice spends one to buy another.
WAL + checkpoint durability recipe. Log the change and fsync the WAL before reporting commit (durability boundary); keep data pages dirty in the buffer pool; flush them at checkpoints so recovery only replays WAL from the last checkpoint. Enable full_page_writes (Postgres) / doublewrite (InnoDB) for torn-page protection. Recovery = redo from checkpoint, then undo uncommitted.
Durability vs latency knob. synchronous_commit = on (default) waits for the WAL fsync — zero committed-data loss, commit latency floored by fsync. synchronous_commit = off returns before the flush — bounded sub-second loss window, 10–100× throughput, still consistent (never corrupt). Set per-transaction with SET LOCAL synchronous_commit = on for ledgers. Group commit amortises fsync across concurrent commits.
Buffer pool sizing. Size the buffer pool (Postgres shared_buffers ~25% RAM; InnoDB innodb_buffer_pool_size ~70% on a dedicated box) so the working set is resident — then most reads never touch disk and the on-disk structure only matters on a cache miss. Monitor cache hit ratio and dirty-page flush pressure.
Real-system map. Postgres / MySQL-InnoDB / SQL Server / Oracle / SQLite = B-tree (heap or clustered). Cassandra / ScyllaDB / HBase / RocksDB / LevelDB = LSM tree. RocksDB is embedded inside CockroachDB, TiDB, MyRocks, and Kafka Streams state stores precisely because it is write-optimized.

Frequently asked questions

How do databases store data on disk?

Databases store data in fixed-size pages (typically 8KB in Postgres, 16KB in MySQL/InnoDB) that are the atomic unit of I/O between disk and memory. The simplest table storage is a heap file — an unordered collection of pages where each row is addressed by a (page_id, slot) pair — and on top of that the storage engine maintains one or more indexes so it can find rows without scanning every page. Reads and writes flow through a buffer pool (a cache of pages in RAM), and every change is first recorded in a write-ahead log so a crash can't lose a committed transaction. The two dominant on-disk index families are the read-optimized B-tree and the write-optimized LSM tree.

What is a database page and why is it usually 8KB?

A page is the smallest chunk of data a database reads from or writes to disk as a single unit — the engine never fetches "a row," it fetches the page the row lives on. A fixed size (8KB in Postgres, 16KB in InnoDB) is chosen because it aligns cleanly with filesystem and SSD block boundaries (so one page is one aligned I/O), it makes the buffer pool a simple array of identical frames, and it makes free-space accounting compact and predictable. The trade-offs are a little wasted space (rows rarely fill a page exactly) and the need for overflow/TOAST storage for values too large to fit inline. Every higher-level structure — heaps, B-tree nodes, LSM index blocks — is built out of these uniform pages.

B-tree vs LSM tree — which is better?

Neither is universally better; they optimise opposite workloads. A B-tree keeps keys sorted in a shallow balanced tree and updates in place, so reads (point lookups and range scans) cost only O(log n) page fetches — pick it for read-heavy OLTP with point lookups and ranges (Postgres, MySQL/InnoDB). An LSM tree buffers writes in an in-memory memtable plus a sequential log and flushes immutable sorted SSTables, so writes never seek and sustain very high throughput — pick it for write-heavy, high-ingest, append-mostly workloads like time-series, event logs, and metrics (Cassandra, RocksDB). The rule of thumb: match the engine's cheap operation (B-tree reads, LSM writes) to your dominant operation, and remember LSM pays with read and space amplification while the B-tree pays with write amplification.

What is the difference between a heap file and a clustered index?

A heap file stores rows in unordered pages with no relationship between a row's key and where it physically lands; you locate a row by its (page, slot) address, and indexes are separate structures that map keys to those addresses. This is how Postgres stores every table. A clustered index (index-organized table) instead stores the rows inside the leaves of the primary-key B-tree, so the table itself is sorted by the primary key — this is how MySQL/InnoDB stores tables. The consequences: heaps make secondary indexes cheap (they store a physical pointer) but scatter rows across pages; clustered tables make primary-key range scans very fast (rows are physically adjacent in PK order) but force secondary indexes to store the PK and do a second lookup to reach the row.

What is a write-ahead log and why is it needed?

A write-ahead log (WAL, or redo log / commit log) is a sequential on-disk log where a database records the description of every change before the corresponding data page is guaranteed to be written to disk. It is needed because writing scattered data pages on every commit would be slow (random I/O) and unsafe (a crash mid-write could corrupt a page). Instead the engine writes a compact change record to the WAL and fsyncs it at commit — a cheap sequential write that is the durability guarantee — while the actual data pages stay dirty in the buffer pool and are flushed later at a checkpoint. On a crash, recovery replays the WAL from the last checkpoint to reconstruct any changes that hadn't reached the data files, so no committed transaction is ever lost. Both B-tree and LSM engines rely on this same primitive.

What is the buffer pool and how does it speed up queries?

The buffer pool is a large region of RAM where the database caches recently-used pages; every read and write goes through it. When the engine needs a page it checks the buffer pool first — a hit serves the page from memory in nanoseconds, while a miss reads it from disk (microseconds on SSD, milliseconds on spinning disk) into a free frame. Modified pages become "dirty" and are flushed to disk lazily at checkpoints rather than on every write, which keeps commits fast. Because hot pages (a B-tree's root, frequently-read leaves, the working set) stay resident, most reads in a well-sized system never touch disk at all — which is why sizing the buffer pool so the working set fits (Postgres shared_buffers, InnoDB innodb_buffer_pool_size) is one of the highest-leverage tuning decisions, and why the on-disk structure only matters on a cache miss.

Practice on PipeCode

Drill the database practice library → for the storage-engine, page-layout, heap, B-tree, LSM, and durability problems interviewers love.
Work the indexing practice library → for B-tree lookup-cost, range-scan, clustered-vs-secondary, and index-design questions.
Sharpen query fluency on the SQL practice library → so you can prove an access-path change with EXPLAIN (ANALYZE, BUFFERS).
Push into the optimization practice library → for buffer-pool, write-amplification, and I/O-cost tuning drills.
Stack these against PipeCode's broader 450+ data-engineering catalogue to anchor the B-tree-vs-LSM decision matrix against real graded inputs.

Lock in storage-engine muscle memory

Docs explain the structures. PipeCode drills explain the decision — when a B-tree's page splits bite, when an LSM's read amplification creeps up, when the WAL fsync becomes your commit-latency floor, and when the buffer pool is the only thing standing between you and disk. Pipecode.ai is Leetcode for Data Engineering — internals-first practice tuned for the storage trade-offs senior data engineers actually face.

Practice database problems →
Practice indexing problems →

1. Why storage-engine internals decide every query's cost

The stack beneath SQL is a chain of physical decisions, and the storage engine is where they all land

Worked example — counting page fetches, not rows

Worked example — mapping real systems to their storage engine

Data engineering interview question on storage-engine selection

Solution Using a B-tree for reads and an LSM tree for ingest, justified by page-level cost

2. Pages & the heap — the fundamental unit of storage

The fixed-size page is the atom of storage, and the heap is the unordered pile of pages your rows land in

Worked example — where a single row physically lives (ctid)

Worked example — reading a page header and computing fill factor

SQL interview question on heap storage and row location

Solution Using a B-tree index to replace a full heap scan, proven with page counts

3. B-Tree storage — the read-optimized default

A B-tree is a shallow, balanced tree of pages that keeps keys sorted so reads touch only a handful of pages

Worked example — tracing a point lookup root → leaf

Worked example — a range scan walking the leaf chain

Data engineering interview question on B-tree write amplification

Solution Using an ordered key to convert random splits into sequential appends

4. LSM Trees — memtable, SSTables, compaction: the write-optimized alternative

An LSM tree turns every write into an in-memory append plus a sequential log, deferring the sorting and merging to background compaction

Worked example — a key's life from write to compaction

Worked example — bloom filters keep reads from scaling with SSTable count

Systems interview question on LSM read amplification

Solution Using compaction-strategy and bloom-filter tuning to trade the three amplifications

5. WAL, buffer pool & durability — how a write actually lands

A committed write is durable because its change is logged and fsync'd before the data page is guaranteed on disk, while the buffer pool serves reads from RAM

Worked example — an UPDATE traced end-to-end

Worked example — the durability vs latency knob (synchronous_commit)

SQL interview question on the write path and crash recovery

Solution Using WAL fsync at commit and checkpoint-bounded redo recovery

Cheat sheet — storage-engine recipes

Frequently asked questions

How do databases store data on disk?

What is a database page and why is it usually 8KB?

B-tree vs LSM tree — which is better?

What is the difference between a heap file and a clustered index?

What is a write-ahead log and why is it needed?

What is the buffer pool and how does it speed up queries?

Practice on PipeCode

Lock in storage-engine muscle memory

Worked example — where a single row physically lives (`ctid`)