Commentary: btree-index

The same 100,000 keys, indexed twice. Inserted in sorted order — the case everyone calls the best case — they build the worse index. A study guide for btree.py.

cd btree-index
python3 demo.py       # the aha (§6) — ~20s, writes two real index files
python3 test_btree.py # pins every claim this page makes — ~2s

1. Orientation

This toy is a B+tree index living in one flat file of 1024-byte pages. It does two things: insert(key, value) and get(key). The Pager counts every page it fetches, which is the only cost this toy cares about.

The demo builds the same 100,000 keys twice. Once inserted in ascending order — the case everybody calls the best case — and once shuffled with a fixed seed. Same tree, same order 63, same key set, same code.

The sorted load produces the worse index. It is 38% bigger, its leaves are half empty, and at this N it is one level taller — so every lookup against it costs four page reads instead of three, forever.

By the end you should be able to:

• compute a tree's height from its page size and key width, before writing any code;
• explain why a lookup costing 3 page reads and 75 key comparisons beats one costing 17 of each, and derive the break-even ratio;
• say exactly why sequential inserts leave leaves at 50% and random inserts settle at 69%, and what a database does about it;
• know when the height penalty applies and when it doesn't — it is a threshold effect, and this page shows the two windows where it bites.

2. The problem this mechanism exists to solve

You have a table with 100 million rows and a query that wants one of them by id. Scanning is out. So you build an index — a data structure that turns the key into a location.

The obvious answer from an algorithms course is a balanced binary search tree: O(log n) comparisons, and 100 million rows means about 27 of them. That answer is close to worthless on disk, and understanding why is the whole reason B-trees exist.

That reframes the goal. You are not trying to minimise comparisons; you are trying to minimise page fetches, and you have a page's worth of bytes to spend on each one. A B-tree spends them by cramming hundreds of keys into one node, so a single fetch narrows the search by a factor of hundreds instead of two. It ends up doing far more comparisons than the binary tree and winning by a mile, because comparisons are free and page fetches are not.

Two goals then pull against each other, and both are defensible:

• Fewer levels. More keys per page means a shallower tree means fewer fetches. This argues for big pages, packed full.
• Cheaper updates. A modified node has to be written back whole. A big page means a big write for a one-key change, and a packed page means the next insert has to split it. This argues for small pages with slack left in them.

Every real engine picks a point on that line — Postgres defaults to an 8 KiB page filled to 90%, SQLite to 4 KiB — and the demo in §6 is about what happens when your insertion order picks a different point for you without asking.

3. Background you need

None of this is deep, but the commentary below leans on it.

The two that carry the result are the first and the fourth. If you only take one thing: the page is the unit of cost, and how full each page is is a property of your insertion order, not of the algorithm.

4. The mental model

Before any code. One file, sliced into fixed-size pages. A lookup is a walk down that file, one page fetch per level.

Two numbers govern everything that follows:

• Height — how many fetches a lookup costs. It is log(N) / log(fanout), so it grows in steps, not smoothly, and each step is permanent.
• Fill — what fraction of each page's 63 slots is actually used. Half-full pages halve the effective fanout, which is how fill turns into height.

The demo is about the second number silently setting the first.

5. Reading the source

194 lines, three classes and one function. Read it in this order.

5.1 The page geometry, decided in four constants

PAGE_SIZE = 1024
MAX_KEYS = 63                     # "order 63": a node holds at most 63 keys
HEADER = struct.Struct("!BHI")    # leaf flag, key count, leftmost child pid
SLOT = struct.Struct("!qq")       # the one record format: key, payload

These four lines fix the shape of the whole tree, and the arithmetic is worth doing by hand because it is the arithmetic a DBA does on a real index.

HEADER.size is 7 (B = 1, H = 2, I = 4). SLOT.size is 16 (two q, signed 64-bit). So a full node is 7 + 63 × 16 = 1015 bytes, nine short of the 1024-byte page — the largest MAX_KEYS that fits. Bump it to 64 and the page overflows.

MAX_KEYS = 63 means fanout 64: an internal node with 63 keys has 64 children. That is what buys the shallow tree:

