Database Internals: B-Trees, LSM Trees, WAL & Query Execution Plans

A database is not a dumb storage box — it is a contract between your write path, your read path, and your consistency guarantees. Every design decision you defer becomes a production incident you eventually own. The most deferred decision in backend engineering is this: understanding what the storage engine is actually doing when you call INSERT, SELECT, or CREATE INDEX. Engineers who skip this layer add indexes until queries stop being slow, then wonder why write throughput collapsed. They disable fsync for performance, then lose data in a crash. They stare at EXPLAIN output and see words. This article closes that gap.

1. B-Tree Internals: Why Adding Indexes Is Not Free

Every relational database you have ever used — Postgres, MySQL, SQLite — stores its indexes as a B-Tree by default. Understanding the B-Tree is not academic. It is the direct explanation for why a table with 20 indexes on it writes slower than one with 3, and why VACUUM is not optional.

1.1 Page Structure and Node Splits

A B-Tree organizes data into fixed-size pages (8 KB in Postgres). Each page is either:

• An internal node — holds fence keys and pointers to child pages
• A leaf node — holds the actual index entries (key + heap pointer)

When you insert a new row, the database walks the tree to the correct leaf page and inserts the key. If the leaf page is full, it splits: the page divides into two, and the parent internal node receives a new fence key pointing to the new sibling. If the parent is also full, the split propagates upward — potentially all the way to the root.

-- ❌ This table has 12 indexes on a write-heavy orders table.
-- Every INSERT fires up to 12 separate B-Tree page-split chains.
CREATE TABLE orders (
  id          BIGSERIAL PRIMARY KEY,
  customer_id BIGINT,
  product_id  BIGINT,
  status      TEXT,
  created_at  TIMESTAMPTZ DEFAULT now()
);
CREATE INDEX idx_orders_customer   ON orders(customer_id);
CREATE INDEX idx_orders_product    ON orders(product_id);
CREATE INDEX idx_orders_status     ON orders(status);
CREATE INDEX idx_orders_created    ON orders(created_at);
-- ... 8 more indexes added "just in case"

-- ✅ Audit indexes against actual query patterns.
-- Keep only indexes that appear in EXPLAIN output as Index Scan or Bitmap Index Scan.
-- Every index is a write tax paid on every INSERT, UPDATE, and DELETE.

1.2 Fill Factor: The Write Buffer Inside the Page

Postgres lets you configure fillfactor per table or index (default: 100 for indexes, 100 for tables). A fillfactor of 70 leaves 30% of each page empty on initial fill. That empty space absorbs future inserts and HOT (Heap-Only Tuple) updates without triggering a page split.

-- ✅ For write-heavy tables with frequent updates to indexed columns,
-- a lower fill factor reduces page splits at the cost of slightly larger index size.
CREATE INDEX idx_orders_status ON orders(status) WITH (fillfactor = 70);

2. LSM Tree Internals: The Write-Optimized Alternative

B-Trees are read-optimized: any key lookup is O(log n) with at most a handful of page reads. But their write path — which involves random page reads, in-place updates, and potential cascading splits — is a poor fit for workloads that are write-dominant with large data volumes.

Log-Structured Merge-Trees (LSM Trees) invert the tradeoff. They are used by RocksDB (the engine powering CockroachDB, TiKV, and PlanetScale), Cassandra, and LevelDB. Understanding them matters because engineers increasingly interact with these engines without realizing it.

2.1 The Memtable → SSTable Pipeline

LSM Trees operate in two tiers:

1. Memtable (in-memory): incoming writes are appended to an in-memory sorted structure. Reads check the memtable first.
2. SSTables (on-disk): when the memtable reaches a size threshold, it is flushed to disk as an SSTable — a sorted, immutable file. SSTables accumulate over time.

Write path:   client → memtable (RAM) → WAL (sequential disk write)
Flush:        memtable → SSTable Level 0 (immutable, sorted)
Compaction:   Level 0 SSTables → merged into Level 1 → Level 2 → ...
Read path:    memtable → Level 0 SSTables → Level 1 → ... (bloom filter short-circuits misses)

2.2 Write Amplification vs Read Amplification

