Storage and Retrieval

3.1Chapter Thesis

A database engine is not a black box with a query language bolted on top - it is one specific data structure, chosen deliberately, that determines exactly which operations are fast and which are slow. Understanding a storage engine means understanding which data structure it committed to, and why that commitment forces everything else.

The central tension is between writes and reads: the fastest possible write is an append to the end of a file, and the fastest possible read is a direct lookup by key. No single data structure gives you both for free - every storage engine is a specific answer to how much read cost it is willing to trade for write speed, or vice versa.

3.2First Principles

Append-only is the cheapest possible write

Sequential writes to the end of a file are dramatically faster than writes at random offsets, because they don't require seeking and they play well with both spinning disks and SSD wear leveling. This single fact is the reason log-structured storage engines exist at all.

An index is a tradeoff, not a free lookup

Any index speeds up the queries it was built for and slows down every write, because the index itself must be updated whenever the underlying data changes. Choosing which fields to index is choosing which future queries you're willing to pay for now.

In-memory index over on-disk data

A hash index mapping every key to a byte offset in an append-only file gives O(1) reads and O(1) writes, as long as the entire index fits in memory. The constraint that makes this fragile is exactly that: the moment the key set outgrows RAM, the mechanism stops working, which is the boundary condition every log- structured engine has to design around.

Compaction reclaims space without random-access rewrites

An append-only log grows forever unless old, overwritten values are reclaimed. Compaction rewrites a segment, keeping only the most recent value for each key, and does so by writing a brand-new segment sequentially - never by mutating the old one in place.

3.3Mechanism

A write appends a length-prefixed key/value record to the active log segment and updates an in-memory hash map from key to (segment, offset). A read looks up the offset in the hash map and seeks directly to it - no scan required. When the active segment crosses a size threshold, it's closed and a new one is opened; a background process merges old, closed segments via compaction, discarding superseded values.

This is precisely the mechanism behind Bitcask-style engines. Its fundamental limitation - the index must fit in memory - is what B-trees and LSM-trees each solve differently: B-trees keep the index itself on disk, organized so a lookup is a small number of disk-page reads; LSM-trees keep the recent index in memory but periodically flush sorted, immutable files (SSTables) to disk and merge them, trading read complexity (checking multiple files) for sustained write throughput.

3.4Build It Yourself

A minimal Bitcask-style engine: append-only log plus an in-memory hash index.

interface Location { segment: number; offset: number; }

class BitcaskEngine {
  private log: string[] = [""];
  private index = new Map<string, Location>();

  put(key: string, value: string): void {
    const segment = this.log.length - 1;
    const record = JSON.stringify({ key, value }) + "\\n";
    const offset = this.log[segment].length;
    this.log[segment] += record;
    // index always points at the most recent write -
    // older copies of the same key become dead space.
    this.index.set(key, { segment, offset });
  }

  get(key: string): string | undefined {
    const loc = this.index.get(key);
    if (!loc) return undefined;
    const tail = this.log[loc.segment].slice(loc.offset);
    const line = tail.slice(0, tail.indexOf("\\n"));
    return JSON.parse(line).value;
  }

  // compaction: rewrite only live keys into a fresh segment,
  // sequentially - never mutate a segment in place.
  compact(): void {
    let merged = "";
    const newIndex = new Map<string, Location>();
    for (const [key] of this.index) {
      const value = this.get(key)!;
      const offset = merged.length;
      merged += JSON.stringify({ key, value }) + "\\n";
      newIndex.set(key, { segment: 0, offset });
    }
    this.log = [merged];
    this.index = newIndex;
  }
}

3.5Failure Modes

3.6Tradeoffs

3.7Production Perspective

Real log-structured engines (LevelDB, RocksDB) generalize this exact mechanism into multiple levels of sorted files, using bloom filters to avoid checking files that can't contain a key and background compaction threads tuned to balance write amplification against read amplification - the same tradeoff this minimal engine makes explicit at a much smaller scale.

3.8Related Concepts