A hundred thousand keys should therefore fit comfortably in height 3. Hold on to that; in §6 one of the two indexes doesn't manage it.

That table is a prediction, so I checked it by shrinking the page. Same 100,000 shuffled keys, MAX_KEYS varied:

Halving the page adds a level, every time, and the page reads track the height exactly. MAX_KEYS=3 is essentially a binary tree — 11 reads, against log₂(100000) ≈ 17 for a true one — and the entire gain from 11 reads down to 3 came from making the page bigger, not from a better algorithm. That is the §2 argument, measured.

The ! prefix (network byte order) is not decoration. Native = layout would insert padding and make the byte layout depend on the machine; ! makes the file identical on any architecture, which is what a real database file format does for exactly the same reason.

5.2 Pager — the only thing in the toy that costs anything

    def read_page(self, pid):
        self.reads += 1
        self.f.seek(pid * PAGE_SIZE)
        return self.f.read(PAGE_SIZE)

    def write_page(self, pid, data):
        self.writes += 1
        self.f.seek(pid * PAGE_SIZE)
        self.f.write(data)

The whole disk model. Page id p is the bytes at offset p × PAGE_SIZE, and the counters are the point: reads is the metric every claim on this page is measured in.

Two deliberate absences.

There is no cache. A real engine has a buffer pool, and the root page of a hot index is never actually read from disk. Adding one here would have made reads count misses rather than fetches, and the number would then depend on the cache size and eviction policy rather than on the tree — which is the thing being measured. The toy keeps the honest, cache-free number and lets §8 explain what the buffer pool would change.

There is no fsync. Durability is a different mechanism, and mixing it in would double the toy's size while teaching neither idea properly.

alloc() (btree.py:38-41) hands out page ids from a monotonic counter and nothing is ever freed. That is what makes the file reproducible: build the same keys in the same order and you get the same bytes, which the demo relies on and test_the_index_file_is_byte_identical_across_builds asserts.

5.3 Node.pack — one record format, and the trick that allows it

    def pack(self):
        out = [HEADER.pack(self.leaf, len(self.keys), 0 if self.leaf else self.kids[0])]
        for key, payload in zip(self.keys, self.kids if self.leaf else self.kids[1:]):
            out.append(SLOT.pack(key, payload))
        return b"".join(out).ljust(PAGE_SIZE, b"\x00")

There is a real problem hiding here. A leaf with n keys has n values — pairs, which serialise beautifully. An internal node with n keys has n+1 children, which does not pair with anything.

The usual fix is two page formats, or a trailing odd field. This toy instead puts child 0 in the header — that is what the I in !BHI is for — so slot i always carries (keys[i], kids[i+1]) and both node types share one 16-byte record. It costs one confusing expression (self.kids[1:]) and buys a SLOT struct that never needs a branch, which is most of why the file is 194 lines and not 300.

ljust(PAGE_SIZE, b"\x00") is why a page is always exactly PAGE_SIZE bytes even when nearly empty. That zero padding is not waste in the file-format sense — it is what makes offset = pid × PAGE_SIZE arithmetic valid, and it is exactly what the "avg leaf fill" number in §6 is measuring the size of.

5.4 scan — the linear search, and the <=/< that is not a typo

def scan(keys, key, leaf):
    """Linear scan for `key`. Returns (slot index, comparisons performed).

    In a leaf: the first slot whose key is >= `key` — where `key` belongs.
    Inside:    the child to descend into, so keys[i-1] <= key < keys[i].
    """
    i = 0
    while i < len(keys) and (keys[i] < key if leaf else keys[i] <= key):
        i += 1
    return i, min(i + 1, len(keys))

Two judgement calls in one line, and only one of them is load-bearing.

Linear, not binary. Deliberate, so the comparison count is visible and countable: scan returns how many comparisons it did, which is what makes the second half of §6 measurable at all. Whether that costs anything is §7.1 — I ran it, and the answer surprised me.

