Primary Index as an Indirection / Buffering, Immutability, and Ordering
Chapter 1 · pages 33–36 · 996 words
This section addresses a design choice for how secondary indexes locate actual data: should they point directly to a data record's physical location, or should they go through the primary index as a layer of indirection? Pointing directly (via file offset) minimizes disk seeks on reads, but every time a record moves or is updated, every index pointing to it must be patched — costly under write-heavy workloads with many indexes. Using the primary index as indirection means secondary indexes store primary keys rather than offsets; a query then does two lookups (secondary index, then primary index) but only the primary index needs updating when a record relocates, since secondary indexes never held raw offsets to begin with. MySQL InnoDB is given as a real example of the indirection approach. A hybrid option is also possible: store both an offset and a primary key, check whether the cached offset is still valid, and fall back to the primary-key lookup (paying the extra cost) only when it isn't, updating the cached offset afterward.
The second half of the section steps back from any single data structure and names three orthogonal variables that recur across virtually every storage engine design discussed later in the book: buffering, mutability, and ordering. Any two engines can be compared along these three axes even if their underlying structures look completely different.
Buffering is about whether the engine deliberately accumulates writes in memory before flushing to disk, beyond the unavoidable minimum of writing in block-sized units. This is a chosen optimization — for example, giving B-Tree nodes in-memory buffers to amortize I/O — and different structures apply it differently; two-component LSM Trees combine buffering with immutability in a distinct way from buffered B-Trees.
Mutability (or immutability) asks whether updates rewrite data in place or whether the engine only ever appends new versions, leaving old file contents untouched. Immutable designs are typically append-only, though copy-on-write is another route: the updated page is written to a new location rather than overwriting the old one. While immutability is often associated with LSM Trees and in-place update with B-Trees, the correspondence isn't strict — Bw-Trees, for instance, are B-Tree-inspired yet immutable.
Ordering asks whether records with nearby keys are physically stored near each other on disk. Ordered storage enables efficient range scans, not just point lookups, whereas storing records out of order (commonly in insertion order, as Bitcask and WiscKey do) trades that away for write-time optimizations. Together these three variables — buffering, mutability, ordering — form the conceptual toolkit the book will reuse when explaining why so many storage structure variants exist.
graph LR A[Storage structure] --> B[Buffering: yes/no] A --> C[Mutability: mutable/immutable] A --> D[Ordering: in-order/out-of-order]
Exhibits and original pages (3)