The fundamental tradeoff between B-Trees and LSM Trees is measured in amplification factors:

Expand

3. Write-Ahead Log (WAL): The Source of Atomicity

Every write to a Postgres table goes through the Write-Ahead Log before it touches the actual data file. This is not a backup mechanism. It is the primitive that makes transactions atomic and durable.

3.1 Anatomy of a WAL Record

When you execute UPDATE orders SET status = 'shipped' WHERE id = 42, Postgres:

1. Appends a WAL record to the WAL segment file on disk (sequential write — fast)
2. Modifies the page in the shared buffer pool (in RAM — fast)
3. The modified page is now a dirty page — it has not been written to the heap file yet

The dirty page is flushed to the heap file asynchronously by the background writer and the checkpoint process.

client COMMIT
  │
  ├─▶ WAL record appended (sequential disk write)    ← durability guaranteed here
  │    └── fsync() called if synchronous_commit = on
  │
  ├─▶ shared_buffers page marked dirty (in RAM)
  │
  └─▶ COMMIT ACK returned to client ✅
         │
         └── (async) bgwriter flushes dirty page to heap file on disk

3.2 Crash Recovery: WAL Replay

If the server crashes between the WAL write and the heap file flush, Postgres recovers by replaying WAL records from the last checkpoint forward. Every committed transaction whose WAL record exists is replayed; every uncommitted transaction is rolled back.

This is why the WAL record must be written to durable storage before the commit acknowledgment is returned. The heap file state is always reconstructable from the WAL.

Expand

3.3 fsync and What Disabling It Actually Means

-- ❌ A common "performance optimization" seen in staging configs that leaks into production
-- synchronous_commit = off   -- WAL record not fsynced before COMMIT ACK
-- fsync = off                -- OS buffer not flushed to disk at all

synchronous_commit = off is safer: it returns the COMMIT ACK before the WAL record is fsynced, risking loss of the last few committed transactions on crash — but without the cluster-corruption risk of fsync = off. Use it only where you can tolerate losing the last ~200ms of commits (e.g., analytics event ingestion, not financial transactions).

4. Query Execution Plans: Reading EXPLAIN ANALYZE Like Source Code

Most engineers EXPLAIN a query once, see "Seq Scan," add an index, and move on. The actual skill is reading the full EXPLAIN ANALYZE output and understanding why the planner made each decision — because the planner is sometimes wrong, and knowing when it is wrong is the only way to fix it.

4.1 EXPLAIN ANALYZE Output Anatomy

EXPLAIN ANALYZE
SELECT o.id, c.name
FROM orders o
JOIN customers c ON c.id = o.customer_id
WHERE o.status = 'pending'
  AND o.created_at > now() - interval '7 days';

Hash Join  (cost=1240.55..3891.20 rows=1842 width=24) (actual time=18.432..42.891 rows=2341 loops=1)
  Hash Cond: (o.customer_id = c.id)
  ->  Bitmap Heap Scan on orders o  (cost=89.12..2510.44 rows=1842 width=16) (actual time=2.341..28.104 rows=2341 loops=1)
        Recheck Cond: ((status = 'pending') AND (created_at > (now() - '7 days'::interval)))
        ->  Bitmap Index Scan on idx_orders_status_created  (cost=0.00..88.66 rows=1842 width=0) (actual time=2.012..2.012 rows=2341 loops=1)
              Index Cond: ((status = 'pending') AND (created_at > (now() - '7 days'::interval)))
  ->  Hash  (cost=820.00..820.00 rows=20000 width=16) (actual time=14.221..14.221 rows=20000 loops=1)
        ->  Seq Scan on customers c  (cost=0.00..820.00 rows=20000 width=16) (actual time=0.012..9.441 rows=20000 loops=1)
Planning Time: 0.812 ms
Execution Time: 43.204 ms

Key fields to read:

4.2 When Estimated ≠ Actual: The Planner Lies

-- ❌ Planner estimated 12 rows, actually scanned 48,000
Seq Scan on orders  (cost=0.00..2840.00 rows=12 width=48) (actual rows=48241 loops=1)

