CHAPTER 03

Storage Engines, Indexing Mechanics & Database Internals

The heart of every database is its storage engine. Choosing between in-place page updates (B+ Trees) and log-structured merge trees (LSM Trees) dictates read amplification, write throughput, disk wear, and compaction overhead.

1. B+ Trees vs LSM Trees (Deep Mechanics)

B+ Trees (In-Place Updating)

Organized in fixed-size physical disk blocks (pages, e.g., 8KB in PostgreSQL, 16KB in MySQL InnoDB). Internal nodes contain branch search keys; leaf nodes hold table row pointers or clustered data and are linked sequentially for fast range scans.

• Read Complexity: \(O(\log_B N)\) bounded disk seeks.
• Page Split Overhead: Inserting into a full page causes a split, cascading up the tree.
• High Write Amplification: A single row update writes an entire 8KB page.

LSM Trees (Log-Structured Merge Trees)

Append-only architecture. Incoming writes are appended sequentially to a Write-Ahead Log (WAL) and stored in an in-memory sorted SkipList/Red-Black Tree (**MemTable**). When full, the MemTable is flushed to an immutable **SSTable** (Sorted String Table) on disk.

• Write Throughput: Extremely high sequential IO (no random disk seeks).
• Read Amplification: Requires checking MemTable, Bloom filters, and multiple SSTable levels.
• Compaction: Background threads merge SSTables to reclaim deleted keys.

B+ Tree Page Structure

LSM Tree Ingestion Pipeline

2. SSTable Compaction Strategies

Size-Tiered Compaction (STCS)

Merges SSTables of similar sizes into a larger SSTable. Fast for write-heavy workloads, but requires up to 50% temporary free disk space during major compactions.

Leveled Compaction (LCS)

Divides disk into levels (\(L_0, L_1, L_2, \dots\)). Each level has a max size (\(L_1=10\text{MB}, L_2=100\text{MB}, L_3=1\text{GB}\)). Guarantees non-overlapping keys in \(L_1+\), reducing read amplification dramatically.

3. ACID Transactions & Write-Ahead Logging (WAL)

Atomicity All operations in transaction succeed or entire transaction rolls back via WAL undo logs.

Consistency Database transitions from one valid state satisfying all schema constraints to another.

Isolation Concurrent transactions execute without interfering with one another (enforced via MVCC / 2PL).

Durability Committed transactions are persisted to disk WAL log even if power fails immediately after.

4. Isolation Levels & Concurrency Anomalies

Isolation Level	Dirty Read	Non-Repeatable Read	Phantom Read	Write Skew
Read Uncommitted	Allowed	Allowed	Allowed	Allowed
Read Committed	Prevented	Allowed	Allowed	Allowed
Repeatable Read	Prevented	Prevented	Allowed (PG prevents)	Allowed
Serializable	Prevented	Prevented	Prevented	Prevented