A B+tree is a page-management policy

“Use a B-tree index” leaves most of the storage decision unanswered. How wide are the keys? Does the query need the rest of the row? Do inserts keep revisiting the same few pages, or spread across a working set larger than the buffer pool?

Ben Dicken’s PlanetScale article is good at connecting the data structure to those questions. This lab keeps that connection: first compare complete workloads, then use Page mutations to inspect the split and merge mechanics behind them.

Start with the same workload, not two convenient pictures #

The default experiment inserts the same 3,000 keys in two orders. One is sequential; the other is a seeded permutation. Both use the same page size, row width, median-split policy and initially empty LRU buffer pool.

That setup separates key order from key width. A binary UUID and a text UUID also have different storage costs; calling both experiments “random keys” would hide an important variable.

Watch the cumulative buffer misses. Sequential inserts keep returning to the rightmost path. Random inserts revisit leaves throughout the tree. When the cache is small, those visits can repeatedly evict dirty pages that the next few inserts need again.

Increase the buffer pool. The locality penalty should change even though the tree’s ordering and search complexity do not. This is why “both are O(log n)” is not a useful performance conclusion.

Capacity follows bytes #

Branch pages store separators and child pointers. Clustered leaves store keys and row payloads. Their capacities should not be the same just because a diagram draws identical rectangles.

With the lab’s explicit overhead assumptions, the maximum separator count is

where $P$ is page size, $H=128$ bytes is the page header, $K$ is key width and $C=8$ bytes is a child pointer. A branch with $n$ separators has $n+1$ children.

Leaf capacity is

with row payload $R$ and eight bytes of assumed record/slot overhead. These are the capacities used by the workload’s actual tree, not numbers printed next to an unrelated three-key animation.

Try a 512-byte payload, then increase page size. The leaf capacity changes much more dramatically than the branch capacity. Real engines add details—variable-length fields, compression, prefix truncation, version metadata and overflow storage—that can move these boundaries considerably.

Count the writes at the right boundary #

A dirty-page touch is not a disk write. Ten updates to a page while it remains cached may eventually produce one page flush. Ten updates separated by evictions can produce many.

The lab reports three different quantities:

• Logical dirty-page touches: pages modified by tree operations.
• Page flushes: dirty evictions plus the final checkpoint.
• Logical WAL estimate: row and key bytes plus an explicitly assumed 24-byte record overhead per insert.

Only the first two are observed counters in this simulation. The WAL figure is a capacity estimate. Structural log records, full-page images, compression and engine-specific encodings are excluded.

A write-ahead log also changes the acknowledgement path. An engine may acknowledge after the required log records are durable while data pages remain dirty in memory. That does not mean data-page writes disappeared; it means durability and eventual page placement have different timing. The lab makes no claim about fsync latency, group commit or device-level write amplification.

There is another useful surprise: the sequential tree can have lower occupancy because the model uses median splits. InnoDB has policies that treat right-edge growth differently. Do not turn the drawing into a claim about InnoDB’s exact page count.

The secondary lookup can dominate the index lookup #

The read experiment selects 100 adjacent insertion-time records. Imagine a range over a timestamp index. That index produces primary keys, which are then used to fetch full rows from the clustered tree.

With sequential primary keys, neighboring insertions tend to share clustered leaves. With shuffled primary keys, they can occupy many different leaves. The experiment reports the distinct clustered leaves and actual cache lookups for those row fetches, using the cache left after the load.

Switch to a covering secondary index. The clustered lookups disappear because the selected payload is available in the index. But the secondary entries become wider, so fewer fit on a page.

The secondary footprint and range-page counts are estimates from entry width, not a second simulated tree. The stated page-aligned range count is a lower bound; an unaligned range can touch another leaf. Secondary update maintenance and its cache interference are not modeled. That distinction matters when deciding whether a covering index is worth its write and memory budget.

This is also InnoDB-oriented reasoning. PostgreSQL’s heap layout and visibility requirements produce a different path; an “index-only” plan there can still need heap visibility checks.

Inspect the structural invariants #

Open Page mutations. This view deliberately uses small capacities so individual edits remain legible.

Records live only in leaves. Each internal separator equals the minimum key in the child immediately to its right. Searching for a key equal to a separator therefore goes right. A split copies the routing boundary into the parent; it does not remove the record from the leaf.

Insert 42, inspect the page IDs, then delete keys until a sibling lends a record or two pages merge. The IDs distinguish a local edit from rebuilding a fresh tree. A range scan descends once, then follows the leaf chain.

The implementation is tested through mixed insertion/deletion sequences for sorted keys, occupancy, correct separators, uniform leaf depth and an intact linked-leaf order. Counting splits without checking those invariants would be a particularly unhelpful benchmark.

What I would take into a design review #

I would not choose a primary key from this experiment alone. I would bring a workload: row-width distribution, secondary indexes, range predicates, insert concurrency, cache budget and the independence requirements of ID generation.

Sequential IDs have locality benefits but can concentrate concurrent inserts on the right edge. Time-ordered distributed IDs may be a useful compromise. A wider primary key can multiply storage costs because secondary indexes carry it. A covering index can save reads while making an already expensive write path worse.

The useful conclusion is a conditional one: given this workload and this memory budget, which pages do we repeatedly need, and which design makes them cheaper to keep useful?

Reference: Ben Dicken, B-trees and database indexes, PlanetScale. This is an original local implementation informed by the article’s sequential/random insertion, page-width, secondary-lookup and buffer-pool experiments. It is not an InnoDB benchmark.