Lesson 02 · An in-memory pager - Build a B+Tree Index

An in-memory pager

Nodes reach each other through a pager, never directly. Today you build the smallest pager - one that hands out page ids and reads and writes whole page buffers - so the tree can allocate and revisit pages without knowing whether they live in RAM or a file.

The goal

Build an in-memory pager whose AllocPage hands out increasing ids and whose ReadPage returns what WritePage stored.

Start here - the target

TO DO

Scenario: Allocate, write, and read back a page

Givena new in-memory pager

WhenAllocPage is called twice

Thenit returns page ids 0 then 1 (increasing, starting at 0)

Andafter WritePage(1, buf) where buf byte 0 is 0x2A, ReadPage(1) returns a buffer whose byte 0 is 0x2A

Background

Every access to a node will go through a pager: allocate a fresh page, read a page by id, write a page by id, and (later) free one. Putting this behind an interface is the pivot the whole project turns on - the core chapters use a simple in-memory pager, and the on-disk chapter swaps in a file-backed one with no change to the tree. Because the tree only ever speaks AllocPage / ReadPage / WritePage, moving to disk is a pager swap, not a rewrite.

The in-memory pager is deliberately dull: keep a slice of page buffers, let AllocPage return the next index and grow the slice, and let ReadPage / WritePage index into it. Ids start at 0 and increase. That id-to-slot mapping is exactly the id-to-offset mapping a file pager will use later, just with a slice standing in for the file.

Make it work

type Pager interface {
  AllocPage() PageID
  ReadPage(id PageID) []byte
  WritePage(id PageID, buf []byte)
  FreePage(id PageID) // used later
}
// in-memory impl: a slice of page buffers, next id = len
type memPager struct { pages [][]byte }

CheckpointDONE

The tree now has a pager it can allocate, write, and read pages through. Commit and stop here.