keys[i] < key in a leaf, keys[i] <= key inside. These look interchangeable and are not. keys[i] in an internal node is the smallest key in child i+1, so a key exactly equal to a separator lives to its right — which means the scan must step past an equal separator, hence <=. In a leaf the same key is the one you want, so the scan must stop on it, hence <. Making them the same character is the single easiest way to write a B-tree that loses data. So I broke it on purpose:

2,274 keys silently vanish out of 100,000 — and that number is derivable, not arbitrary. The random index has 2,275 leaves (§6), so it has 2,274 separators sitting in internal nodes. Every separator, and only a separator, becomes unfindable. The descent walks left past its own boundary and lands in the leaf next door. get returns None, no error, no corruption you could detect from outside. This is the line I would put a test on first, and test_the_64th_key_splits_the_root_exactly_in_half does exactly that with its final assertion, tree.get(32) == 320.

The min(i + 1, len(keys)) in the return is bookkeeping: a scan that stops early made i + 1 comparisons (the failed ones plus the one that stopped it), and a scan that ran off the end made len(keys).

5.5 get — the shape of the entire structure

    def get(self, key):
        pid = self.root
        self.last_path = []
        while True:
            self.last_path.append(pid)
            node = Node.unpack(self.pager.read_page(pid))
            i, comps = scan(node.keys, key, node.leaf)
            self.comparisons += comps
            if not node.leaf:
                pid = node.kids[i]
                continue
            self.comparisons += 1
            if i < len(node.keys) and node.keys[i] == key:
                return node.kids[i]
            return None

One read_page per level and no backtracking — the loop only ever descends. That is the promise of the structure, and it means pager.reads for a lookup equals the height exactly, which test_a_lookup_reads_exactly_height_pages asserts at heights 1, 2 and 3.

There is no separate "does this key exist" pass. A B+tree lookup is unconditional descent to a leaf followed by one equality test, so a miss costs precisely the same as a hit — a property that matters for anyone reasoning about worst-case latency.

The extra self.comparisons += 1 before the equality test is honesty about cost: the final keys[i] == key is a real comparison and the totals in §6.5 include it.

5.6 _insert — the recursion that carries splits back up

        else:
            split = self._insert(node.kids[i], key, value)
            if split is None:
                return None       # nothing below changed shape: this page is untouched
            sep, right = split
            node.keys.insert(i, sep)
            node.kids.insert(i + 1, right)
        if len(node.keys) > MAX_KEYS:
            return self._split(pid, node)
        self.pager.write_page(pid, node.pack())
        return None

The return None on the third line is the whole write-amplification story of a B-tree. An insert reads a page at every level, but it only writes the pages it changed — usually just the leaf. If nothing below split, this internal node's bytes are unchanged and rewriting them would be a page of I/O for no reason. I checked what it saves:

