Overview

Fixed-size pages give I/O a well-defined unit -- the buffer pool, the B-tree's fanout math, and a checksum all assume the same fixed unit; without it, none of those mechanisms would have a stable size to reason about. Page size is engine-specific (Postgres 8 KB, InnoDB 16 KB), not universal (Example 1).

A header, a slot array growing forward from right after the header, and tuple data growing backward from the end of the page, with free space between the slot array and the tuple data. The slot array and tuple data are the two regions that grow toward each other; the page is full exactly when they meet (Examples 2, 3, 4, 6).

A byte offset changes whenever a compaction moves a record, which would invalidate any external reference that stored the old offset. A slot index stays stable across a compaction because only the slot array's own entry gets rewritten to point at the record's new location -- external references never need to change (Examples 5, 7, 8).

The page table maps page-id to frame. Each frame carries a pin count (how many callers currently depend on this page staying resident) and a dirty bit (whether the page has been modified since it was loaded) (Examples 10, 13).

CLOCK approximates LRU cheaply via one reference bit per frame instead of maintaining a full recency ordering. LRU-K tracks the last K references (not just the most recent one), which is what lets it tell a genuinely hot page apart from a page touched only once during a sequential scan -- plain LRU cannot make that distinction and will evict hot pages during a scan. Whichever policy picks the victim, eviction itself must still write back a dirty page before the frame is reused, which is exactly what Example 14 verifies (Examples 14, 15, 16, 41).

Every metric (hit ratio) and every higher-level mechanism (the WAL's materialization path, an index's page fetch) assumes reads genuinely check memory before disk -- if that ordering were violated, a hit ratio would be meaningless and disk-read counts would not reflect real cache behavior (Examples 11, 12, 42).

A B-tree stores values at every node; a B+-tree keeps values only in leaves, with the leaves linked as siblings. Most SQL "btree" indexes (Postgres nbtree, InnoDB) are actually B+-trees, even though their public API calls them "btree" (Examples 17, 22).

Tree height is approximately log_fanout(N) -- a higher fanout means each level can route among more children, so the tree stays shallow even as N grows into the billions. A fanout in the hundreds keeps a B-tree only 3-4 levels deep at realistic scale, which is why B-trees are the default on-disk index structure. Example 18 confirms a lookup actually benefits from that shallow depth, and Example 43 shows bulk-loading sorted keys bottom-up builds the identical shape a one-by-one insert would (Examples 18, 19, 43).

An overflowing leaf splits in two and promotes a separator key upward into its parent; if the parent also overflows from that promotion, the split propagates further up, potentially all the way to the root -- which is exactly how a B-tree grows one level taller while staying balanced. Deletion is the mirror image: Example 45 shows a leaf underflow triggering a merge or borrow instead of a split (Examples 20, 44, 45).

Without sibling links, crossing from one leaf to the next during a range scan would require re-descending from the root -- an O(log N) cost paid again for every leaf boundary. Sibling links turn a multi-leaf range scan into one descent plus a cheap linear walk across linked leaves (Example 21).

Many individual writes accumulate in the sorted memtable first; when it's flushed, the ENTIRE memtable becomes one large, already-sorted, sequential write to a new immutable SSTable -- the many small random writes never individually touch disk (Examples 23, 24).

Because SSTables are immutable, an update or delete cannot modify an old value in place -- it can only add a newer entry (or a tombstone) that shadows the older one. Checking newest-to-oldest and stopping at the first match is exactly what makes the newest write win (Examples 25, 26).

Leveled compaction (RocksDB's default) favors read cost and space at the expense of more write amplification; size-tiered compaction (Cassandra's default) favors write cost at the expense of more space and slower reads. Neither is universally better -- it's a workload bet (Examples 48, 49).

The RUM conjecture claims no single design can simultaneously minimize read, write, and space amplification all at once -- improving one tends to cost one of the others. That's precisely why choosing between a B-tree and an LSM tree is a real trade-off decided by the actual workload, not a question with one universally correct answer. Examples 77, 78, and 79 measure that trade-off directly on real engines: the LSM sustains higher write throughput, the B-tree answers point reads in fewer page reads, and a workload-driven chooser picks the LSM for write-heavy load and the B-tree for read-heavy load (Examples 50, 51, 52, 77, 78, 79).

A false negative would mean a read incorrectly skips an SSTable that actually contains the key -- that would silently produce a wrong answer, which is unacceptable. A false positive only causes an unnecessary (but safe) SSTable check. That asymmetry is what makes a Bloom filter safe to rely on for reducing read amplification (Examples 27, 28, 53).

A log record must reach stable storage before the page it describes is written. If a page could reach disk first and the system crashed in between, there would be no log record to explain what that on-disk change even was, with no way to reconstruct or verify it during recovery (Examples 29, 30).

