File Header and Many Trees

Why this stage exists

Until now page 0 has done two jobs without saying so. It is the root of the only tree, and it is the only way to know where that tree starts. Both are about to stop being enough.

The next stage creates tables. Each table is a tree, and each tree has a root somewhere in the file. Something has to record where. A fixed page cannot: two trees cannot both have their root at page 0. The file needs one place, at a known offset, that says what is in it.

And a file needs to say what it is. Point the program at a text file whose size happens to be a multiple of 4096, and today it reads the first page as a leaf, finds nonsense, and does whatever nonsense makes it do. Every real storage format starts with a few bytes that identify it, so a program can refuse a file it does not understand before trusting anything in it.

This stage makes page 0 that header. It is small: a magic string, a version, the page size and one root. The root moves to page 1 on a fresh file, and every rule that said "page 0" about the root now says "the page the header records".

What changes: page 0 is the header

When it is written. The header appears the first time the file needs any page at all. pager alloc on an empty file writes the header into page 0, then allocates the page it was asked for, so it prints page 1 and leaves two pages. An INSERT on an empty file writes the header, then the root leaf, page 1. A session that allocates nothing, pager status on a new file for instance, still leaves the file empty: opening never writes.

When it is read. Every open of a file that has pages reads page 0 and checks three fields. A wrong magic, a version other than 1 or a page size other than 4096 means this is not a file this program can read: 00608, printed before the welcome line, as the only line, with exit status 1, and the file untouched, like the other files the persistence stage refuses. Because opening now reads page 0, a session on an existing file starts with cached=1.

What changes: the root is a recorded page

The users tree's root is the page in the header's root field. While that field is 0 there is no tree yet; the first command that needs one allocates a root leaf and writes its page into the field. On a fresh file that is page 1.

Everything the B+Tree stages said about page 0 now holds for that page instead. It is the only node with is-root 1, and its parent field is 0. When it splits it keeps its page: its halves go to two new pages and it becomes the internal node over them.

That is the invariant this stage replaces "the root is always page 0" with: a tree's root is the page its record names, and that page never changes. A split of the root leaf, a split of the root internal node that makes the tree deeper, a restart, deletes: none of them moves it. The header is written once for the root and never needs to be written for it again.

Copy-on-write engines such as LMDB do the opposite: every change writes a new root, and the header is updated to point at it. SQLite keeps a table's root page fixed, as this tutorial does, so its catalog never has to change while a table grows.

Pages are still never freed. A deleted row leaves room in its leaf, but no page goes back to the file. A header with a list of free pages arrives with DROP TABLE, which is the first thing that can empty a page for good.

What changes: tree commands name a table

btree structure and btree find take a table name as their first word when it is not digits: btree structure users, btree find users 2. Without one they mean users, so every earlier command still works. A name that is not a table is 00401, the same code SQL uses. That changes one answer: btree find abc used to be 00104, a key that cannot be an id, and is now 00401, a table that does not exist. With a table named, a bad key is still 00104. Until the next stage users is the only table, but the commands are ready for more.

btree dump takes a page, not a table. Without one it dumps the users root. With the header in the file, not every page is a node: btree dump 0 is the header, and a page pager alloc made and nothing wrote is zeros. Both are 00703, a page that is not a B+Tree node. A page past the last one is still 00601.

Output contract for this stage

The full definition is on the output contract page, section 18.

On a fresh file the header is page 0 and the users root page 1, so every page number in btree structure, btree dump, btree find and pager status is one higher than before for the same statements. Earlier cases that assert those numbers, or page 0 as a leaf, are retired here by name in the manifest; everything they checked about SQL still has to pass.

What you should see when done

On a new file:

Welcome to droid!
>pager status
[PAGER] Status: total_pages=0 cached=0
>db header
[DB] Header: magic='droid db' version=1 page_size=4096 root=0
>insert into users (id, name, email) values (1, 'dan', 'd@e');
Insert statement executed successfully (1 rows)
>db header
[DB] Header: magic='droid db' version=1 page_size=4096 root=1
>pager status
[PAGER] Status: total_pages=2 cached=2
>btree structure
[BTREE] Tree depth: 1
[BTREE] LEAF (page=1 cells=1 keys=[1])
>btree find users 1
[BTREE] Find key=1: FOUND (page=1 cell=0)
[BTREE] Row: id=1 name='dan' email='d@e'
>btree dump 0
[ERROR:00703] Page 0 is not a B+Tree node
>btree structure orders
[ERROR:00401] Unknown table: orders
>.exit
exiting.. good bye!

Things to notice. Opening the new file wrote nothing: total_pages=0. db header created page 0 with no tree yet, root 0. The INSERT needed the tree, so it allocated the root leaf, page 1, and recorded it. Page 0 is not a node any more.

Opening the same file again starts with the header already read:

Welcome to droid!
>pager status
[PAGER] Status: total_pages=2 cached=1
>.exit
exiting.. good bye!

And a file that is not a droid database never gets as far as the welcome line:

$droid --db notes.db
[ERROR:00608] Not a droid database: notes.db
$echo $?
1

Common bugs in this stage

• Writing the header on open. Opening an empty file must leave it empty. The header is written by the first allocation, not by the open.
• Allocating the header after the page that was asked for. The first pager alloc of a file is page 1, because page 0 goes to the header first.
• Checking the header after the welcome line. A refused file prints its error and nothing else, like the other files the persistence stage refuses.
• A root that is still page 0 somewhere. The split, the is-root flag, the parent field, btree dump with no page, the cursor that starts a scan: each of them used to know the root was page 0. Read the root from the header everywhere, or one of them walks into the header.
• Moving the root on a split. The root keeps its page; its halves go to new pages. Copying the root's cells to a new page and pointing the header at it breaks the invariant the tests check.
• Forgetting cached=1. Opening reads page 0, so it is in memory from the start.
• Reading page 0 as a node. btree dump 0 is 00703 now, not a leaf full of odd numbers.

Language notes

The page above is the same for every language. These are the only language-specific hints.

• C and C++: a packed struct for the header is tempting; write and read the fields one by one at their offsets instead, as the other pages do, so padding and byte order never surprise you. memcmp checks the magic.
• Rust: u32::from_le_bytes reads a field from a four-byte slice of the page, and comparing a slice with a byte-string literal checks the magic.
• Zig: std.mem.readInt with .little reads a field, and std.mem.eql checks the magic.