Overflow Pages: Values Bigger Than a Page

A page holds a few thousand bytes, but a row can hold a megabyte of text. If a big value were stored in its page, one row would fill the page and the B-tree would hold one row per node. After this lesson your store keeps a prefix of each value in its cell and puts the remainder in a chain of overflow pages, reads it back by following the chain, and recycles freed pages.

One cell, a prefix, a chain

Two sizes control the layout (CONFIG <local> <chunk>; the defaults are 8 and 16 so tests stay readable):

• local: how many bytes of the value stay inside the cell itself
• chunk: how many bytes each overflow page carries

A value of length n is split like this:

value:  The quick brown fox jumps over the lazy dog      (43 bytes, local 8, chunk 16)

cell:        "The quic"                          first overflow page: 1
page 1:      next=2   "k brown fox jumps"   ... 16 bytes
page 2:      next=3   16 bytes
page 3:      next=0   the last 3 bytes

If n <= local there is no chain at all: CHAIN prints (inline) and no page is used. Otherwise the remaining n - local bytes need ceil((n - local) / chunk) pages. Each page stores its piece of the value and the number of the next page; 0 ends the chain. The cell remembers only the first page. Notice the boundaries: a remainder of exactly chunk bytes uses one page, and one byte more needs a second.

Reading

GET starts with the inline part, then follows next pointers from the first overflow page, appending each page's data until it reaches 0. The order of the pointers is the order of the bytes: that is the invariant to protect when you allocate.

Allocating and recycling pages

Pages are numbered from 1. A new page takes the lowest-numbered free page if there is one; otherwise it takes the next unused number (the file grows by one page). A value's pages are allocated in chain order, so the first piece gets the first page allocated.

DROP frees every page of the chain and removes the cell. A freed page is not erased: it joins the free list, to be reused by a later store. That is how real files avoid growing forever (SQLite keeps a free-page list in its file header). Because the free list is consulted lowest-first, pages freed in any order come back in ascending order. A chain built from reused pages can therefore jump around: 1 -> 2 -> 5. That is normal, and exactly why every page records its own next.

Commands

Common mistakes

• Off by one at the boundary. A value of local + chunk bytes needs one overflow page, not two.
• Linking in the wrong order. If page numbers come from the free list, the chain order is the order of allocation, not numeric order.
• Forgetting to free the last page of a chain, so STATS free is one too low.
• Taking the highest free page instead of the lowest.

Your exercise

The starter does the parsing and printing. You write the five storage functions: alloc_page, free_page, store_value, chain_of, read_value and drop_value. The mistake to avoid: giving each piece the next page number instead of the next page allocated.