Whether that specific log record's change is already reflected on the page. If the record's LSN is less than or equal to the page's pageLSN, the change is already applied and redoing it again would be wrong (or at least redundant) -- this comparison is what makes redo idempotent (Examples 31, 32).

Analysis, then redo, then undo. "Repeats history" means redo replays EVERY logged change, whether its transaction eventually committed or not -- it does not try to distinguish winners from losers during redo. That deliberate choice avoids the much harder problem of deciding transaction outcomes before the log has even been fully processed; undo, which runs after redo, is what removes the losers' effects (Examples 64, 65, 66, 67).

A no-force policy (a committed page need not reach disk at commit time) makes redo necessary, since a committed change might still only exist in the log after a crash. A steal policy (an uncommitted page CAN be written to disk before commit, e.g. under memory pressure) makes undo necessary, since an uncommitted change might already be on disk. Real engines use steal + no-force for buffer-pool flexibility, which is exactly why both redo and undo are needed together -- Example 67 combines both in one end-to-end recovery over a crashed log (Examples 33, 34, 67).

A checkpoint bounds how far back in the log recovery must scan -- it records a known-consistent point, so recovery only replays log records written after it. Without checkpoints, every recovery would need to scan the log all the way back to the database's very first write, making recovery time grow unboundedly with the database's age (Example 35).

An update appends a brand-new row version rather than modifying the old one. xmin records the transaction id that created a version; xmax records the transaction id that deleted it (or stays unset if the version is still live) -- together they let the engine reconstruct exactly which versions existed at any point in time (Examples 36, 38).

A snapshot sees every version committed before it, and not yet deleted as of that point. Because this rule only reads facts already recorded on each version (who created it, who deleted it) -- it never needs to acquire a lock on a concurrently-running writer, and a writer never needs to wait for a reader either (Examples 37, 39).

Every update leaves the old version behind; once no active snapshot can still see a given dead version, it serves no purpose but still occupies space. VACUUM (or an equivalent garbage-collection pass) is what reclaims that space by removing versions no live snapshot can ever reference again (Example 40).

Read-uncommitted permits dirty reads; read-committed stops dirty reads but permits non-repeatable reads; repeatable-read stops non-repeatable reads but (in the classical definition) permits phantom reads; serializable stops all of the above. PostgreSQL's REPEATABLE READ is actually snapshot isolation, and snapshot isolation still permits write skew even though it blocks the classical phantom-read pattern -- only true serializable (SSI) catches write skew. Example 76 runs that same write-skew pair under serializable and confirms one transaction aborts instead (Examples 72, 73, 74, 75, 76).

