Database Systems & Storage Engines

Relational and storage engine internals: B-Tree disk page layouts, write-ahead logging (WAL), two-phase locking (2PL), MVCC snapshot isolation, and composite indexing.

ACID Properties & Write-Ahead Logging (WAL)

Relational databases (PostgreSQL, MySQL InnoDB, SQLite) rely on the ACID paradigm to ensure data integrity under concurrent transactions and system crashes.

Atomicity (All-or-Nothing):Every transaction either completes entirely or rolls back with zero partial writes.
Consistency (Valid Invariants):Data must satisfy all schema constraints, foreign keys, and unique indexes before and after commit.
Isolation (Concurrent Non-Interference):Controls visibility of uncommitted changes across concurrent transactions via 4 ANSI SQL isolation levels.
Durability (Persistence via WAL):Changes are appended to the Write-Ahead Log on non-volatile disk before updating in-memory buffer pool pages.

Write-Ahead Logging (WAL): Every INSERT/UPDATE writes a sequential redo log record to disk via fsync(). In the event of a power outage, crash recovery replays the WAL to restore committed transactions.
B+ Tree Index Structure: Data is organized in a balanced multi-way tree with a high branching factor (fanout ~100-500). All data values are stored in the leaf nodes, which are linked as a doubly-linked list for ultra-fast range queries O(log_B N + K).
Multi-Version Concurrency Control (MVCC): Instead of locking rows for reads, PostgreSQL and MySQL maintain multiple row versions with xmin/xmax transaction IDs. Readers never block writers, and writers never block readers.

Definition: Multi-Version Concurrency Control (MVCC)

A database concurrency mechanism where each transaction sees a point-in-time snapshot of the database, enabling non-blocking concurrent reads without acquiring exclusive shared locks.

B+ Tree Height & Lookup Cost

Tree Height H = ceil( log_B (N / LeafCapacity) ) ==> Disk I/Os <= 3-4

Variable Definitions & Term Breakdown:

B (Fanout)Number of child pointers per 8KB/16KB page (typically 100 to 500)

NTotal records in table (even for 1 billion rows, B+ Tree height is only 3 or 4)

ANSI SQL Isolation Levels & Concurrency Phenomena

Isolation Level	Dirty Read	Non-Repeatable Read	Phantom Read
Read Uncommitted	Allowed (Dirty)	Allowed	Allowed
Read Committed (Default in Postgres)	Prevented	Allowed	Allowed
Repeatable Read (Default in MySQL)	Prevented	Prevented	Prevented (MVCC)
Serializable	Prevented	Prevented	Prevented

Trade-offs between throughput performance and data consistency

Tip

When designing composite B+ Tree indexes `(colA, colB)`, order columns by equality filters first (`colA = 5`), followed by range filters (`colB > 10`). A B+ Tree can only use index seek on ONE range predicate.

PythonSimulated MVCC Snapshot Read Engine

1class MVCCStore:
2    def __init__(self):
3        self.records = {} # key -> list of (xmin, xmax, value)
4        self.tx_counter = 100
5 
6    def insert(self, key, value, tx_id):
7        if key not in self.records:
8            self.records[key] = []
9        self.records[key].append({'xmin': tx_id, 'xmax': None, 'val': value})
10 
11    def update(self, key, new_val, tx_id):
12        for version in self.records.get(key, []):
13            if version['xmax'] is None:
14                version['xmax'] = tx_id
15        self.records[key].append({'xmin': tx_id, 'xmax': None, 'val': new_val})
16 
17    def read(self, key, reader_snapshot_tx):
18        for version in self.records.get(key, []):
19            if version['xmin'] <= reader_snapshot_tx and (version['xmax'] is None or version['xmax'] > reader_snapshot_tx):
20                return version['val']
21        return None
22 
23db = MVCCStore()
24db.insert('balance', 1000, tx_id=101)
25 
26# Transaction 102 starts snapshot
27snapshot_tx = 102
28 
29# Transaction 103 updates balance to 2500
30db.update('balance', 2500, tx_id=103)
31 
32print('Snapshot TX 102 View:', db.read('balance', 102))
33print('Current TX 104 View:', db.read('balance', 104))

Output

Snapshot TX 102 View: 1000
Current TX 104 View: 2500

SQLSQL Transaction Isolation & B+ Tree Index Creation

1-- Create composite B+ Tree index
2CREATE INDEX idx_orders_user_created ON orders (user_id, created_at DESC);
3 
4-- Set Serializable Isolation for atomic balance transfer
5SET TRANSACTION ISOLATION LEVEL SERIALIZABLE;
6BEGIN;
7  UPDATE accounts SET balance = balance - 500 WHERE id = 1;
8  UPDATE accounts SET balance = balance + 500 WHERE id = 2;
9COMMIT;

Output

[Transaction Committed Successfully - Zero Dirty Reads]

Quick Syntax & Reference Sheet

Concept / Rule	Syntax / Usage
Composite Index Rule	`CREATE INDEX idx ON table (equality_col, range_col)`
EXPLAIN ANALYZE	`EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM table WHERE condition;`

Common Pitfalls & Developer Mistakes

✕ Mistake 1:

Applying functions to indexed columns in WHERE clause (e.g. WHERE YEAR(created_at) = 2026)

Why it happens: Wrapping an indexed column in a function prevents the database query optimizer from performing an index seek, forcing a full table scan.

Correction: Rewrite queries using range comparisons without column function wrappers.

# Incorrect (Full Scan):
WHERE YEAR(created_at) = 2026

# Correct (Index Seek):
WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'

Frequently Asked Questions

Why do databases use B+ Trees instead of Binary Search Trees (Red-Black / AVL)?

Disk I/O Block Size. Memory on disks/SSDs is read in 4KB/8KB/16KB blocks. A binary tree node only holds 1 key per node, requiring dozens of sequential disk seeks. A B+ Tree node holds hundreds of keys per block, reducing tree height to 3-4 levels for billions of records.