This gap — estimated 12, actual 48,241 — means the planner's statistics are stale. It chose a Seq Scan because it thought the table had 12 matching rows, for which an index scan would be more expensive. With 48,000 rows, an index scan would have been dramatically faster.

-- ✅ Fix: Update statistics so the planner has accurate row count estimates
ANALYZE orders;

-- For heavily skewed data distributions, increase the statistics target
-- (default is 100 samples; for high-cardinality columns, go higher)
ALTER TABLE orders ALTER COLUMN status SET STATISTICS 500;
ANALYZE orders;

4.3 Join Strategies: When the Planner Chooses Each

Postgres chooses between three join algorithms based on estimated input sizes and available memory:

-- ❌ Forcing a nested loop on a large unsorted inner table
-- (Postgres may choose this if statistics are wrong)
SET enable_hashjoin = off;  -- never do this in production

-- ✅ If the planner consistently picks the wrong join strategy,
-- fix the root cause: update statistics, add an index on the join key,
-- or increase work_mem so hash joins can build their hash table in RAM.
SET work_mem = '64MB';  -- per-sort, per-hash-table allocation

5. Index Types Beyond B-Tree

The default CREATE INDEX creates a B-Tree. For many production access patterns, a more specialized index type delivers order-of-magnitude improvements.

5.1 Partial Indexes

A partial index indexes only rows matching a WHERE predicate. For tables where queries almost always filter on a status column with low cardinality (most rows are completed, queries almost always ask for pending), a partial index on the minority set is dramatically smaller and faster.

-- ❌ Full index on all 10M rows, but 98% of queries only want 'pending' (50K rows)
CREATE INDEX idx_orders_status ON orders(status);

-- ✅ Partial index: only indexes the 50K pending rows
-- Smaller index → fits in cache → faster scans
CREATE INDEX idx_orders_pending ON orders(created_at)
  WHERE status = 'pending';

-- Queries that include WHERE status = 'pending' will use this index automatically.

5.2 Covering Indexes

A covering index includes additional columns beyond the indexed key using INCLUDE. When all columns needed by a query are in the index, Postgres can answer the query from the index alone — an Index-Only Scan — without touching the heap file.

-- ❌ This query hits the index to find matching rows, then fetches the heap for 'name'
SELECT id, name FROM customers WHERE email = 'user@example.com';

-- ✅ Covering index: includes 'name' in the index leaf pages
-- Postgres never touches the heap for this query pattern
CREATE INDEX idx_customers_email_cover
  ON customers(email) INCLUDE (name, id);

5.3 Expression Indexes

An expression index indexes the result of a function or expression. This is essential for case-insensitive searches and computed filters that appear in WHERE clauses.

-- ❌ This query cannot use a standard index on email because of lower()
SELECT * FROM users WHERE lower(email) = lower('User@Example.com');

-- ✅ Index on the expression — now the query matches the index perfectly
CREATE INDEX idx_users_email_ci ON users(lower(email));

6. Diagnosing Bloat: The Silent Table Decay

Postgres uses MVCC (Multi-Version Concurrency Control) — it never overwrites a row in place. An UPDATE writes a new row version and marks the old version as dead. A DELETE marks the row as dead. Dead rows accumulate until VACUUM reclaims their space.

-- Detect table bloat (requires pgstattuple extension)
SELECT
  schemaname,
  tablename,
  pg_size_pretty(pg_total_relation_size(schemaname || '.' || tablename)) AS total_size,
  pg_size_pretty(
    pg_total_relation_size(schemaname || '.' || tablename)
    - pg_relation_size(schemaname || '.' || tablename)
  ) AS index_size
FROM pg_tables
WHERE schemaname = 'public'
ORDER BY pg_total_relation_size(schemaname || '.' || tablename) DESC
LIMIT 20;

-- For severe bloat: rebuild the index without locking
REINDEX INDEX CONCURRENTLY idx_orders_status;

-- For severe table bloat without locking
VACUUM (VERBOSE, ANALYZE) orders;

Summary

What's Next

In Part 2a, we build on the WAL atomicity foundation established here to examine isolation levels and concurrency control — the formal specification of which data anomalies your application is designed to tolerate, and the exact SQL that prevents each one. → Isolation & Concurrency Control