Storage & Retrieval

Chapter 1: Hash Indexes

The simplest possible index is the one you already know from any programming language: a hash map (dictionary, hash table). The idea: keep the append-only log file on disk, but maintain an in-memory hash map that maps every key to the byte offset where that key's most recent value starts in the file.

When you write a key, you append to the file (just like before), then update the hash map to point to the new byte offset. When you read a key, you look it up in the hash map (O(1)), seek to that byte offset on disk (O(1)), and read the value. Both operations are now fast.

This is not a toy idea. This is exactly how Bitcask, the default storage engine of Riak, works. Bitcask offers very fast reads and writes as long as all keys fit in memory.

The Mechanics, Step by Step

Let us trace through a concrete example. We will insert five key-value pairs and watch both the log file and the hash map evolve:

Notice that the old value for "cat" (Whiskers at offset 0) is still in the file. It just wastes space. This is where compaction comes in.

Compaction and Segment Merging

The log file grows forever because we never delete old entries. To reclaim space, we perform compaction: read the entire segment, discard all but the latest value for each key, and write a new, smaller segment file.

In practice, you do this in the background while the current segment continues accepting writes. Once the new compacted segment is ready, you atomically switch reads to it and delete the old one. This is the same pattern as a garbage collector — never block the live path.

You can also break the log into fixed-size segments (e.g., when a file reaches 1 GB, close it and start a new one). Then compaction can merge multiple segments into one, discarding duplicate keys.

Interactive Hash Index

The simulation below lets you insert keys into a Bitcask-style hash index. Watch the log file grow on the left and the hash map update on the right. Try inserting the same key twice to see the pointer update. Click "Compact" to merge duplicate entries.

Practical Considerations: Crash Recovery, Deletion, Concurrency

Several engineering details make hash indexes production-ready:

Crash recovery. If the process crashes, the in-memory hash map is lost. You must rebuild it by scanning the entire data file on startup, which is slow for large files. Bitcask speeds this up by storing a "hint file" alongside each segment — a stripped-down version of the segment containing only keys and offsets (not values). The hint file is much smaller and can rebuild the hash map quickly.

Deletion. You cannot remove a record from an append-only file. Instead, append a special tombstone record (a marker that says "this key is deleted"). During compaction, the tombstone causes the compaction process to discard all prior values for that key. The key is removed from the hash map immediately.

Partially written records. The database might crash mid-write, leaving a corrupted partial record at the end of the file. Bitcask includes a CRC checksum with each record so that damaged records can be detected and discarded on recovery.

Concurrency. Since the file is append-only, writes are strictly sequential — only one writer thread. But multiple reader threads can read concurrently without locks, because the data file segments are immutable once written (only the active segment is being appended to, and the hash map protects reads from seeing partial writes via the pointer update being atomic).

python
# Tombstone pattern for deletions
TOMBSTONE = "__DELETED__"

def delete(db, key):
    """Mark a key as deleted. Compaction removes it later."""
    db.set(key, TOMBSTONE)  # append tombstone to log
    del db.index[key]         # remove from in-memory hash map

def compact(old_segment, new_segment):
    """Remove tombstoned and duplicate keys."""
    seen = {}
    for key, value in read_segment(old_segment):
        if value == TOMBSTONE:
            seen.pop(key, None)  # remove if present
        else:
            seen[key] = value     # keep latest value
    for key, value in seen.items():
        write_to_segment(new_segment, key, value)

Limitations of Hash Indexes

Hash indexes are fast and simple, but they have two critical limitations:

1. All keys must fit in RAM. The hash map is entirely in memory. If you have a billion unique keys, each requiring ~64 bytes for the key plus 8 bytes for the offset, that is 72 GB of RAM just for the index. This is workable for some use cases (Bitcask was designed for relatively few keys with frequently updated values, like URL visit counters) but not for general-purpose databases.

2. Range queries are terrible. Want to find all keys between "user:1000" and "user:2000"? A hash map cannot help you. You would have to scan every key in the map and check if it falls in the range. There is no ordering. This is O(n) for range queries regardless of the result set size.

Worked Example: Memory Budget for Hash Index

Let us calculate exactly how much RAM a hash index needs for a realistic workload:

Implementation Detail: File Format

A production Bitcask-style log format is more structured than our toy "key,value\n" approach. Each record includes a header with metadata:

python
import struct, zlib, time

# On-disk record format (Bitcask-style):
# ┌──────────┬───────────┬─────────┬──────────┬───────┬────────┐
# │ CRC (4B) │ tstamp(4B)│ ksz(2B) │ vsz (4B) │ key   │ value  │
# └──────────┴───────────┴─────────┴──────────┴───────┴────────┘

HEADER_FMT = "!IIhI"  # CRC, timestamp, key_size, value_size
HEADER_SIZE = struct.calcsize(HEADER_FMT)  # = 14 bytes

def encode_record(key, value):
    """Encode a key-value pair into the on-disk format."""
    k = key.encode() if isinstance(key, str) else key
    v = value.encode() if isinstance(value, str) else value
    ts = int(time.time())
    payload = struct.pack(HEADER_FMT[1:], ts, len(k), len(v)) + k + v
    crc = zlib.crc32(payload) & 0xFFFFFFFF
    return struct.pack("!I", crc) + payload

def decode_record(data, offset):
    """Decode a record starting at the given offset."""
    crc, ts, ksz, vsz = struct.unpack(HEADER_FMT, data[offset:offset+HEADER_SIZE])
    k = data[offset+HEADER_SIZE : offset+HEADER_SIZE+ksz]
    v = data[offset+HEADER_SIZE+ksz : offset+HEADER_SIZE+ksz+vsz]
    # Verify CRC to detect corruption
    payload = data[offset+4 : offset+HEADER_SIZE+ksz+vsz]
    assert zlib.crc32(payload) & 0xFFFFFFFF == crc, "Corrupted record!"
    return k.decode(), v.decode(), HEADER_SIZE + ksz + vsz

Segment Strategy: How Bitcask Manages Disk Space

In a real Bitcask deployment, the append-only log is divided into segments. When a segment reaches a size threshold (e.g., 1 GB), it is closed (becomes immutable) and a new segment is opened for writes. Here is the full lifecycle:

The merge process is crucial because without it, disk usage grows without bound. Even if you only have 1 million unique keys, writing each key 1000 times creates 1 billion records across many segments. Compaction reduces this back to 1 million records.

Chapter 2: SSTables & LSM-Trees

What if we take the append-only log from Chapter 1 but add one constraint: the keys in each segment file must be sorted? This seemingly simple change — called a Sorted String Table (SSTable) — gives us three enormous advantages over the hash index approach.

Why Sorted Keys Change Everything

