Pages linked into a tree

Build a B-tree storage engine (SQLite-style) (11 scenes)

Scene 03 · Pages linked into a tree

Pages are linked into a tree where leaves hold rows and interior pages hold keys + pointers — branching factor is hundreds, so 3 levels = ~64M rows.

Previously

Scene 2 left you with a strip of fixed-size pages — no order between them. Now we link those pages into a tree so you can find any row in a few page reads instead of N.

Scene 03

Pages linked into a tree

Watch

Diagram

A 3-level tree drawn over the page strip from scene 2. Top: one **root page** with separator keys. Middle: **interior pages** (keys + child pointers). Bottom: **leaf pages** holding the actual rows. Each interior page draws ~5 keys for legibility but really holds **branching factor B ≈ 400** of them — the side panel shows max_rows = B^depth.

Sources

The root page lights first, then arrows fan out to interior pages, then those fan out to leaves. Same pages as scene 2 — now they have parents and children.

Implementation

Page anatomy

What a B-tree page actually holds.

1Page = {
2    type: "interior" | "leaf",  # 0x05 / 0x0d header byte
3    page_no: int,
4    keys: [int],                # rowid separators, sorted
5    # interior pages: pointers down to children
6    children: [page_no],        # len(keys) + 1 child slots
7    # leaf pages: actual rows live here
8    rows: [(rowid, payload)],
9}
10 
11# 4 KB page, ~10 B per interior cell ->
12#   B = floor(page_size / cell_size) ~= 400 children

depth_for(N, B)

Side-panel formula: depth = ceil(log_B(N)).

1def depth_for(N, B):
2    # Each interior level multiplies reachable rows by B,
3    # so depth is the exponent that gets B^depth >= N.
4    return ceil(log(N) / log(B))
5 
6depth_for(16_000_000, 2)    # ~24 levels  (binary tree)
7depth_for(16_000_000, 5)    # ~11 levels
8depth_for(16_000_000, 50)   #   5 levels
9depth_for(64_000_000, 400)  #   3 levels  # B=400, 4 KB page

PreviousThe file is a strip of pages NextSearching — a cursor descends the tree