Identical file, 2.9× the writes. So this line is worth nothing to correctness and a great deal to I/O — which is exactly the kind of line worth knowing about before you "simplify" it away. 104,673 writes for 100,000 inserts is close to the floor of one per insert, and the excess decomposes exactly: 1 initial root page + 100,000 leaf writes + 2,336 splits (2 writes each, replacing the 1 they'd have done) + 2,334 parents that absorbed a split without splitting themselves + 2 root growths = 104,673.

len(node.keys) > MAX_KEYS also deserves a look: the node is allowed to become overfull in memory and is split afterwards. Insert-then-split is several lines shorter than checking for room first, and since the page is only ever written after the check, an over-63-key node never reaches disk.

5.7 _split — the four lines the whole demo is about

    def _split(self, pid, node):
        """Halve an overfull node in place; the new right half gets a fresh pid."""
        mid = len(node.keys) // 2
        sep = node.keys[mid]
        if node.leaf:
            # The separator is *copied* up: a B+tree keeps every key in a leaf.
            left = Node(True, node.keys[:mid], node.kids[:mid])
            right = Node(True, node.keys[mid:], node.kids[mid:])
        else:
            # The separator *moves* up; the children either side of it split.
            left = Node(False, node.keys[:mid], node.kids[:mid + 1])
            right = Node(False, node.keys[mid + 1:], node.kids[mid + 1:])
        rpid = self.pager.alloc()
        self.pager.write_page(pid, left.pack())
        self.pager.write_page(rpid, right.pack())
        return sep, rpid

Leaves copy the separator up; internal nodes move it. Look at the slices: the leaf's right starts at keys[mid:], so sep is still in the leaf and now also in the parent. The internal node's right starts at keys[mid + 1:], so sep has left this level entirely. That difference is the difference between a B+tree and a B-tree, and getting it wrong loses data the same silent way §5.4 did:

(A real B-tree stores a value alongside the separator in the internal node, so nothing is lost. Dropping the value while moving the key, as the variant does, is the mistake — and it costs you one key per split.)

Note also that left is written back to the same page id. A split creates exactly one new page, not two, so the parent's existing downlink stays valid and only one new pointer has to be threaded in.

6. The demo, and what it proves

demo.py builds two indexes over the same key set. The only difference is the order the keys arrive in:

    ascending = list(range(N))
    shuffled = list(range(N))
    random.Random(SEED).shuffle(shuffled)

Both files are real; the demo leaves ascending.idx and random.idx behind so you can ls -l them.

python3 demo.py

The sorted load lost. Not marginally: 38% more pages (3222/2339 = 1.3775) and 33% more page reads on every lookup for the life of the index (4/3 = 1.3333). Sorting your load file made your queries slower.

6.1 Where the 50.8% comes from

Ascending inserts only ever touch the rightmost leaf — every new key is larger than every key already in the tree. So:

1. The rightmost leaf fills to 63 keys.
2. The 64th key overflows it. mid = 64 // 2 = 32, so it splits 32/32.
3. The left half is now closed forever. No key smaller than its largest will ever arrive again, so nothing will ever be inserted into it. It is frozen at 32 of 63 slots.
4. The right half becomes the new rightmost leaf. Go to 1.

Every leaf is sealed at exactly 32 keys the moment it stops being the rightmost one. 32/63 = 0.507936…, and test_sorted_load_builds_a_worse_index asserts the measured fill is exactly 32/63, not approximately.

The leaf count falls straight out. Splits happen at inserts 64, 96, 128, …, i.e. at 64 + 32k. Since 100000 = 64 + 32 × 3123, the hundred-thousandth insert is itself a split, and the tree ends with 2 + 3123 = 3125 leaves — which is precisely what the demo prints, and 3125 × 32 = 100,000 accounts for every key.

6.2 Where the 69.8% comes from

Random inserts land all over the tree, so a leaf that split is just as likely to be inserted into again as any other. A leaf therefore lives between 32 and 63 keys, and the average across a large tree converges to a famous constant: ln 2 = 0.693…, the classic result for B-trees built by random insertion (Yao, On Random 2-3 Trees, Acta Informatica 9, 1978).

That is not a hand-wave here. test_sorted_load_builds_a_worse_index builds 20,000 shuffled keys and measures a fill of 0.69314480 against ln 2 = 0.69314718 — agreement to six decimal places, on a tree of 458 leaves. The 100,000-key run in the demo sits a little higher at 69.8%, which is the usual sampling wobble at a particular N; the test asserts the convergence at the N where it is cleanest.

So: 32 keys per leaf versus ~44. 3125 / 2275 = 1.374, and there is the 37% extra pages.

6.3 How fill turns into height

Pages are cheap; a level is not. The extra level is what makes this permanent.

The root can hold 64 children. Each level-1 node, once closed by an ascending 50/50 split, holds 33 children (an internal node overflows at 64 keys/65 children and splits into 32 keys/33 children plus 31 keys/32 children). Each closed leaf holds 32 keys. So a height-3 ascending tree tops out at roughly:

Measured crossing: 68,608. The 1,024-key gap is the right-hand spine, whose nodes are still filling toward 64 children rather than sitting at the closed 33 — 1,024 keys is exactly 32 more leaves' worth, and the ascending tree only ever has one partially-filled node per level.

Compare against §5.1's table: a packed height-3 tree holds 258,048 keys. The ascending tree gives up at 68,608 — 26% of the theoretical capacity, because it filled everything to about half and half-filling twice over (leaves and internal nodes) compounds.

The random tree, at 69.3% fill on both levels, keeps going. I ran the sweep to find out how far:

100,000 sits between the two. That is why the demo shows 4 reads versus 3.

6.4 The boundary condition — when the height gap vanishes

From the two measured growth lists:

The gap holds for 613 + 79,466 = 80,079 of the first 148,073 values of N, or 54% — a coin flip. Pick N = 50,000 and the demo's headline evaporates: both trees are height 3 and every lookup costs 3 reads in both. Pick N = 100,000, as the demo does, and it is stark.

What does not vanish at any N is the size: the ascending index is ~38% bigger, always, because 32/63 versus ln 2 is a ratio, not a threshold. Every one of those extra pages is a page of buffer pool the index will occupy forever, evicting something else. The height penalty is intermittent; the memory penalty is permanent. Do not carry away "sorted inserts cost you a level" — carry away "sorted inserts waste a third of your index, and at some values of N that also buys you a level."

6.5 Why 3 page reads and 75 comparisons beats 17 and 17

Section (4) of the demo is the second measured fact, and it is the one that explains why B-trees exist at all.

Every one of the 100,000 lookups against the random index cost exactly 3 page reads — the reads/lookup column is a single value, not a range, because get never backtracks. The comparisons ranged from 4 to 157, average 75.1. The upper bound is 3 nodes × 63 keys + 1 equality test = 190; 157 is what a real linear scan through mostly-69%-full nodes actually costs.

A balanced binary tree over the same 100,000 keys does log₂(100000) = 16.6, call it 17, of each. So relative to the BST the B+tree does:

The B+tree wins as long as one page read costs more than 4.3 key comparisons. That is the entire argument, and it needs no hardware numbers to be convincing — a page read involves a syscall at absolute minimum, and an integer comparison is a single instruction. Published latency figures put a random SSD read in the tens of microseconds and an integer comparison in the nanoseconds, three to four orders of magnitude apart (I did not measure those here; the break-even ratio above is the part derived from this toy). The B-tree is not winning by 20%. It is winning by four orders of magnitude of margin on a threshold of 4.3.

One inversion worth noticing, because it looks like a contradiction: the ascending index does fewer comparisons (62.0) than the random one (75.1), while doing more page reads. Its nodes are half empty, so there is less to scan in each one — 62.0/4 = 15.5 comparisons per node against 75.1/3 = 25.0. It is a perfect illustration of the trade the whole structure is built on: the sorted index optimised the free resource and paid in the expensive one.

6.6 The output is reproducible, and so are the files

python3 demo.py > run1.txt; shasum -a 256 ascending.idx random.idx
python3 demo.py > run2.txt; shasum -a 256 ascending.idx random.idx
diff run1.txt run2.txt && echo IDENTICAL

Both index files are byte-identical between runs. The only randomness in the toy is random.Random(42).shuffle in demo.py; page ids come from a monotonic allocator, !-prefixed structs remove any machine dependence, and padding is explicit zeros. If you get different digests, something in this page is wrong and you should trust your run.

6.7 The tests

python3 test_btree.py

test_sorted_load_builds_a_worse_index is §6 shrunk to 20,000 keys so it runs in two seconds. It asserts the exact 32/63 fill, the ln 2 convergence, and the page counts — and it asserts that at 20,000 keys both trees are height 3, so the test itself refuses to let §6.4's threshold caveat rot.

7. Design decisions and roads not taken

7.1 Linear scan inside a node, not binary search

The obvious criticism of scan is that it is O(63) where bisect is O(log 63). It is also, on this evidence, not worth fixing. I swapped it for a hand-written binary search that counts every real comparison, and ran the same 10,000 lookups:

572,136 comparisons eliminated — 4.2× fewer — and the tree, the page reads and the wall clock are all unchanged. The 0.45s/0.40s above is not a real 0.05s saving; it is noise. Repeating the pair four more times:

Linear ranged 0.43–0.51s and binary 0.43–0.46s; on the third pair the binary search was slower. Deleting three quarters of the comparisons is unmeasurable. In this toy the cost is Node.unpack decoding 63 structs per page, and the comparisons are lost in the noise beside it. That is §6.5's point arriving from the other direction: comparisons really are the cheap resource.

Linear stayed because it makes the comparison count countable — scan returning its own comparison total is what makes the second half of §6 possible. Real engines do use binary search (Postgres's _bt_binsrch), for a reason this toy can't show: with 8 KiB pages and hundreds of keys per node, the constant stops being invisible.

7.2 The 50/50 split, and the heuristic that fixes it

This is the counterfactual that carries the whole page, so I built it. The variant keeps everything else identical and changes one rule: if the overfull leaf is the rightmost one — the key just inserted is its largest — split 63/1 instead of 32/32.

That inverts the entire result. The ascending load goes from the worst index in the experiment to the best one: height 3, 1,637 pages, 100% leaf fill — half the pages of the 50/50 ascending build and 30% fewer than the random build. And the random load barely notices (2,365 pages against 2,339, a 1% regression), because its overfull leaf is almost never the rightmost one.

So a heuristic that costs one comparison, applies to a fraction of splits, and cannot meaningfully hurt anyone, turns the worst case into the best case. Which is exactly why Postgres has it. From nbtsplitloc.c:

If the page is the rightmost page on its level, we instead try to arrange to leave the left split page fillfactor% full. […] when we are inserting successively increasing keys (consider sequences, timestamps, etc) we will end up with a tree whose pages are about fillfactor% full, instead of the 50% full result that we'd get without this special case.

"Instead of the 50% full result" is the number in the demo's first table, named in the source of a production database. Postgres's default fillfactor is 90 rather than my variant's 100, which leaves slack for the occasional out-of-order insert; CREATE INDEX documents it as applying "when extending the index at the right (adding new largest key values)."

The toy keeps the naive 50/50 split. The whole point is to see the failure that the heuristic exists to prevent, and a toy that quietly fixes it teaches you nothing about why real B-tree code has a special case for the right edge.

7.3 B+tree, not B-tree

A plain B-tree stores values in internal nodes too. A B+tree keeps every value in a leaf and uses internal nodes purely as a routing directory. Two consequences, both visible in _split (§5.7):

• Internal nodes carry only (key, child_pid) — 16 bytes here, but in a real index with a wide row pointer it means far more keys per interior page, so a shallower tree.
• Every lookup costs exactly height reads, never fewer. A B-tree can get lucky and find a key in the root. That sounds like a win and isn't: it makes latency variable, and it means the usual case is deeper.

Essentially every database index is a B+tree, for the first reason.

7.4 No page cache

Adding a buffer pool would be twenty lines and would destroy the measurement (§5.2). More importantly, it would change what the toy is about: with a cache, the interesting number becomes hit rate, which is a different mechanism with its own trade-offs. reads here is a count of logical page fetches, which is the number a query planner reasons about, and the one that scales with height.

7.5 Fixed-width 64-bit keys

Real indexes key on strings, composite tuples, and NULLs, and every one of those forces variable-length records, a slot array with pointers into a cell heap, and a "does this still fit" calculation on every insert. That is where most of a real B-tree implementation's code lives (see SQLite's cell format, §10) — and none of it is the mechanism this toy is about. One struct and one record format is what keeps the file at 194 lines.

The cost is honest and worth stating: with variable-length keys, "the node is full" stops being len(keys) > 63 and becomes a byte-budget question, and the split point stops being len // 2 and becomes a search for the byte-wise midpoint. Postgres's nbtsplitloc.c is 1,200 lines almost entirely because of this.

8. What's simplified vs. the real thing

• No delete. The biggest cut. A real B-tree deletes keys, and when a node falls below half full it must merge with a sibling or redistribute keys from one — the mirror image of splitting, and roughly as much code again. This is why stats()["pages"] in this toy can only ever grow: page ids come from a monotonic counter with no free list, so even if deletion existed there would be nothing to reuse the space. Real engines keep a free-page list in the file itself, which is why a Postgres index does not shrink on DELETE — the pages are recycled internally, not returned to the filesystem, and getting the space back needs REINDEX.
• No leaf sibling pointers. A real B+tree chains its leaves into a doubly linked list, which is what makes WHERE id BETWEEN 10 AND 500 a descent plus a linear walk instead of 490 descents. It is two extra fields in the page header and it is the single most valuable thing a B+tree does that a hash index cannot. Left out because range scans are a second mechanism.
• No concurrency. insert is not safe against a concurrent reader for one page, let alone a split cascading up three levels. Real implementations use latch coupling (lock the child before releasing the parent) or the Lehman-Yao B-link tree, which adds a right-link to every node so a reader that arrives mid-split can follow it sideways instead of blocking. Postgres uses B-link trees for exactly this.
• No WAL, no fsync. A crash mid-split leaves a torn index: the new right page written, the parent's downlink not. Real engines log the split atomically. This toy would simply lose the keys.
• No buffer pool. Every read is a real pread. In practice the root and most of level 1 are permanently cached, so a "3-read" lookup is usually one physical read. The height still matters — it is the number of cache lookups plus latch acquisitions — but the disk cost is not 3× the leaf cost.
• One key type, no NULLs, no duplicates. A duplicate insert overwrites (§5.6). Real indexes support duplicate keys, which needs a tie-break — Postgres appends the heap TID to the key — and then needs a special split strategy so a million equal keys don't produce a million half-full pages.
• No metadata page. The root page id lives in the Python object, so the file cannot be reopened. Every real format reserves page 0 for a header naming the root; SQLite's is the first 100 bytes of page 1. Left out because it would put a fourth read in front of every lookup in the toy and muddy the headline number.

9. Check yourself

Answer before expanding. Each answer is derivable from the source, and each was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written. Three candidates were dropped: postgresql.org/docs/current/btree-implementation.html (404), and the ACM Digital Library and Springer pages for the occupancy results, which return 403 / paywall redirects to an unauthenticated fetch — Yao 1978 and Wright's Acta Informatica analysis are cited above by reference rather than by link for that reason.

• PostgreSQL nbtsplitloc.c — the single most relevant file to this page: production code choosing a split point, with the rightmost-page special case quoted in §7.2 and a separate strategy again for pages full of duplicates. Read the header comment even if you read nothing else.
• PostgreSQL nbtree/README — the design document for a real B+tree: Lehman-Yao right-links for concurrency, "the smallest split point available within an acceptable range of the fillfactor-wise optimal" one, and the cached-insertion-page optimisation for increasing keys. This is §8's list of omissions, written by people who couldn't omit them.
• PostgreSQL CREATE INDEX — fillfactor — the knob, from the user's side. Default 90 for B-trees, and the sentence that matters for §6: leaf pages are filled to it "when extending the index at the right (adding new largest key values)."
• PostgreSQL pgstattuple / pgstatindex — how to measure §6 on your own indexes. avg_leaf_density is this toy's "avg leaf fill", tree_level is its height, and leaf_fragmentation is the thing this toy cannot show because it never deletes.
• PostgreSQL docs: B-Tree implementation — the user-facing description of the same structure: metapage, leaf and internal pages, cascading splits, plus bottom-up index deletion and deduplication, two mechanisms this toy has no equivalent of.
• SQLite database file format §1.6, B-tree Pages — the counterpoint to §5.3. A real page format: a one-byte type flag (0x0d leaf, 0x05 interior), a cell-pointer array, variable-length cells growing from the end, and overflow pages. Compare it against Node.pack to see precisely what fixed-width records bought and cost.
• Wikipedia: B+ tree — the formal treatment, including the split arithmetic (⌈(K+1)/2⌉ and ⌊(K+1)/2⌋ items) that mid = len(node.keys) // 2 implements, and the leaf linked list §8 leaves out.
• Markus Winand: Use The Index, Luke — The B-Tree — the best short explanation of why tree depth barely matters and leaf traversal does. Written for people tuning queries rather than writing storage engines, which makes it the right next stop if this toy made you want to look at a real EXPLAIN.