The page cache — RAM is 1000x faster than disk

The pager keeps a fixed-size LRU cache of pages in RAM; you're fast iff the working set fits, slow the moment it doesn't.

Previously

Every B-tree descent we drew assumed each page touch hit the disk. In reality the pager keeps recent pages in RAM — and that one fact rewrites the cost model for everything we've built so far.

Scene 07

The page cache — RAM is 1000x faster than disk

Watch
Try it
Predict
Capture

What to watch for

We run the same 3-page B-tree descent twice. First run: cold cache → 3 misses → ~30 ms total. Second run: same path → 3 hits → ~3 µs total.

Implementation

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

Pager.read_page(page_no)

the only routine the B-tree ever uses to touch a page

1def read_page(page_no):
2    if page_no in cache:
3        page = cache[page_no]            # HIT: ~1 us, RAM
4        touch_lru(page_no)               # mark as MRU
5        return page
6    # MISS: page is not resident
7    if len(cache) >= cache_size:
8        evict_lru(cache)                 # make room
9    page = disk_read(page_no)            # ~10 ms, syscall
10    cache[page_no] = page
11    touch_lru(page_no)
12    return page

evict_lru(cache)

drop the least-recently-used page to make room

1def evict_lru(cache):
2    victim = pick_least_recently_used(cache)
3    del cache[victim.page_no]
4    return victim

Sources

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

Scene 07 of 11, in the Speed & durability act — Page cache, WAL+fsync, and the checkpoint that keeps WAL bounded.. The pager caches pages in RAM with LRU; you're fast iff the working set fits, slow the moment it doesn't.

Up next. RAM makes reads (and dirty writes) blazing fast. But cache is not durability — a crash wipes RAM. Next scene: WAL + fsync, the trick that turns cache writes into durable commits without rewriting the file every time.

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