system-design · intermediate

Database Storage Architectures — B-Trees vs. LSM-Trees

The Central Question

Consider two high-scale software applications running on the DataLab platform (datalab.com):

• Workload A (Financial Banking Engine): Executes 50,000 read queries per second retrieving specific user account rows by primary key. Queries require sub-2ms read response times, but write volume is moderate (2,000 writes/sec).
• Workload B (IoT Sensor Ingestion): Ingests 250,000 metrics per second from global temperature sensors. Writes occur continuously in heavy random bursts, while reads are infrequent historical range queries.

• Workload A achieves blazing-fast sub-millisecond read seeks.
• Workload B causes severe disk Write Amplification. Random writes force random 8 KB disk page updates, thrashing disk I/O, fragmenting pages, and stalling server CPU.

• Workload B ingests 250,000 writes per second effortlessly by appending sequential records into RAM.
• Workload A suffers from Read Amplification, searching across multiple SSTable disk files to locate a single user record.

The Core Trade-Off: Read Amplification vs. Write Amplification

Every database storage architecture makes a fundamental trade-off governed by disk physics:

flowchart LR
  subgraph B-Tree Storage Model: Read-Optimized
    BTree[In-Place Page Updates] -->|Low Read Amplification| BRead[Fast O(log N) Single Disk Seek]
    BTree -->|High Write Amplification| BWrite[Random Disk Writes Thrash I/O]
  end
subgraph LSM-Tree Storage Model: Write-Optimized
    LSM[Append-Only Sequential Writes] -->|Low Write Amplification| LWrite[Fast Sequential RAM/Disk Appends]
    LSM -->|High Read Amplification| LRead[Searches MemTable + Multiple SSTable Disk Files]
  end

Figure 1: Trade-off comparison between B-Tree in-place updates and LSM-Tree append-only structures.

The Storage Mechanics Definitions

• Write Amplification: The ratio of bytes written to physical disk storage relative to bytes submitted by the application.

• Read Amplification: The number of physical disk page reads required to satisfy a single application read query.
• Space Amplification: The ratio of physical disk space consumed on disk relative to pure uncompressed payload size (caused by fragmentation and obsolete row versions).

1. B-Tree Storage Architecture (In-Place Updates)

B-Trees (and their variants like $\text{B}^+\text{Trees}$) organize database files into fixed-size blocks called Pages (typically 4 KB to 16 KB).

flowchart TD
  RootPage[Root Page: Keys 10, 50, 100] --> NodeLeft[Internal Node: Keys 10 to 49]
  RootPage --> NodeRight[Internal Node: Keys 50 to 99]
  
  NodeLeft --> Leaf1[Leaf Page 1: Keys 10..25 + Pointer to Row Data]
  NodeLeft --> Leaf2[Leaf Page 2: Keys 26..49 + Pointer to Row Data]
  
  NodeRight --> Leaf3[Leaf Page 3: Keys 50..75 + Pointer to Row Data]
  NodeRight --> Leaf4[Leaf Page 4: Keys 76..99 + Pointer to Row Data]

Figure 2: Balanced B+Tree page hierarchy linking root, internal, and leaf pages.

How B-Trees Handle Writes and Reads

1. Reads ($O(\log N)$): The database loads the root page into RAM, traverses internal branch nodes down the tree, and lands on the exact leaf page containing the target key. Point reads require a deterministic number of page seeks ($3 \text{ to } 4$ hops for billions of rows).
2. Writes (In-Place Page Mutation):

The Write-Ahead Log (WAL)

2. Log-Structured Merge-Tree (LSM-Tree) Architecture

LSM-Trees eliminate random disk writes by converting all mutation operations (INSERT, UPDATE, DELETE) into sequential append-only writes.

flowchart TB
  subgraph Memory Layer
    WAL[Sequential Write-Ahead Log on Disk]
    MemTable[MemTable: Sorted SkipList in RAM]
  end
subgraph Disk Layer
    SST0[Level 0 SSTables: Un-Sorted Flushed Runs]
    SST1[Level 1 SSTables: Key-Sorted Compacted Runs]
    SST2[Level 2 SSTables: Larger Compacted Runs]
  end
AppWrite[Application Write] --> WAL
  AppWrite --> MemTable
  MemTable -->|MemTable Full: Flush to Disk| SST0
  SST0 -->|Background Compaction| SST1
  SST1 -->|Background Compaction| SST2

Figure 3: Multi-tiered LSM-Tree architecture moving data from RAM MemTables to Level 0..N SSTables.

The 4 Pillars of LSM-Tree Storage

1. MemTable (RAM):

1. Write-Ahead Log (WAL on Disk):

1. Sorted String Tables (SSTables on Disk):

1. Deletes (Tombstones):

LSM-Tree Compaction: Leveled vs. Size-Tiered

Over time, flushing MemTables creates hundreds of immutable SSTable files on disk. To prevent read performance from degrading, the LSM-Tree engine merges SSTables using Compaction:

flowchart TD
  subgraph Size-Tiered Compaction
    ST1[SSTable 1: 64MB] & ST2[SSTable 2: 64MB] & ST3[SSTable 3: 64MB] & ST4[SSTable 4: 64MB]
    ST1 & ST2 & ST3 & ST4 -->|Merge-Sort| STBig[Single 256MB SSTable]
  end
subgraph Leveled Compaction
    L0[L0: Overlapping Keys] -->|Promote & Merge-Sort| L1[L1: Non-Overlapping Key Ranges]
    L1 -->|Promote & Merge-Sort| L2[L2: 10x Larger Key Ranges]
  end

