Make page 0 a file header: a magic string, a version, the page size and the page of the users tree's root. Write it on the first allocation, check it on every open, and find the root through it instead of assuming page 0. Let the tree commands name the table they work on.
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".
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.
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.
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.
Page 0 is written once, the first time the file needs any page.
droid db, version 1, page size 4096, root 0, zeros after them. Then allocate the page that was asked for, page 1.A file that has pages must say it is a droid database.
droid db, a version other than 1 or a page size other than 4096 is 00608: the only line printed, exit status 1, the file untouched.cached=1.Every rule that said page 0 now says the recorded root.
The tree commands learn which tree they work on.
The full definition is on the output contract page, section 18.
| Input | Output |
|---|---|
db header | [DB] Header: magic='droid db' version=1 page_size=4096 root=<p> |
pager alloc on a file with no pages | [PAGER] Alloc: page 1 (4096 bytes, zeroed), and total_pages=2 after it |
| opening a file whose page 0 is not a droid header | [ERROR:00608] <message>, the only line, exit status 1 |
btree structure [table], btree find [table] <key> | as before, for that table's tree; 00401 for a table that does not exist |
btree dump of a page that is not a node | [ERROR:00703] <message> |
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.
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>.exitexiting.. 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>.exitexiting.. 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
pager alloc of a file is page 1, because page 0 goes to the header first.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.cached=1. Opening reads page 0, so it is in memory from the start.btree dump 0 is 00703 now, not a leaf full of odd numbers.The page above is the same for every language. These are the only language-specific hints.
memcmp checks the magic.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.std.mem.readInt with .little reads a field, and std.mem.eql checks the magic.