2PL pays a locking cost upfront on every access, betting that conflicts are common enough to be worth preventing early. OCC pays nothing until a commit-time validation check, betting that conflicts are rare. Strict 2PL adds the rule that write locks are held until commit (not released as soon as the growing phase's own last access happens), which is exactly what prevents cascading aborts that plain 2PL still permits (Examples 68, 69, 70, 71).

A page write can be physically interrupted mid-write by a crash, leaving a "torn" page that is neither the old version nor the fully-written new one -- Example 9's per-page checksum is what lets recovery even detect that tearing happened. PostgreSQL's full-page-writes and InnoDB's doublewrite buffer are both mitigations that let recovery repair a torn page rather than merely detect that it happened; fsync is what forces a write to genuinely reach stable storage in the first place, and group commit amortizes that fsync cost across many transactions (Examples 9, 60, 61, 62, 63).

Clustering (InnoDB's PK, SQLite's rowid tables) makes a primary-key lookup essentially free -- the row itself lives right in the B+-tree leaf, no extra indirection needed. It makes secondary-index maintenance more expensive, since a page split can change where a row physically lives, and every secondary index's pointer would need updating. A heap (PostgreSQL) decouples the two by storing rows separately, with secondary indexes pointing via a stable row-id/ctid (Examples 46, 47).

A column store lays out one column's values contiguously, all the same type, often with repeated or slowly-changing values (an OLAP pattern) -- that contiguity and homogeneity is exactly what dictionary encoding (mapping repeated values to small integer codes), run-length encoding (collapsing consecutive repeats), and delta encoding (storing differences between consecutive monotonic values) all exploit. Interleaved with other columns' unrelated values, as a row store does, none of those patterns would hold (Examples 54, 55, 56, 57, 58, 59).

Page size is engine-specific, not universal (co-01) -- Postgres and SQL Server use 8 KB, InnoDB uses 16 KB. The "correct" answer is a design trade-off (I/O granularity vs. internal fragmentation), not a fixed industry constant (Example 1).

This is exactly what plain LRU mishandles and LRU-K is built for (co-05) -- a one-time sequential scan touches every page exactly once, which looks "recently used" to plain LRU and evicts genuinely hot pages in the process; LRU-K's multi-reference history correctly distinguishes the two access patterns (Example 41).

This is the B-tree-vs-B+-tree decision (co-07) -- keeping values only in leaves (a B+-tree) makes internal nodes smaller and more cacheable, and the leaf-sibling links this enables are what make range scans fast; most production SQL "btree" indexes make this choice (Examples 17, 22).

Sibling-linked leaves (co-10) fix exactly this -- once the scan reaches the first matching leaf, it walks forward via sibling links instead of re-descending, turning a multi-leaf range scan into one descent plus a cheap linear walk (Example 21).

An LSM-tree (co-11) is the workload-appropriate alternative -- buffering writes in an in-memory memtable and flushing sorted, immutable SSTables converts many small random writes into large sequential ones, which is precisely what a write-heavy ingestion workload needs (Examples 23, 24).

A per-SSTable Bloom filter (co-15) directly addresses this -- its no-false-negatives guarantee lets a read safely skip any SSTable the filter reports as definitely lacking the key, cutting read amplification without any risk of missing a real match (Examples 27, 28, 53).

This is the WAL rule plus fsync as a durability barrier (co-16, co-26) -- the commit acknowledgment must not be sent until the transaction's log record has genuinely reached stable storage via fsync, which is the only guarantee that survives a crash occurring the instant after (Examples 29, 30, 60).

ARIES's redo-then-undo phases (co-18, co-19) solve exactly this -- redo first repeats history, replaying every logged change regardless of commit status, deferring the committed/uncommitted question entirely; undo then rolls back only the uncommitted (loser) transactions' effects, using compensation log records (Examples 64, 65, 66, 67).

MVCC's snapshot read (co-21, co-22) is designed for exactly this -- the snapshot visibility rule lets the reporting query see versions committed before its snapshot point without ever taking a lock a concurrent writer would have to wait on (Examples 36, 37, 38, 39).

This is write skew under snapshot isolation (co-24) -- PostgreSQL's REPEATABLE READ is actually snapshot isolation, which blocks the classical phantom-read pattern but does NOT block write skew; only true serializable (SSI) detects the rw-antidependency cycle and aborts one of the two transactions (Examples 75, 76).

This points toward 2PL over OCC (co-25) -- OCC's read/validate/write cycle bets that conflicts are rare and pays for that bet with restarts whenever a conflict IS detected at validation time; under genuinely high contention, that bet loses often, and 2PL's upfront locking (which simply makes a conflicting transaction wait, rather than restart) tends to perform better (Examples 68, 69, 70).

This is a torn page (co-26) -- a page write is not atomic across a crash, and full-page-writes (or a doublewrite buffer) are the mitigation that lets recovery detect and repair exactly this mixed state, by restoring the page from a full pre-image logged before the write began (Examples 62, 63).

A column store (co-28) is the correct layout for this access pattern -- laying the target column's values contiguously means the aggregate query reads only the bytes for that one column, skipping every other column entirely, and the layout also enables dictionary/run-length/delta compression that a row store's interleaved layout cannot exploit (Examples 54, 55, 56).

Root cause: the header's pd_lower field is the ONLY thing that tracks how many slots already exist -- if it's never written back after an insert, the next insert recomputes the exact same slot_count and reuses the exact same slot offset, silently clobbering the previous record's slot entry. Packing (new_pd_lower, new_pd_upper) back into the header is what makes the slot array genuinely grow.

Run: python3 kata.py

Output:

0 1
b'first'

Root cause: _evict() never consulted pin_count at all -- it just removed whatever frame happened to be first in dict-iteration order, which can (and did) include a frame a caller is actively depending on. Scanning specifically for an UNPINNED frame, and failing loudly with a RuntimeError when none exists, is what makes the pin count a real safety guarantee rather than decorative bookkeeping.

Run: python3 kata.py

Output:

buffer pool full and every frame is pinned -- cannot evict
True

Root cause: range_scan()'s correctness depends entirely on leaf already being sorted -- it never sorts anything itself, it just filters in existing order. An insert() that always appends gives no such guarantee, so a range scan over out-of-order data returns results in whatever order they happened to be inserted. bisect.insort is what actually maintains the sorted invariant that range_scan silently relies on.

Run: python3 kata.py

Output:

[(1, 10), (3, 30), (5, 50), (7, 70)]
True

Root cause: LSM SSTables are immutable, so a newer write to the same key lives in a NEWER SSTable, never overwriting the old one in place -- scanning oldest-first means the read stops at the stale value the very first time it finds any match at all, never reaching the newer, correct one. Scanning reversed() (newest-first) is the one-line fix that makes "the newest write wins" actually true.

Run: python3 kata.py

Output:

updated-value
True

Root cause: durability (the log record persisting) and visibility (the write becoming readable) are two DIFFERENT guarantees that commit() must provide together -- the buggy version only provided durability, flipping a flag on the already-logged record, but never actually applied the value into the table readers query. A real commit path both marks the record committed AND materializes it.

Run: python3 kata.py

Output:

v1

Root cause: MVCC's entire visibility model depends on old versions staying PRESENT, just tagged with the transaction that deleted them (xmax) -- physically removing a version the moment it's deleted destroys the exact history an earlier snapshot needs to still see. Setting xmax instead of popping is what lets a snapshot correctly answer "was this row visible AS OF my snapshot point," regardless of what happened after.

Run: python3 kata.py

Output:

row-exists

Root cause: "repeatable read" is a promise about what a SNAPSHOT sees, not a promise that the underlying data never changes -- holding a live reference to mutable state means every query re-reads whatever the world looks like right now, which is exactly what a genuine snapshot is supposed to prevent. Taking an explicit copy (or, in a real engine, resolving reads through MVCC's snapshot visibility rule from co-22) is what makes the two reads inside one transaction agree.

Run: python3 kata.py

Output:

1 1
True

Root cause: releasing a write lock as soon as the write itself is done (rather than holding it until commit) is plain 2PL's shrinking phase starting too early -- it lets a second transaction acquire and potentially read or overwrite data from a transaction that might still abort, which is precisely the cascading-abort risk strict 2PL exists to close. Tracking every acquired lock and releasing the whole set together, only inside commit(), is strict 2PL's defining rule.

Run: python3 kata.py

Output:

False
True

The ORDER is the entire guarantee -- "eventually logged" says nothing about what happens if a crash lands between the page write and the (still-pending) log write, which is exactly the window where data could be lost with no way to reconstruct it. Requiring the log record first means that at any point a crash could occur, the log is always at least as up to date as any page, which is the precondition every later recovery mechanism (LSN comparison, ARIES's phases) depends on.

Because the RUM conjecture names a real, unavoidable trade-off -- no single design minimizes read, write, and space amplification simultaneously. A B-tree tends to favor read latency and in-place update simplicity; an LSM tree tends to favor write throughput at the cost of read amplification (mitigated by Bloom filters) and compaction overhead. Recommending one universally would mean ignoring the actual workload, which is precisely the mistake the RUM conjecture warns against.

The entire benefit of MVCC (non-blocking snapshot reads) depends on old versions staying present long enough for any snapshot that might still need them -- but that same design means dead versions accumulate by construction, since nothing automatically removes a version the moment it's superseded. VACUUM is the necessary other half of the trade: MVCC buys non-blocking concurrency at the cost of a cleanup pass that a simpler "update in place" design would never have needed in the first place.

Snapshot isolation's guarantee is about what each transaction READS -- both transactions see a consistent snapshot, so neither observes a phantom row appearing mid-transaction. Write skew doesn't require either transaction to see anything inconsistent; it only requires that each transaction reads a value the OTHER is about to change and that neither's read technically conflicts with the other's write under snapshot isolation's conflict-detection rules. Catching that requires reasoning about the whole pair's write-read (rw-antidependency) relationship, which only true serializable (SSI) actually checks.

Plain 2PL's rule (never acquire a new lock after releasing any lock) prevents SOME anomalies, but still allows a second transaction to acquire a just-released lock and read data from a first transaction that has not yet committed -- if the first transaction later aborts, that second transaction has now read (and possibly acted on) data that never should have existed, a cascading abort. Holding every write lock until commit closes exactly that window, at the cost of longer lock hold times.

"One disk operation" from the application's view is not atomic at the hardware level -- disk sectors are written incrementally, and a crash mid-write can leave a page that is neither the old, valid version nor the new, valid version, but a genuinely corrupted mix of both. Because a checksum alone can only DETECT this, not repair it, mitigations like full-page-writes exist specifically to give recovery something (a full pre-image) to restore from, closing the gap between "detected corruption" and "durable data."

Plain LRU makes its eviction decision from a SINGLE piece of information -- the one most recent access. LRU-K deliberately tracks the last K references for each page and bases eviction on the K-th-most-recent reference specifically, which is what lets it distinguish a page touched once during a scan (whose K-th reference, if K > 1, doesn't exist or is very old) from a page touched repeatedly by a hot workload. That's a genuinely different decision rule, not just a parameterized version of the same one.

A clustered index physically locates the row inside its own B+-tree leaf, which means a leaf split (or any operation that moves the row) changes the row's physical location -- and any secondary index pointing at that row by its old physical location would now be wrong unless it's updated too. A heap avoids this coupling by giving every row a stable, physical-location-independent identifier (row-id/ctid) that a secondary index can point to without needing to track every clustered-index reorganization.