Advantage 1: Efficient merging. When you need to compact multiple segment files into one, you can merge them like merge sort — read from all input segments simultaneously, always picking the lowest key. If the same key appears in multiple segments, keep only the value from the most recent segment. This runs in O(n) time and O(1) memory regardless of file sizes, because each segment is already sorted.

Advantage 2: Sparse index. You no longer need every key in the in-memory index. If you know that key "handbag" is at offset 12000 and key "handsaw" is at offset 13200, then "handler" must be somewhere between those offsets. You jump to offset 12000 and scan forward until you find it. With one index entry per few kilobytes of data, you can cover terabytes of on-disk data with a tiny in-memory index.

Advantage 3: Range queries. Because keys are sorted, finding all keys between "user:1000" and "user:2000" means seeking to the first key ≥ "user:1000" and scanning forward until you pass "user:2000". This is efficient — you only read the data you need.

But How Do You Sort an Append-Only Log?

You cannot sort a file as you append to it — that would require random I/O, which defeats the whole purpose. The trick is to separate the write path from the on-disk format:

This three-level architecture is called a Log-Structured Merge-Tree (LSM-Tree). It was originally described by Patrick O'Neil in 1996 and is the engine behind LevelDB, RocksDB, Cassandra, HBase, and many modern databases.

The Read Path: Where Is My Key?

Reading from an LSM-tree requires checking multiple places, in order:

The worst case is looking up a key that does not exist. You must check the memtable and every SSTable on disk before you can conclude it is not there. This is where Bloom filters save the day.

Bloom Filters: Avoiding Unnecessary Disk Reads

A Bloom filter is a memory-efficient probabilistic data structure that can tell you "this key is definitely not in this SSTable" or "this key might be in this SSTable." It never gives false negatives, but it can give false positives (at a controllable rate, typically 1-2%).

How it works: a Bloom filter is a bit array of m bits, initially all zeros. To add a key, hash it with k different hash functions, each producing a position in the bit array. Set those k bits to 1. To check if a key exists, hash it with the same k functions and check if all k bits are set. If any bit is 0, the key is definitely not in the set. If all are 1, the key probably is (but might be a false positive due to hash collisions).

Each SSTable has its own Bloom filter, stored alongside it. Before seeking into an SSTable file, you check its Bloom filter. If the filter says "no," you skip that file entirely. This turns most non-existent-key lookups from O(levels × log n) into O(levels), checking only a few bytes of Bloom filter per level.

Worked Example: Complete Read and Write Paths

Let us trace a write and a read through a realistic LSM-tree with 3 levels:

Handling Deletes: Tombstones

You cannot simply remove a key from the memtable and call it deleted. The key might still exist in older SSTables on disk. If someone reads the key, they would find the old value in an SSTable and think it still exists.

The solution: write a special marker called a tombstone. The tombstone is a record that says "this key has been deleted." When the read path encounters a tombstone (in the memtable or any SSTable), it returns "key not found" without checking deeper levels. During compaction, tombstones cancel out the key-value pairs they cover, and both are discarded once the tombstone reaches the deepest level.

Tombstones are one of the trickiest parts of LSM-tree engineering. If you delete many keys but compaction has not run yet, the tombstones pile up and make reads slower (you still have to check all the SSTables, only to find tombstones). This is why some databases (like Cassandra) let you set a gc_grace_seconds parameter that controls how long tombstones linger before compaction is forced.

Compaction Strategies

There are two main approaches to compaction, and they produce very different behaviors:

Size-Tiered Compaction: Visual Walkthrough

In size-tiered compaction, SSTables are grouped by size. When you accumulate enough similarly-sized SSTables (typically 4), they are merged into one larger SSTable. Think of it like a tournament bracket — small files merge into medium files, medium into large.

Leveled Compaction: Visual Walkthrough

In leveled compaction (used by LevelDB and RocksDB), SSTables are organized into levels. Each level is 10x the total size of the previous. Within a level (except L0), SSTable key ranges do not overlap — this is the key invariant that makes reads fast.

LSM-Tree Visualization

The simulation below shows an LSM-tree in action. Writes go to the memtable. When it fills, it flushes to Level 0. Background compaction merges L0 into L1. Watch the data flow through levels.

Worked Example: Write Amplification

Let us calculate the write amplification of leveled compaction with a size ratio of 10:

LSM-Tree Tuning: The Knobs That Matter

Production LSM-tree engines like RocksDB expose dozens of tuning parameters. The ones that matter most:

Chapter 3: B-Trees

While LSM-trees are the new hotness, the B-tree has been the dominant index structure since 1970. Virtually every relational database — PostgreSQL, MySQL, Oracle, SQL Server — uses B-trees as their primary index structure. If you have used a database, you have used a B-tree.

Like SSTables, B-trees keep keys sorted, which enables efficient range queries. But the design philosophy is completely different. Where LSM-trees buffer writes in memory and periodically flush sorted files, B-trees update data in place on disk.

The Structure: Pages and Pointers

A B-tree organizes data into fixed-size pages (also called blocks), typically 4 KB — the same size as a disk sector or virtual memory page. This is not a coincidence. It means reading one B-tree node costs exactly one disk I/O.

There are two types of pages:

Internal pages contain keys and pointers to child pages. If an internal page contains keys [10, 20, 30], it has four child pointers: one for keys < 10, one for keys 10-19, one for keys 20-29, and one for keys ≥ 30. The number of children per page is called the branching factor.

Leaf pages contain the actual key-value pairs (or keys plus pointers to the rows in a separate heap file).

Deriving the Depth: Why B-Trees Are So Shallow

The magic of B-trees is in the branching factor. A typical 4 KB page can hold hundreds of key-pointer pairs. Let us work through the math:

Lookups: Following the Pointers

To find a key in a B-tree, start at the root page. Binary-search within the page to find the right child pointer. Follow it. Repeat until you reach a leaf. Each level costs one disk read (or one cache hit if the page is already in the buffer pool).

Insertions: Splitting Pages

To insert a new key, follow the lookup path to the correct leaf page. If the leaf has room, insert the key in sorted order within the page. If the leaf is full, split it into two half-full pages and promote the middle key to the parent. If the parent is also full, split it too. This can cascade up to the root, which is the only way a B-tree grows taller.

Let us trace through a page split step by step:

