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

Find the row — why a file scan won't do — point, range and indexed lookups in one file

A SQL engine has to answer point, range, and indexed lookups against ONE file — the only family of structures that can do all three is an ordered tree.

Scene 01

Find the row — why a file scan won't do

  1. Watch
  2. Try it
  3. Predict
  4. Capture
FILEusers.dblayout: unsorted (hash-like)#17grace#3bob#22judy#8#1alice#14frank#24ken#5carol#19ivy#11eve#7dan#21#4#16#2#23#9#13#6#20#18#10#15#12POINTSELECT * FROM users WHERE id = 14point lookup by primary key0 scannedRANGESELECT * FROM users WHERE id BETWEEN 5AND 120 scannedINDEXEDSELECT * FROM users WHERE email ='eve@x'0 scannedROWS SCANNED0 / 24Three queries, three full scans. Cost is N for every shape.
users.db — one file, every row of the users table
point: one row by PK
What to watch for

Three queries fire one after another — point, range, indexed. Watch the cursor walk every row in the file for each one. The counter tells you the cost.

Continue unlocks when the animation finishes.
Implementation

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

select_row(file, target_id)
unsorted users.db: every query walks every cell
def select_row(file, target_id):
    # no order to exploit — read the cells in disk order
    for cell in file.cells:           # O(N) page reads
        if cell.rowid == target_id:
            return cell.row           # point hit (still scanned)
    return None                       # range / indexed: full file
insert_row_into_sorted(file, row)
sorted-flat users.db: log-N to find, but N to make room
def insert_row_into_sorted(file, row):
    # file is kept in PK order on disk
    pos = bisect_left(file.cells, row.rowid)   # O(log N)
    # make room at pos by sliding the tail one slot right
    for i in range(len(file.cells) - 1, pos - 1, -1):
        file.cells[i + 1] = file.cells[i]      # O(N) writes
    file.cells[pos] = row
    file.length += 1
Sources

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

Scene 01 of 11, in the The brief act — Why a flat or sorted file isn't enough.. A SQL engine has to answer point, range, and indexed lookups against ONE file — the only family of structures that can do all three is an ordered tree.

Up next. We've decided we need an ordered structure inside the file. But what is the file even, physically? Not bytes addressed individually — the next scene reveals it's a strip of fixed-size pages.

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