SSTable Storage Walkthrough

A key is never inserted into a file on disk. It is inserted into a sorted tree in memory, and that tree is later written out whole as a new sorted file. A read looks in memory first, then works back through the files from newest to oldest. Run an operation and step through what it touches.

In this model the memtable holds 6 records and a block holds 3, so everything fits on screen. Real engines use megabytes and kilobytes. The sample keys are the hand… words from the book's figures.

How does a new key land in the right place?

It doesn't go into a file at all. A put appends one line to the log and inserts the key into the memtable. The memtable is the only sorted structure that accepts inserts, and it lives in RAM, where putting a key into a balanced tree is cheap.

When the memtable fills up, it is walked in key order and written out front to back. The file is sorted because the tree was. Existing segments are never opened for writing.

Where does a read look for it?

Memtable first, then each segment from newest to oldest. The first place that has the key answers the read, whether it holds a value or a tombstone.

That order is what makes overwrites and deletes work without editing old files. The stale value is still on disk. The read just never gets that far.

What does the sparse index buy?

It stores one key per block instead of one per record. Since the file is sorted, knowing where handbag and handiwork start is enough to know handful must sit between them.

So the index stays small enough for RAM even when the file is huge. The price is a short scan inside one block, which is read from disk in one go anyway.

What this model leaves out

Bloom filters. Each segment keeps one so a read for a missing key can skip the file without a disk read.
Background work. Flushes and compaction run on other threads while new writes go to a fresh memtable.
Compaction strategy. Real engines merge a few files at a time, by size tier or by level. A tombstone can only be dropped once no older file could still hold the key.
Blocks are compressed, and each file also records its smallest and largest key.

The read path as Go

This is the loop the stepper walks through, with the same early exits.

func (db *DB) Get(key string) (string, bool) {
    if e, ok := db.memtable.Get(key); ok {
        return e.Value, !e.Tombstone        // newest write wins
    }
    for _, seg := range db.segments {       // ordered newest first
        off, ok := seg.index.Floor(key)     // last index key <= key
        if !ok {
            continue                        // key sorts before the whole file
        }
        for _, e := range seg.ReadBlock(off) {
            if e.Key == key {
                return e.Value, !e.Tombstone
            }
            if e.Key > key {
                break                       // sorted: it can't be further on
            }
        }
    }
    return "", false
}