B+Tree Leaf Node and INSERT

Why this stage exists

You can turn a row into 60 bytes, and you can keep pages in a file across restarts. Nothing connects the two yet: an INSERT has nowhere to go. This stage gives it a place. Page 0 becomes a leaf node, the bottom level of the B+Tree the next stages grow, and INSERT puts each row into it as a cell.

A leaf is the smallest tree there is: one node, no children. It is still worth building as a tree node from the start, because everything that comes later works on the same page layout. The next stage keeps the cells sorted and finds keys by binary search. The stage after it splits a full leaf in two and adds the first internal node above them. None of that changes how a leaf stores its cells, which is what you build now.

What changes: a page with a header and cells

Until now a page was 4096 bytes with no meaning. A node page has a structure: a header of 14 bytes that says what kind of node the page is and how full it is, then the cells, one after the other.

Every number is an unsigned integer with its least significant byte first, like id in the row format. The key is the row's id, stored once more in front of the row. That looks redundant, and it is what lets a tree compare keys without knowing anything about rows.

This is page 0 after inserting (2, 'bo', 'b@e') and then (5, 'dan', 'd@e'): the header, and the first of the two cells.

The root, and when it is created

The root of the tree is always page 0. That is a rule, not an accident: every search starts at the root, and a fixed page number means the program never has to look up where the root is.

Page 0 does not exist in a new file, and opening the file does not create it. The root is created the first time a command needs the tree: btree dump or an INSERT. Before that, pager status still reports total_pages=0, exactly as in the pager stage.

The rule that matters most is the other half: the root is created only when the file has no pages. A file with pages already has its root, with its cells in it. A program that writes an empty leaf into page 0 at every start works perfectly in one session and empties the table at every restart.

INSERT, from statement to cell

An INSERT goes through every layer you have built. The parser gives you the table, the columns and the values. Then come the checks this stage adds: the table must be users (00401), each column must be id, name or email (00402), and id must be there (00406). A column that is left out is an empty string. The row format's checks follow, as in the row-serialization stage: 00403 for a value of the wrong type, 00404 for an id out of range, 00405 for a string of more than 27 bytes. Last comes the leaf's own check, below: it must have room for one more cell.

Only then does anything change. The row is serialized, the cell goes in at the position the count gives, the count grows by one, and the program prints Insert statement executed successfully. Every check comes before the page changes, which is what makes "a failed statement changes nothing" easy to keep true.

In this stage a new cell simply goes after the last one, so the cells are in the order the rows arrived. The next stage keeps them sorted by key.

How many cells fit

A leaf holds at most 8 cells in this tutorial. That is a test-mode number, chosen so a full leaf takes eight inserts and a test that fills one runs in an instant.

The 9th INSERT into a full leaf is error 00702, and it changes nothing: the leaf still holds 8 cells and the row is not stored anywhere. That is a temporary answer. From btree-leaf-split on the leaf splits instead, and 00702 is no longer what a 9th row gets.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 3, 6, 9 and 10, including the page layout above.

There are three spaces between [BTREE] and Cell. The page in the file is part of the contract too: the header and cells laid out as in the table above, so the tests read the file to check a row really is where the layout says.

What you should see when done

$droid --db users.db
Welcome to droid!
>pager status
[PAGER] Status: total_pages=0 cached=0
>insert into users (id, name, email) values (1, 'ada', '[email protected]');
Insert statement executed successfully
>insert into users (id) values (2);
Insert statement executed successfully
>insert into people (id) values (3);
[ERROR:00401] Unknown table: people
>insert into users (id, name, email) values (4, 'abcdefghijklmnopqrstuvwxyz01', 'x');
[ERROR:00405] name is 28 bytes, at most 27 fit
>btree dump
[BTREE] Page 0: type=LEAF num_cells=2
[BTREE]   Cell 0: key=1 (60 bytes)
[BTREE]   Cell 1: key=2 (60 bytes)
>pager status
[PAGER] Status: total_pages=1 cached=1
>.exit
exiting.. good bye!
$droid --db users.db
Welcome to droid!
>pager status
[PAGER] Status: total_pages=1 cached=0
>btree dump 0
[BTREE] Page 0: type=LEAF num_cells=2
[BTREE]   Cell 0: key=1 (60 bytes)
[BTREE]   Cell 1: key=2 (60 bytes)
>.exit
exiting.. good bye!

The first INSERT created page 0; before it, there were no pages. The two failed INSERTs left no trace in the leaf. The second session found one page in the file, read nothing until btree dump needed page 0, and found both rows still there. The error messages are yours to word; the tests check only the codes.

Common bugs in this stage

• Resetting the root at every start. Writing an empty leaf into page 0 whenever the program opens the file. Every single-session test passes and the second session shows num_cells=0. Create the root only when the file has no pages.
• Creating the root when the file is opened. Then a fresh database reports total_pages=1 before anything has used the tree. Create it when a command first needs it.
• Changing the page before the checks. Writing the cell, or adding to the count, and then finding the name too long. Do every check first; an error leaves the page alone.
• Cutting a long string to fit. A 28-byte name is 00405. Storing its first 27 bytes quietly changes the user's data.
• Forgetting that the page changed. The cell is in memory and never reaches the file, because the page was not marked as changed. The persistence stage saves pages allocated or written in the session; an INSERT writes to page 0.
• Cells overlapping the header. Putting cell 0 at byte 0, or at the size of some structure in your language, which may include padding. Cell i starts after the 14-byte header, 64 bytes after cell i − 1.
• A signed key. Id 4294967295 printed as -1. The key is unsigned, like id.
• Letting the 9th cell in. A leaf of 4096 bytes has room for 63 cells, so nothing breaks at the 9th unless you check. The limit is 8.
• Big-endian or native byte order. The counts and keys are least significant byte first on every machine, like id in the row format.

Language notes

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

• C and C++: a struct laid over the page is tempting, but the compiler adds padding: a struct with a 1-byte field followed by a 4-byte field is usually 8 bytes, not 5. Read and write each field at its offset instead, with memcpy into and out of a fixed-width integer, and convert the byte order if your machine is not little-endian.
• Rust: u32::from_le_bytes and to_le_bytes over slices of the page read and write each field. u32::try_from on the parsed id rejects values past 4294967295.
• Zig: std.mem.readInt(u32, page[6..10], .little) and std.mem.writeInt read and write a field at its offset in the given byte order. An extern struct laid over the page has C layout, padding included, so reading each field at its offset is the simpler path.
• Every language: keep the offsets in named constants, one per field, and derive the cell offset from them. A layout written as numbers in several places drifts.