Figure 4: Comparing Size-Tiered Compaction against Leveled Compaction.

1. Size-Tiered Compaction

• Mechanism: When $N$ SSTables of similar file size accumulate in a level, the engine merges them into a single larger SSTable.
• Best For: Write-heavy workloads with minimal reads.
• Drawback: High Space Amplification (requires up to 50% free disk space to execute merge operations).

2. Leveled Compaction (RocksDB / LevelDB Standard)

• Mechanism: Disk storage is divided into discrete levels ($L_1, L_2, L_3, \dots$). Each level has a strict capacity limit (e.g. $L_1 = 10\text{ MB}$, $L_2 = 100\text{ MB}$, $L_3 = 1\text{ GB}$).
• Within $L_1$ and higher, key ranges across SSTables are strictly non-overlapping.
• Best For: Read-heavy or balanced workloads. Reduces Read Amplification by guaranteeing that a key exists in at most one SSTable per level.

Architectural Comparison: B-Tree vs. LSM-Tree

Complete Worked Example: Go LSM-Tree MemTable & SSTable Flush Engine

Let's inspect the complete Go implementation of an in-memory MemTable that flushes sorted key-value pairs to disk as an immutable SSTable for the DataLab engine (datalab.com).

package main
import (
	"bytes"
	"encoding/binary"
	"fmt"
	"os"
	"sort"
	"sync"
)
type DataEntry struct {
	Key   string
	Value string
}
type MemTable struct {
	mu        sync.RWMutex
	data      map[string]string
	sizeBytes int
	maxSize   int
}
func NewMemTable(maxSizeBytes int) *MemTable {
	return &MemTable{
		data:    make(map[string]string),
		maxSize: maxSizeBytes,
	}
}
func (m *MemTable) Put(key, value string) bool {
	m.mu.Lock()
	defer m.mu.Unlock()
m.data[key] = value
	m.sizeBytes += len(key) + len(value)
// Return true if MemTable exceeds capacity limit and requires disk flush
	return m.sizeBytes >= m.maxSize
}
// FlushMemTableToSSTable writes sorted entries sequentially to disk
func (m *MemTable) FlushMemTableToSSTable(filename string) error {
	m.mu.Lock()
	defer m.mu.Unlock()
// 1. Sort keys alphabetically (Mandatory for SSTables!)
	keys := make([]string, 0, len(m.data))
	for k := range m.data {
		keys = append(keys, k)
	}
	sort.Strings(keys)
// 2. Open binary file for sequential writing
	file, err := os.Create(filename)
	if err != nil {
		return err
	}
	defer file.Close()
var buf bytes.Buffer
	for _, k := range keys {
		v := m.data[k]
		// Write Key Length (4 bytes), Value Length (4 bytes), Key Bytes, Value Bytes
		binary.Write(&buf, binary.BigEndian, uint32(len(k)))
		binary.Write(&buf, binary.BigEndian, uint32(len(v)))
		buf.WriteString(k)
		buf.WriteString(v)
	}
_, err = file.Write(buf.Bytes())
	if err == nil {
		fmt.Printf("[SSTABLE FLUSH SUCCESS] Flushed %d keys to %s\n", len(keys), filename)
		m.data = make(map[string]string)
		m.sizeBytes = 0
	}
	return err
}

Failure Modes and Engineering Mitigations

What You Should Remember

1. B-Trees optimize for reads: B-Trees use balanced in-place page structures to deliver fast, deterministic $O(\log N)$ point reads.
2. LSM-Trees optimize for writes: LSM-Trees convert random writes into sequential appends in RAM (MemTables) before flushing immutable SSTables to disk.
3. MemTables use WALs for crash durability: MemTables store sorted writes in RAM for speed; WALs log writes to disk for recovery.
4. Compactions clean up SSTables and Tombstones: Background compactions merge immutable SSTables and purge deleted Tombstone markers.
5. Use UUIDv7 to prevent B-Tree page splits: Sequential primary keys prevent destructive B-Tree page split thrashing.

Glossary of Terms

Practice Scenario and Self-Assessment

Architecture Scenario

1. User Auth Store (10,000 read queries/sec, primary key lookups, strict low read latency)
2. Clickstream Event Log (500,000 append-only event writes/sec, continuous ingestion)

1. Recommend whether a B-Tree or LSM-Tree engine is appropriate for each of the two workloads and justify your reasoning.
2. Explain why inserting random UUIDv4 primary keys causes high Write Amplification in B-Trees but not in LSM-Trees.

Interactive Self-Assessment

LSM-Trees convert random writes into fast sequential RAM and disk append operations.

LSM-Trees store all historical data permanently in RAM without writing to disk.

LSM-Trees bypass database index structures completely.

LSM-Trees do not use operating system file systems.

It marks a key as deleted in memory/disk without modifying existing immutable SSTable files immediately.

It encrypts old SSTable files to prevent unauthorized data access.

It signals the API gateway to disconnect client TCP sockets.

It resets the primary key AUTO_INCREMENT counter to zero.

What to Learn Next

• Database Scaling Strategies — Replicas, Shards, and Multiplexing: Learn how to scale database storage engines across clusters.
• Types of Databases — Matching Tools to Access Patterns: Explore database paradigms beyond storage engines.
• Database Indexing — B-Trees and Left-Prefix Rules: Deep dive into B-Tree index structures and query optimization.

Track: Data, Storage and Messaging

Previous: Consistent Hashing — Rings, Virtual Nodes, and Minimal Rebalancing

Next: Database Indexes — Find Rows Without Scanning Everything

By Shubham Jain

All articles · Study paths

Shubham Jain · Learning Lab