The average fill factor of a B-tree after many random insertions is about 69% (ln 2). This means roughly one-third of the space in each page is wasted. Some databases let you set a lower initial fill factor (e.g., PostgreSQL's fillfactor parameter) to leave room for future updates without splitting, at the cost of a deeper tree.

The Write-Ahead Log (WAL)

B-trees update pages in place. If the system crashes mid-write (say, while splitting a page), the tree could be left in a corrupted state — one page has been written but the parent pointer has not been updated yet, leaving an orphan page.

The solution: before modifying any page, write the intended change to an append-only write-ahead log (WAL, also called redo log). If the system crashes, replay the WAL to bring the tree back to a consistent state. This means every B-tree write actually hits the disk twice: once for the WAL, once for the actual page update.

Interactive B-Tree

The simulation below lets you insert keys into a B-tree with a small branching factor (4, so you can see splits happen). Watch pages fill and split as you add keys.

Concurrency: Latches, Not Locks

When multiple threads read and write the B-tree simultaneously, you need concurrency control. B-trees use latches (lightweight mutexes) on individual pages, not full database-level locks. A common strategy: acquire a read latch on the root, descend to the child, acquire a latch on the child, release the parent's latch. This "latch crabbing" protocol minimizes contention.

An alternative approach used by some modern databases (LMDB, BoltDB) is copy-on-write: instead of modifying a page in place, create a new version of the page and atomically update the parent pointer. This eliminates the need for latches and the WAL, but uses more disk space.

B-Tree vs B+ Tree

Almost all databases actually use a B+ tree, not a classic B-tree. The difference:

The B+ tree's leaf-linked-list makes range queries extremely efficient: find the starting key (O(log n) tree traversal), then follow the leaf pointers sequentially. No need to go back up and down the tree. This is why PostgreSQL, MySQL, and SQLite all use B+ trees.

B-Tree Optimizations in Practice

Production B-tree implementations use several tricks beyond the basic algorithm:

Prefix compression. Keys within a page often share a common prefix (e.g., "user:1001", "user:1002", "user:1003"). Store the common prefix once and only the differing suffixes per key. This increases the branching factor — more keys per page = shallower tree.

Bulk loading. Building a B-tree by inserting keys one at a time is O(n log n) and creates a tree with ~69% fill factor. Bulk loading sorts all keys first, then builds the tree bottom-up, filling each page to 100%. This creates a more compact tree and is much faster. PostgreSQL's CREATE INDEX CONCURRENTLY uses this approach.

Fractal trees. A hybrid of B-trees and LSM-trees. Like a B-tree, but each internal node has a small buffer for pending insertions. When the buffer fills, the insertions are pushed down to children in a batch. This gives near-LSM write performance with B-tree read performance. TokuDB (now part of Percona) used fractal trees.

Buffer pool management. The database maintains a fixed-size buffer pool of B-tree pages in RAM. Popular pages (the root, heavily-accessed leaves) stay resident. Eviction uses LRU or clock algorithms. PostgreSQL's shared_buffers parameter controls this — typically set to 25% of available RAM.

B-Tree Deletion: Merging Pages

Deletion in B-trees is the inverse of insertion. Remove the key from the leaf page. If the leaf now has fewer keys than the minimum (typically half the maximum), it is underful. The tree must rebalance by either borrowing a key from a sibling page (called rotation) or merging the underful page with a sibling (the inverse of a split). Merged pages propagate up the tree, just like splits.

In practice, many databases do not merge pages immediately on deletion. PostgreSQL marks deleted entries as "dead" and relies on VACUUM to reclaim space later. This is simpler and avoids the complexity of page merges, but it means deleted rows leave behind dead space (called bloat). If a table has 50% bloat, it is taking twice the disk space it needs, and scans read twice as many pages.

B-Tree Performance Characteristics

Let us derive the exact I/O cost for B-tree operations:

Chapter 4: B-Trees vs LSM-Trees

This is THE comparison question in systems design interviews. "When would you use an LSM-tree versus a B-tree?" If you can answer this fluently, you demonstrate a deep understanding of storage engine trade-offs.

The Write Path: Sequential vs Random

LSM-trees batch writes into memory (the memtable) and flush them as large sequential writes. B-trees perform random I/O — seeking to the correct page and updating it in place. On any storage medium (HDD, SSD, or cloud block storage), sequential I/O is faster than random I/O:

On spinning disks, the advantage is massive (150x). On SSDs, it is smaller but still significant (5x). This is why LSM-trees can sustain higher write throughput despite higher write amplification.

Write Amplification: The Detailed Comparison

The Read Path: One Seek vs Many Checks

B-trees have a clear read advantage. A point lookup touches at most depth pages (typically 2-3 disk reads, often 1 due to caching). An LSM-tree must check the memtable, then potentially every level of SSTables — even with Bloom filters, this can mean 2-5 disk reads for a cold key.

Latency predictability is another B-tree strength. B-tree read latency is consistent: always depth disk reads. LSM-tree read latency varies — it might be in the memtable (instant) or buried in the oldest SSTable (multiple disk reads). If you need predictable p99 latency (e.g., for a financial trading system), B-trees win.

The Compaction Tax

LSM-trees must perform background compaction to merge SSTables. This compaction competes with foreground operations for disk bandwidth and CPU. If the write rate exceeds the compaction throughput, uncompacted SSTables pile up, reads slow down (more files to check), and eventually the database must throttle writes. This is called compaction debt.

B-trees have no compaction. Their write overhead is paid immediately (WAL + page write), not deferred. This makes their performance more predictable under sustained load.

SSD Lifetime: The Hidden Cost of Write Amplification

SSDs have a finite number of write cycles per cell (typically 1,000-10,000 for TLC NAND). Write amplification directly reduces SSD lifetime. If your LSM-tree has 30x write amplification and you are writing 1 GB/s of user data, the SSD sees 30 GB/s of actual writes. An SSD rated for 1 petabyte of total writes would last:

Transaction Support

B-trees naturally support transactions because each key lives in exactly one place (one page). You can lock individual keys, implement MVCC by storing multiple versions in the page, and ensure serializability with page-level latches.

LSM-trees are harder to transact on. A key might exist in the memtable AND in multiple SSTables simultaneously (with different versions). Implementing snapshot isolation requires careful coordination between the memtable and all SSTable levels. This is doable (RocksDB supports transactions via a pessimistic or optimistic concurrency control layer on top of the LSM), but it adds complexity and overhead that B-trees handle naturally.

Compression: LSM-Trees Win Decisively

LSM-trees achieve much better compression than B-trees, for two reasons:

1. No fragmentation. B-tree pages are rarely 100% full. After many random insertions and deletions, the average page fill factor is about 69%. That means 31% of your on-disk index is wasted space. LSM-tree SSTables are written sequentially and compacted, so they have no internal fragmentation.

2. Compression-friendly layout. SSTable files contain sorted keys, which means adjacent entries often share prefixes and have similar values. This is ideal for dictionary encoding, prefix compression, and LZ4/Snappy/Zstd compression. B-tree pages are too small (4 KB) for compression to be as effective, and compressing/decompressing individual pages adds latency to every read.

The Emerging Middle Ground: Bw-Trees and Fractal Trees

Some modern storage engines try to get the best of both worlds:

Bw-Tree (Buzzword-Tree), developed by Microsoft Research, is a lock-free B-tree that uses a mapping table to indirect all page references. Updates create "delta records" that chain to the base page (like an LSM within each page). Periodic consolidation merges deltas into the base page. This gives B-tree read performance with near-LSM write performance. Used in SQL Server's Hekaton in-memory engine.

Fractal Tree (TokuDB, now Percona): each internal B-tree node has an attached write buffer. Inserts go into the buffer instead of being pushed all the way down to a leaf. When the buffer fills, its contents are flushed to children in a batch. This converts random writes into sequential batch writes at each level — effectively an LSM approach applied within a B-tree structure. Write amplification is O(log_B(N) / B) instead of O(B × log_B(N)) for standard B-tree.

Write Stalls: The LSM-Tree Achilles Heel

The most feared production issue with LSM-trees is the write stall. Here is how it happens:

The mitigation strategy has three layers:

1. Prevent: Size your compaction throughput for 2x your peak write rate. More compaction threads, faster disks (NVMe over SATA), larger memtable (fewer L0 flushes).

2. Soften: Use rate limiting (delayed_write_rate) to gradually slow writers before a hard stall. Writers get slower instead of completely blocked.

3. Recover: If a stall happens, temporarily reduce write rate (back-pressure from the database to the application), let compaction catch up, then resume normal operation.

Real Benchmark Numbers

Theoretical analysis is useful, but let us look at real benchmark data. The following numbers come from published benchmarks comparing RocksDB (LSM) vs InnoDB (B-tree) on the same hardware:

Notice the pattern: RocksDB dominates writes (especially p99 write latency — 17x better) and disk space efficiency. InnoDB dominates reads (1.6x better throughput, 4x better p99 read latency). The LSM compaction spikes are what cause the higher read p99.

Side-by-Side Comparison

The Decision Framework

Real-World Decision: How Companies Choose

Here is how some well-known companies picked their storage engines, and why:

Chapter 5: Other Indexing Structures

So far we have talked about indexing a single key. But real databases need much more: secondary indexes (looking up by a non-primary column), multi-column indexes (querying by two fields at once), full-text search, and even geospatial queries. Each requires a different indexing approach.

Secondary Indexes

A primary index maps a unique key (like user_id) to the row's location. A secondary index maps a non-unique column (like city) to the set of rows that match. The B-tree or LSM-tree structure is the same — the difference is that secondary index entries can point to multiple rows.

There are two ways to handle this:

Heap file + pointers. The table data lives in a separate heap file in insertion order. Both the primary index and all secondary indexes contain pointers (row IDs) into this heap file. A secondary index lookup returns a list of row IDs, and you chase each pointer to the heap file to retrieve the actual row data. This pointer-chasing is called a non-clustered index scan.

Clustered index. Store the actual row data directly inside the primary index's leaf pages, sorted by the primary key. Secondary indexes still use pointers, but now they point into the primary index rather than a heap file. This is how InnoDB (MySQL) works — the primary key IS the table, and secondary indexes point to primary key values.

Multi-Column and Covering Indexes

A concatenated index combines multiple columns into a single key. An index on (last_name, first_name) stores keys like "Smith|Alice". This supports queries that filter by last_name alone or by (last_name AND first_name), but NOT by first_name alone — the index is sorted by last_name first.

A covering index (or index-only scan) includes additional column values directly in the index entries, so the database can answer a query without touching the heap file at all. For example, an index on (city) that also INCLUDEs (population) can answer "SELECT population FROM cities WHERE city = 'Tokyo'" entirely from the index.

Covering Indexes: Avoiding the Second Lookup

A covering index is one of the most powerful optimization techniques in database tuning. The idea: include the values the query needs directly in the index, so the database never has to visit the heap file or primary index at all.

python
# Standard secondary index on email (PostgreSQL):
# CREATE INDEX idx_email ON users(email);
# SELECT name FROM users WHERE email = 'alice@example.com';
# → index lookup (email → ctid) → heap fetch (ctid → row) → return name
# TWO lookups!

# Covering index (INCLUDE the columns we need):
# CREATE INDEX idx_email_covering ON users(email) INCLUDE (name);
# SELECT name FROM users WHERE email = 'alice@example.com';
# → index lookup (email → name) → return name
# ONE lookup! The "name" value is stored in the index leaf page.

# EXPLAIN output would show "Index Only Scan" instead of "Index Scan"
# This can be 2-5x faster for queries that hit many rows.

Multi-Dimensional Indexes

How do you find "all restaurants within 2 km of my location"? This requires searching on two dimensions (latitude and longitude) simultaneously. A standard B-tree can sort by one dimension, but not two.

R-trees solve this by grouping nearby objects into rectangular bounding boxes, organized hierarchically. PostGIS (the geospatial extension for PostgreSQL) uses R-trees (via GiST indexes) for spatial queries.

Another approach: space-filling curves like the Z-order curve or Hilbert curve map 2D coordinates to a 1D value, preserving spatial locality. Then you can use a standard B-tree on the 1D value. This is how DynamoDB's geospatial indexes work.

Full-Text Search and Fuzzy Indexes

Full-text search indexes need to handle things that B-trees and LSM-trees cannot: word stemming (running, runs, ran → run), synonym matching, relevance ranking, and fuzzy matching (tolerate typos). These use inverted indexes — a map from each word to the list of document IDs containing that word. Lucene (the engine behind Elasticsearch and Solr) uses an SSTable-like structure for its term dictionary and posting lists.

For fuzzy matching (finding "restaurant" when the user typed "resturant"), Lucene uses a finite automaton built from a Levenshtein distance threshold. The automaton can efficiently traverse the sorted term dictionary and find all terms within edit distance 1 or 2 of the query term. This is how Elasticsearch's fuzzy queries work.

R-Trees for Geospatial Queries

A standard B-tree can efficiently search one dimension. But "find all restaurants within 2 km" requires searching two dimensions (latitude and longitude) simultaneously. An R-tree extends the B-tree idea to multiple dimensions using minimum bounding rectangles (MBRs).

PostGIS uses GiST indexes (Generalized Search Trees), which are a generalization of R-trees that support any decomposable search predicate. This is how Uber finds nearby drivers, how Airbnb searches for listings in a map viewport, and how DoorDash finds restaurants near you.

Index Selection: The DBA's Art

Choosing which indexes to create is one of the most impactful decisions a database administrator makes. Too few indexes → slow reads. Too many indexes → slow writes and wasted disk space. The decision framework:

python
# PostgreSQL: check if your indexes are being used
# This query shows which indexes are never used (candidates for removal)

query = """
SELECT
    schemaname, tablename, indexname,
    idx_scan as times_used,
    pg_size_pretty(pg_relation_size(indexrelid)) as index_size
FROM pg_stat_user_indexes
WHERE idx_scan = 0  -- NEVER used!
ORDER BY pg_relation_size(indexrelid) DESC;
"""

# Each unused index costs:
# 1. Disk space (visible in index_size above)
# 2. Write overhead (every INSERT/UPDATE/DELETE updates this index)
# 3. VACUUM overhead (must clean dead entries in index too)
# Drop unused indexes for immediate write performance improvement.

Concatenated Index Deep Dive

The order of columns in a concatenated index matters enormously. Consider an index on (last_name, first_name, age):

Secondary Index Canvas

Chapter 6: In-Memory Databases

We have spent five chapters agonizing over disk I/O. Pages, segments, sequential vs random writes. What if we just... keep everything in RAM?

RAM prices have fallen dramatically. In 2024, a cloud instance with 256 GB of RAM costs roughly $3/hour. Many datasets fit comfortably in that budget. This opens the door to in-memory databases — systems that keep the entire dataset in RAM, with disk used only for durability (crash recovery).

How In-Memory Databases Achieve Durability

Keeping data only in RAM would mean losing everything on a crash or power failure. In-memory databases solve this with several strategies:

Write-ahead log on disk. Every write is appended to a persistent log on disk before being applied in memory. On crash, replay the log. This is how Redis (with AOF mode) and VoltDB work. The log is append-only and sequential, so it does not bottleneck writes.

Periodic snapshots. Serialize the entire in-memory state to disk at intervals (e.g., every 5 minutes). On crash, restore from the latest snapshot, then replay the WAL entries since the snapshot. Redis RDB mode does this.

Replication. Keep copies on other machines. If one machine dies, another has the data. This is how Memcached clusters survive node failures (though Memcached itself has no persistence — it relies on the application to re-populate from the primary database).

Redis Data Structures: Why In-Memory Matters

To make the "data structures" advantage concrete, here are operations that Redis handles in microseconds but are nightmarish on disk:

The ZRANK operation is particularly illustrative. In Redis, a sorted set is implemented as a skip list with augmented size counts at each level. Finding the rank of an element means traversing the skip list and summing the span counts — O(log n). In PostgreSQL, finding the rank requires counting all rows with a higher score, which is a full index scan — O(n). For a 10-million-entry leaderboard, that is the difference between 5 microseconds and 50 milliseconds — a 10,000x gap.

Anti-Caching: The Best of Both Worlds

Anti-caching (used by VoltDB, MemSQL/SingleStore) flips the traditional approach. Instead of caching hot data in memory from a disk-based store, you keep everything in memory and evict cold data to disk when RAM pressure increases. It is like a user-space page cache — the database knows which tuples are cold (based on access patterns), evicts them efficiently, and fetches them back on demand.

This gives you the programming model of an in-memory database (all data structures, no page management) with the capacity of a disk-based system.

NVM and the Future of Memory

Non-Volatile Memory (NVM), most notably Intel Optane Persistent Memory (now discontinued, but the concept lives on), sits between DRAM and SSD in both speed and cost. It offers byte-addressable persistent storage with latency around 300ns — 3x slower than DRAM but 300x faster than SSD. This blurs the line between in-memory and on-disk databases.

With NVM, a database can keep its data structures (B-trees, hash maps) directly in persistent memory. No WAL needed — every write is instantly durable. No buffer pool needed — the data is already in addressable memory. No crash recovery needed — the data survives power loss. This eliminates the three biggest sources of complexity in storage engine design.

However, NVM introduces its own challenges: cache-line-level atomicity (writes smaller than a cache line are atomic, but larger writes are not), memory ordering (CPU may reorder writes, requiring explicit flush instructions), and wear leveling (like SSD, NVM cells have finite write endurance). These require new data structure designs — "persistent data structures" that are correct even if the system crashes mid-operation.

Cost Analysis: When Does In-Memory Make Sense?

In-Memory Database Landscape

Redis vs Memcached: When to Use Which

Both are in-memory, but they serve different use cases:

Redis Persistence Deep Dive

Redis offers two persistence mechanisms that can be used independently or together:

RDB (Redis Database) snapshots. Periodically fork the process and dump the entire dataset to a point-in-time snapshot file. The fork uses copy-on-write (COW), so the parent continues serving requests while the child writes to disk. Configurable: "save after 900 seconds if at least 1 key changed." Recovery: load the snapshot on startup. Data loss: up to one snapshot interval (e.g., 15 minutes of data).

AOF (Append Only File). Log every write operation to an append-only file on disk. Three durability levels: (1) always — fsync every write (slowest, no data loss), (2) everysec — fsync every second (good compromise, up to 1 second of data loss), (3) no — let the OS decide when to flush (fastest, up to 30 seconds of data loss). The AOF file is periodically rewritten (compacted) in the background to prevent unbounded growth.

Chapter 7: OLTP vs OLAP

So far we have been thinking about databases that serve user-facing applications: a web server reads a user record, updates a shopping cart, inserts an order. These queries touch a small number of rows, but there are thousands of them per second. This is Online Transaction Processing (OLTP).

But there is a second class of database usage that looks completely different. A business analyst wants to know: "What was the total revenue by product category in Q3 across all stores?" This query must scan millions or billions of rows, aggregate values, and return a single summary. This is Online Analytical Processing (OLAP).

Two Completely Different Access Patterns

The Data Warehouse: ETL from OLTP

Most organizations do not run analytics directly on their OLTP databases. Instead, they Extract, Transform, Load (ETL) data from multiple OLTP systems into a dedicated data warehouse optimized for analytics.

Star and Snowflake Schemas

Data warehouses typically organize data into a star schema. At the center is a fact table — a very large table where each row represents an event (a sale, a click, a page view). Each fact row has foreign keys pointing to smaller dimension tables (product, store, customer, date).

The star schema gets its name from the visual layout: the fact table in the center with dimension tables radiating outward like points of a star.

A snowflake schema is a variation where dimension tables are further normalized (e.g., the product dimension has a separate category sub-dimension). This saves space but makes queries more complex with additional joins.

Why Not Just Use the Same Database?

A common question: "Why can't the analyst just query the OLTP database directly?" Three reasons:

1. Performance interference. An OLAP scan that reads millions of rows competes with OLTP queries for buffer pool space, disk I/O, and CPU. A single dashboard refresh could evict thousands of frequently-accessed pages from the buffer pool, causing every user-facing query to hit disk instead of cache. Your 2ms point lookups suddenly become 20ms.

2. Different schemas. OLTP tables are normalized (third normal form) to minimize update anomalies. Analytics work better on denormalized star schemas where every fact row contains or points to all the context you need. ETL performs this denormalization during the transform step.

3. Different storage formats. OLTP uses row-oriented storage (fast for inserting and reading individual rows). OLAP is 10-100x faster with column-oriented storage (Chapter 8). You cannot get both benefits from a single storage format.

python
# A simplified ETL pipeline for a data warehouse

# 1. EXTRACT: Read from OLTP sources
users   = pg_conn.execute("SELECT * FROM users WHERE updated_at > %s", last_etl)
orders  = mysql_conn.execute("SELECT * FROM orders WHERE created_at > %s", last_etl)
events  = mongo_conn.find({"ts": {"$gt": last_etl}})

# 2. TRANSFORM: Clean, join, denormalize into star schema
fact_rows = []
for order in orders:
    user = users_by_id[order.user_id]
    fact_rows.append({
        "order_id": order.id,
        "date_key": to_date_key(order.created_at),
        "user_key": user.id,
        "product_key": order.product_id,
        "revenue": order.total,
        "quantity": order.qty,
        "user_country": user.country,  # denormalized from user dim
    })

# 3. LOAD: Bulk insert into the data warehouse
warehouse.bulk_insert("sales_facts", fact_rows)

ETL vs Change Data Capture (CDC)

Traditional ETL runs on a schedule — hourly or daily. This means the data warehouse is always at least one ETL cycle behind the OLTP sources. For many analytics use cases, this is fine ("what were last month's sales?" does not need real-time data).

But some use cases need fresher data ("how many users signed up in the last 5 minutes?"). Change Data Capture (CDC) replaces batch ETL with a continuous stream of changes. The OLTP database's WAL (write-ahead log) is read in real time, and each change (insert, update, delete) is streamed to the data warehouse within seconds.

OLTP vs OLAP Canvas

Fact Table Sizing: How Big Do They Get?

Fact tables in a data warehouse can be enormous. Let us size one for a mid-size e-commerce company:

The HTAP Trend

The newest trend is HTAP (Hybrid Transactional/Analytical Processing): databases that handle both OLTP and OLAP in a single system. The idea: maintain a row-oriented store for transactions and a column-oriented store for analytics, with automatic real-time synchronization between them.

TiDB, for example, has two storage engines: TiKV (a distributed key-value store based on RocksDB/LSM for OLTP) and TiFlash (a columnar store for OLAP). When you write to TiKV, the data is asynchronously replicated to TiFlash in columnar format. The query optimizer routes each query to the appropriate engine — point lookups go to TiKV, aggregation queries go to TiFlash.

This is the theoretical ideal: one database, no ETL, real-time analytics. In practice, HTAP databases are still maturing, and most large organizations still separate OLTP and OLAP into different systems for operational simplicity and failure isolation.

Chapter 8: Column-Oriented Storage

This is the showcase chapter — the single most important idea for OLAP performance. Once you understand column-oriented storage, you understand why data warehouses are orders of magnitude faster than row-oriented databases for analytics.

The Problem with Row-Oriented Storage

In a row-oriented database (PostgreSQL, MySQL), each row is stored contiguously on disk. A row for a sales event might look like this in storage:

Now run the query: SELECT SUM(revenue) FROM sales WHERE date BETWEEN '2024-01-01' AND '2024-03-31'.

This query needs only two columns: date and revenue. But in a row-oriented layout, the database must read ALL seven columns for every row, because each row is stored as a single unit. If each row is 100 bytes and you have 100 million rows, you read 10 GB of data to access 16 bytes per row (8-byte date + 8-byte revenue) — you are reading 6x more data than you need.

Column-Oriented Layout: Store Each Column Separately

In a column-oriented (columnar) database, all values from one column are stored contiguously, separate from other columns:

Column Compression

Storing values of the same type contiguously also enables dramatically better compression. A column of dates contains similar values (most dates cluster in recent months). A column of product categories might have only 50 distinct values across 100 million rows.

Bitmap encoding. For a column with n distinct values, create n bitmaps — one per distinct value. Each bitmap has one bit per row (1 if that row has this value, 0 otherwise). For a "country" column with 200 countries across 100M rows, each bitmap is 100M bits = 12.5 MB, and the total is 200 × 12.5 MB = 2.5 GB. But most bitmaps are very sparse (mostly zeros), so they compress extremely well with run-length encoding.

With run-length encoding, a bitmap for "NYC" across 100 million rows where 30% are NYC compresses from 12.5 MB to about 200 KB. The compression ratio for the entire column can be 10-100x.

Interactive: Row Store vs Column Store

The simulation below shows the same table stored in row-oriented and column-oriented format. Select columns for your query and see how much data each format must read.

Dictionary Encoding and Delta Encoding

Beyond bitmap encoding, column stores use two other powerful compression techniques:

Dictionary encoding. Replace each distinct string value with a small integer. Store a separate dictionary mapping integers to strings. If a "product_name" column has 10,000 distinct products across 100 million rows, each row stores a 2-byte integer instead of a 20-byte string — 10x compression on that column alone.

Delta encoding. For sorted columns (especially timestamps), store the difference between consecutive values instead of the absolute values. If timestamps are in milliseconds and rows are 100ms apart, each delta is small and compresses well:

CPU-Friendly Processing: Vectorized Execution

Column stores unlock a performance trick that row stores cannot use: vectorized execution. Because all values in a column are the same type, stored contiguously in memory, you can process them in tight loops that exploit CPU cache lines and SIMD instructions.

A modern CPU can compare 16 integers against a constant in a single SIMD instruction (using 128-bit SSE or 256-bit AVX). Processing a column of dictionary-encoded integers with SIMD is 10-20x faster than the row-by-row processing that row stores must use.

Sort Order and Multiple Sort Orders

Within each column file, the rows must be stored in the same order across all columns (so that row 42 in the date file corresponds to row 42 in the revenue file). You can choose what order to sort the rows in.

Sorting by date (the most common filter in analytics) means the date column compresses beautifully (many consecutive identical dates → long run-length encoding runs), and date-range queries scan a contiguous region.

Some databases (like Vertica, now part of OpenText) maintain multiple sort orders — several copies of the data, each sorted differently. This is like having multiple clustered indexes. It uses more space but means the query optimizer can pick the sort order that best matches each query.

Materialized Views and Data Cubes

For frequently-run aggregation queries, you can pre-compute the result and store it as a materialized view. A data cube (also called an OLAP cube) is a specialized materialized view that pre-computes aggregates across every combination of dimensions. For example, a cube over (date, product, store) pre-computes the SUM of revenue for every (date, product, store) combination.

The downside: materialized views and cubes must be updated when the underlying data changes, and they cannot answer queries that do not match the pre-computed dimensions. They are a caching optimization, not a general solution.

Real-World Column Store: DuckDB

DuckDB is worth special attention because it demonstrates the power of column-oriented processing in an embedded context — no server, no network, just a library linked into your application (like SQLite, but columnar).

python
import duckdb

# DuckDB can directly query Parquet files (columnar format) on disk
# No need to load into a database first!

result = duckdb.sql("""
    SELECT
        product_category,
        SUM(revenue) as total_revenue,
        COUNT(*) as num_sales,
        AVG(revenue) as avg_sale
    FROM read_parquet('sales_2024_*.parquet')
    WHERE date BETWEEN '2024-01-01' AND '2024-03-31'
    GROUP BY product_category
    ORDER BY total_revenue DESC
    LIMIT 10
""")

# This query over 100M rows in Parquet files completes in ~2 seconds
# because DuckDB:
# 1. Only reads the 4 columns needed (date, product_category, revenue)
# 2. Uses vectorized execution (processes 2048 values at a time)
# 3. Pushes the WHERE filter down to the Parquet reader (skip row groups)
# 4. Runs on all CPU cores in parallel

# The same query on PostgreSQL (row-oriented) would read ALL columns
# and take 20-60 seconds. 10-30x slower on the same hardware.

Column Store vs Row Store: When Columns Lose

Column stores are not always better. They lose decisively in these scenarios:

1. Point lookups. Retrieving a single row by primary key requires reading one value from every column file and reassembling the row. If you have 200 columns, that is 200 file seeks. A row store does this in 1 seek. For OLTP-style "get user by ID" queries, row stores are 10-100x faster.

2. Small inserts. Adding one row to a column store means appending to 200 separate column files. A row store appends to one file. This is why column stores use the LSM-buffered write path (batch in memory, flush in bulk).

3. Wide SELECT * queries. If your query needs all columns (like a backup or export), column store must read every column file and reassemble rows. Row store reads the data in its natural format with zero reassembly cost.

4. Narrow tables. If your table has only 3-5 columns, the column store advantage disappears — you are reading most of the data regardless of format. The overhead of maintaining separate column files is not worth it.

The Column Store Write Path

Column-oriented storage is optimized for reads, but writes are tricky. Inserting a single row requires appending a value to every column file — potentially hundreds of files. The solution: use an LSM-tree within each column. Incoming writes go to an in-memory buffer (a row-oriented memtable). When the buffer is full, pivot the rows into columnar format and flush all columns as a batch. Background compaction merges small column segments into larger sorted ones.

This is exactly how Apache Parquet + Delta Lake work, and it is the write engine behind ClickHouse, DuckDB, and Snowflake. The key insight: accept row-oriented writes, batch them, convert to columnar format in bulk. This bridges the gap between the write-friendly row format and the read-friendly columnar format.

python
# Conceptual column store write path
class ColumnStore:
    def __init__(self, columns, flush_threshold=10000):
        self.columns = columns  # list of column names
        self.buffer = []         # row-oriented in-memory buffer
        self.threshold = flush_threshold
        self.segments = []        # list of flushed column segments

    def insert(self, row):
        """Insert a row (dict of column_name → value)."""
        self.buffer.append(row)
        if len(self.buffer) >= self.threshold:
            self._flush()

    def _flush(self):
        """Pivot rows to columns and write to disk."""
        segment = {}
        for col in self.columns:
            segment[col] = [row[col] for row in self.buffer]
        self.segments.append(segment)
        self.buffer = []

    def scan(self, needed_columns, predicate=None):
        """Only read the columns we need — the whole point."""
        results = []
        for seg in self.segments:
            n_rows = len(seg[self.columns[0]])
            for i in range(n_rows):
                row = {c: seg[c][i] for c in needed_columns}
                if predicate is None or predicate(row):
                    results.append(row)
        return results

Parquet File Format: Anatomy of a Column Store on Disk

Understanding the Parquet file format makes column store concepts concrete. A Parquet file is organized into row groups, each containing column chunks, each containing pages:

Predicate pushdown is the key optimization. Each column chunk's metadata includes the minimum and maximum values for that chunk. If your query says WHERE date > '2024-06-01' and a row group's date column has max = '2024-05-31', the entire row group (potentially millions of rows) can be skipped without reading a single byte of data.

Chapter 9: Interview Arsenal

This chapter is your cheat sheet. Everything from Chapters 0-8 condensed into tables, decision frameworks, and ready-to-use answers for system design interviews.

Storage Structure Comparison

System Design Talking Points

"Design a key-value store."

"Design a time-series database."

"Design a data warehouse."

Design Challenge: E-Commerce Product Catalog

Let us work through a real design challenge, the kind you would get in a 45-minute system design interview:

Debug Scenarios

Coding Drills

Drill 1: Simple Hash Index in Python

python
import os

class HashIndex:
    """Bitcask-style hash index: append-only log + in-memory hash map."""

    def __init__(self, path):
        self.path = path
        self.index = {}  # key → byte offset
        self.f = open(path, 'a+b')  # append + read, binary
        self._rebuild_index()

    def _rebuild_index(self):
        """Scan the file to rebuild the in-memory index on startup."""
        self.f.seek(0)
        while True:
            offset = self.f.tell()
            line = self.f.readline()
            if not line:
                break
            key, _ = line.decode().strip().split(',', 1)
            self.index[key] = offset  # last write wins

    def set(self, key, value):
        offset = self.f.seek(0, 2)  # seek to end
        self.f.write(f"{key},{value}\n".encode())
        self.f.flush()
        self.index[key] = offset

    def get(self, key):
        if key not in self.index:
            return None
        self.f.seek(self.index[key])
        line = self.f.readline().decode().strip()
        _, value = line.split(',', 1)
        return value

Drill 2: Simple LSM Memtable + Flush

python
import json, os
from sortedcontainers import SortedDict  # pip install sortedcontainers

class LSMTree:
    """Minimal LSM-tree: memtable + SSTable flush."""

    def __init__(self, directory, memtable_limit=1000):
        self.directory = directory
        self.memtable_limit = memtable_limit
        self.memtable = SortedDict()  # sorted in-memory tree
        self.sstables = []  # list of SSTable file paths, newest first
        os.makedirs(directory, exist_ok=True)

    def put(self, key, value):
        self.memtable[key] = value
        if len(self.memtable) >= self.memtable_limit:
            self._flush()

    def get(self, key):
        # 1. Check memtable first (newest data)
        if key in self.memtable:
            return self.memtable[key]
        # 2. Check SSTables from newest to oldest
        for sst_path in self.sstables:
            with open(sst_path) as f:
                data = json.load(f)  # [{key:..., value:...}, ...]
                # Binary search (data is sorted by key)
                lo, hi = 0, len(data) - 1
                while lo <= hi:
                    mid = (lo + hi) // 2
                    if data[mid]['key'] == key:
                        return data[mid]['value']
                    elif data[mid]['key'] < key:
                        lo = mid + 1
                    else:
                        hi = mid - 1
        return None

    def _flush(self):
        """Write sorted memtable to disk as an SSTable."""
        path = os.path.join(self.directory, f"sst_{len(self.sstables)}.json")
        data = [{'key': k, 'value': v} for k, v in self.memtable.items()]
        with open(path, 'w') as f:
            json.dump(data, f)
        self.sstables.insert(0, path)  # newest first
        self.memtable = SortedDict()

Drill 3: B-Tree Search in Python

python
class BTreeNode:
    def __init__(self, leaf=True):
        self.keys = []       # sorted list of keys
        self.values = []     # values (only in leaf nodes)
        self.children = []   # child pointers (only in internal nodes)
        self.leaf = leaf

def btree_search(node, key):
    """Search for a key in a B-tree. Returns (node, index) or None."""
    if node is None:
        return None

    # Binary search within the node's keys
    lo, hi = 0, len(node.keys) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if node.keys[mid] == key:
            return (node, mid)    # found!
        elif node.keys[mid] < key:
            lo = mid + 1
        else:
            hi = mid - 1

    # Not found in this node
    if node.leaf:
        return None           # key doesn't exist
    else:
        return btree_search(node.children[lo], key)  # recurse into child

# Usage: each recursive call = one disk page read
# Total disk reads = depth of tree = log_b(n)

Drill 4: Bloom Filter in Python

python
import hashlib

class BloomFilter:
    """Simple Bloom filter with k=3 hash functions."""

    def __init__(self, size=1000):
        self.size = size
        self.bits = [False] * size

    def _hashes(self, key):
        """Generate 3 hash positions for a key."""
        h = hashlib.md5(key.encode()).hexdigest()
        return [
            int(h[:8], 16) % self.size,
            int(h[8:16], 16) % self.size,
            int(h[16:24], 16) % self.size,
        ]

    def add(self, key):
        for pos in self._hashes(key):
            self.bits[pos] = True

    def might_contain(self, key):
        """Returns False = definitely not in set. True = maybe in set."""
        return all(self.bits[pos] for pos in self._hashes(key))

# Usage in LSM read path:
# if not bloom_filter.might_contain(key):
#     skip_this_sstable()  # saved a disk read!

Capacity Planning: A Worked Example

Let us size a real storage system from scratch — the kind of back-of-envelope calculation you would do in a system design interview:

The Five-Minute Interview Framework

When asked "Design a [X] storage system" in an interview, use this framework:

Quick Reference: When to Use What

Performance Mental Model: The Numbers Everyone Should Know

Jeff Dean's famous "latency numbers every programmer should know," updated for 2024 hardware and applied to storage engines:

Chapter 10: Connections

Storage and retrieval is the foundation upon which everything else in database systems is built. Now that you understand how data is organized on disk (and in memory), the remaining DDIA chapters snap into focus:

Beyond This Chapter

The storage engine landscape continues to evolve. Some frontiers worth exploring:

Learned indexes (2018). Tim Kraska et al. proposed replacing B-trees with neural networks that predict the position of a key. A small ML model trained on the data distribution can predict "key 42 is at approximately position 1,247,000" faster than traversing a B-tree. If the data has a near-uniform distribution, a linear model (2 multiplications) replaces a 4-level B-tree (4 random reads). Still mostly academic, but Google's internal systems reportedly use learned index components for specific workloads.

Persistent memory (Intel Optane). Non-volatile memory that sits between DRAM and SSD in both speed and capacity. It blurs the line between in-memory and disk-based databases, potentially making the WAL unnecessary (writes persist directly to memory). Intel discontinued Optane in 2022, but CXL-attached persistent memory from other vendors continues the concept.

Disaggregated storage (Aurora, Neon). Separate the compute (query processing) from storage (data persistence) and connect them via a fast network. The storage layer replicates and persists data independently, while compute nodes are stateless and can scale independently. Aurora DSQL (2024) pushes this further with active-active multi-writer across regions — something traditional storage engines were never designed for.

LSM-tree optimizations. WiscKey (2016) separates keys from values in LSM-trees — keys stay in the LSM-tree, values go in a separate log. This reduces write amplification dramatically because only small keys are compacted, not large values. RocksDB's BlobDB implements this pattern. For large values (images, embeddings), this can reduce write amplification from 50x to 5x.

The rise of Rust databases. A new generation of storage engines written in Rust (TiKV, SurrealDB, Qdrant, AgateDB) is challenging the C/C++ incumbents. Rust's ownership model prevents entire classes of bugs (buffer overflows, use-after-free) that have caused data corruption in production databases. The performance is comparable to C++, but the safety guarantees mean fewer catastrophic production incidents.

The Modern Landscape: Convergence

The biggest trend in storage engines today is convergence. The hard lines between categories are blurring:

Vector Indexes: The New Frontier

With the rise of AI and embeddings, a new category of index has emerged: the vector index. Instead of looking up keys or ranges, you search for the nearest neighbors in a high-dimensional embedding space. "Find the 10 products most similar to this one" is a vector search query.

The dominant algorithm is HNSW (Hierarchical Navigable Small World): a multi-layer graph where each node is an embedding vector. Higher layers contain fewer nodes (for fast, coarse search), lower layers contain all nodes (for precise results). A query navigates top-down, getting closer to the target at each layer. Typical query latency: 1-5ms for finding 10 nearest neighbors among 10 million vectors.

Recommended Reading

The Big Picture

Everything in this chapter comes down to one sentence: different access patterns demand different storage layouts. There is no universal "best" storage engine, just as there is no universal "best" data structure. A hash map is perfect for key lookups, terrible for sorted iteration. A sorted array is perfect for binary search, terrible for insertions. Storage engines are the same — each is optimized for a specific workload pattern.

The mark of a strong engineer is not memorizing which engine to use when. It is understanding why each engine makes the trade-offs it does, so you can reason about novel situations the way the engine designers did. If you understand that LSM-trees convert random writes into sequential writes by buffering in memory — you can predict that any write-heavy workload benefits. If you understand that B-trees keep data in a single sorted structure — you can predict that they offer better read latency and stronger transaction support. If you understand that column stores skip unnecessary data — you can predict that any analytical query benefits from columnar layout.

The principles are timeless. The specific engines will change. The trade-offs will not.

Implementation Challenges

If you want to cement your understanding, try building these (in order of difficulty):

Each challenge from the table above can be done in a single file in Python. The goal is not production quality — it is to experience the engineering trade-offs firsthand. You will remember the design decisions much better after fighting with them in code.

A Final Quote