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

Pages linked into a tree — branching factor of hundreds across three levels

Pages are linked into a tree where leaves hold rows and interior pages hold keys + pointers — branching factor is hundreds, so 3 levels reach about 64 million 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

  1. Watch
  2. Try it
  3. Predict
  4. Capture
B-TREE — depth 3page strip — same pages from scene 2ROW CAPACITYmax_rows = B^depthB = real branching factordrawn B = 5real B = 5depth = 11max_rows ≈48.8Mrows addressable in 11 page readsDEPTH METER11 levelsB=5: ~11 levels for 16M rows. S…Same pages from scene 2, now arranged as a tree.
What to watch for

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.

Continue unlocks when the animation finishes.
Implementation

Highlighted lines are the ones running in the diagram right now.

Page anatomy
What a B-tree page actually holds.
Page = {
    type: "interior" | "leaf",  # 0x05 / 0x0d header byte
    page_no: int,
    keys: [int],                # rowid separators, sorted
    # interior pages: pointers down to children
    children: [page_no],        # len(keys) + 1 child slots
    # leaf pages: actual rows live here
    rows: [(rowid, payload)],
}
 
# 4 KB page, ~10 B per interior cell ->
#   B = floor(page_size / cell_size) ~= 400 children
depth_for(N, B)
Side-panel formula: depth = ceil(log_B(N)).
def depth_for(N, B):
    # Each interior level multiplies reachable rows by B,
    # so depth is the exponent that gets B^depth >= N.
    return ceil(log(N) / log(B))
 
depth_for(16_000_000, 2)    # ~24 levels  (binary tree)
depth_for(16_000_000, 5)    # ~11 levels
depth_for(16_000_000, 50)   #   5 levels
depth_for(64_000_000, 400)  #   3 levels  # B=400, 4 KB page
Sources

Where this sits in Build a B-tree storage engine (SQLite-style)

Scene 03 of 11, in the Anatomy act — Pages, the tree of pages, and how a search descends.. 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.

Up next. You can label the tree, but you haven't driven anything through it yet. Next: a SELECT query descends the tree page by page — and the I/O counter stops at 3.

All 11 scenes in Build a B-tree storage engine (SQLite-style) · Every curriculum

Built with Arqly
Every scene in Build a B-tree storage engine (SQLite-style) builds on the one before it.All 11 Build a B-tree storage engine (SQLite-style) scenes