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

Indexes — a second B-tree — two descents per read and write amplification

Each CREATE INDEX builds a second B-tree; reads do TWO descents, but every write must update every index.

Previously

We've covered the table B-tree end-to-end — one tree per table, growing on insert and not shrinking on delete. CREATE INDEX builds another one beside it, and that 'beside it' is where both reads and writes get more interesting.

Scene 06

Indexes — a second B-tree

  1. Watch
  2. Try it
  3. Predict
  4. Capture
table B-tree (rowid → row)ROOTp1 rootINTp4INTp5LEAF p17#41 bob#42 aliceLEAF p18#73 carol#74 daveLEAF p19#88 erin#91 frankindex B-tree on emailROOTp21 rootINTp22INTp23LEAF p31alice@x →…bob@x → #…LEAF p32carol@x →…dave@x → …LEAF p33erin@x → …frank@x →…WRITE AMPLIFICATION2× B-trees / INSERT1 table + 1 indexTHROUGHPUT50%insert latency: ~60 µs/INSERT (2× descents)1 secondary index — every write hits 2 trees.SELECT WHERE email='alice@x' = two trees, two descents.
What to watch for

SELECT WHERE email='alice@x' fires. Watch the cursor descend the email index, find rowid=42, then cross to the table tree and descend again to fetch the row.

Continue unlocks when the animation finishes.
Implementation

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

SELECT WHERE email = ?
two-tree read path: index descent, then table descent
def select_by_email(email):
    # 1. Walk the index B-tree; leaf cells = (email, rowid).
    rowid = index_tree.find(email)   # ~3 page reads
    if rowid is None:
        return None
    # 2. Walk the table B-tree by rowid to fetch the row.
    return table_tree.find(rowid)    # ~3 more page reads
INSERT INTO users(...)
write path fans out across the table tree + every index
def insert(row):
    # 1. Always: insert into the table B-tree (keyed by rowid).
    table_tree.insert(row.rowid, row)
    # 2. For EVERY secondary index, insert (col_value, rowid).
    for idx in secondary_indexes:        # runs N times
        # index leaf cell = (col_value, rowid) — no payload.
        idx.tree.insert(
            key = (row[idx.col], row.rowid),
            payload = None,
        )
    # B-trees touched per INSERT = 1 + N (write amplification).
Tree.insert (per B-tree)
what every one of those N+1 trees runs on each INSERT
def insert(key, payload):
    # 1. Descend interior pages to the target leaf.
    leaf = root
    while leaf.kind == 'interior':
        leaf = leaf.child_for(key)   # ~log_B(rows) page reads
    # 2. Insert the new cell in key order on the leaf.
    leaf.insert_cell(key, payload)
    # 3. If the leaf overflows, split and propagate upward.
    if leaf.bytes_used > PAGE_SIZE:
        split_and_propagate(leaf)    # may grow the tree
Sources

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

Scene 06 of 11, in the Indexes act — Every CREATE INDEX is a second B-tree to keep current.. Each CREATE INDEX builds a second B-tree; reads do TWO descents, but every write must update every index.

Up next. Now we know what one write costs in trees. But every page touch in this scene was treated as a real disk I/O — the next scene introduces the page cache that turns most of those reads into RAM accesses.

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