B+Tree Leaves on Slotted Pages

Why this stage exists

The two previous stages built a row that takes only the bytes it needs and a page that holds records of any length. Neither changed what the database stores: the B+Tree still keeps 64-byte cells, each a key and a 60-byte row, eight to a leaf. This stage puts the pieces together. A leaf becomes a slotted page, and its cells become records of whatever length their rows have.

Two things follow. A leaf no longer holds a fixed number of rows: it holds as many as fit, 140 short ones or four long ones. And the string limit of 27 bytes, which existed only because a field had to be 28 bytes wide, can go. From this stage name and email hold up to 1000 bytes each.

This is also the stage that retires the Core Engine's test-mode leaf. Eight cells per leaf kept the tests small while splitting was new; with capacity in bytes there is no count to shrink, and a leaf is exactly as big as a real one.

What changes: the leaf is a slotted page

A leaf's header is the slotted page's header with type 1. Every field keeps its Core Engine meaning: is-root, the parent, the count of cells, the link to the next leaf. The two bytes after them are the record start. Slot i is cell i, and a cell is the 4-byte key followed by the row:

The slots are sorted; the records are not. Here is a leaf after inserting keys 2, 1 and 3, in that order, with one way the records can land:

Inserting in the middle now moves slots, not rows. Key 2 arriving between 1 and 3:

Full is a number of bytes

A cell needs its record, 4 + row size bytes, and a slot of 4. It fits when the leaf's free space covers both, where free space is everything no header, slot or cell uses: 4080 − the sum of 8 + row size over the cells. That is the only test for full. Rows of 21 bytes take 29 bytes each, so a leaf holds 140 of them and has 20 bytes left, too few for a 141st. Rows of 1000 bytes take 1008, and a leaf holds four.

When the cell does not fit, the leaf splits. Everything about the split is what the Core Engine built: the left half keeps the page (or, for the root, both halves go to new pages), the right leaf takes over the link, the separator is the right leaf's first key. Only the division changes. In this stage any division that leaves both halves non-empty and each fitting its page is right, halving by count included. The next stage, varlen-btree-split, makes it a division by bytes and says why.

The row limit makes splits safe

A split has to put every cell, the new one included, into two pages. That is only always possible if no cell is too large. With rows of at most 1000 bytes, a cell is at most 1004 bytes and needs 1008 with its slot, so any four cells fit in an empty leaf's 4080 bytes. A full leaf plus one new cell always divides into two halves that fit.

So a row over 1000 bytes is refused, with 00407, before the tree is touched. That can happen with both strings inside their own limit of 1000: a 600-byte name and a 400-byte email make a row of 1015 bytes. The first check that fails decides the code: a string over 1000 bytes is 00405, as it always was, and only a row whose strings are each fine but too long together is 00407. An UPDATE that would make a row too large is 00407 too, and changes nothing.

Real engines don't refuse such rows. They store what does not fit on overflow pages and keep only a part in the leaf. That comes later, in Memory and Space. Until then 1000 bytes is the limit.

Delete and update

DELETE removes the cell's slot; the slots after it move up one place, exactly as the cells did in the Core Engine. The record's bytes are free at once. Whether they stay as a hole or the leaf compacts is up to you: free_space counts them either way.

UPDATE can change a row's size now. A row that still fits in its leaf, with the old one gone, stays in the same slot, so btree find reports the same page and cell. A row that no longer fits needs room the leaf does not have, and the leaf splits as it would for an insert of it. The tests of this stage only grow rows that fit; the next stage tests the split.

What stays the same

The pager, the file, SELECT, WHERE, explain, the counters and every error code but one are unchanged. Internal nodes keep their 14-byte header and 8-byte entries, and their test-mode limit of 3 keys: a real internal node would hold 510, and a tree of depth 3 would need tens of thousands of rows. The root is still page 0.

Output contract for this stage

These are the exact lines the tests check. The full definition is on the output contract page, sections 14, 15 and 17.

free_space is 4080 less 8 + row size for every cell. The limits of the users columns are now 1000 bytes, and a row, its header and length prefixes included, is at most 1000 bytes. A leaf never refuses a row with 00702: from this stage a full leaf always splits.

The Core Engine cases that check the old leaf (its bytes in the file, btree dump lines without free_space, splits after eight cells and the depths that follow from them, the 27-byte limit, here and in varlen-rows) are retired here, by name, in the manifest. Everything they checked about SQL is checked again by this stage's cases on the new leaves.

What you should see when done

Welcome to droid!
>btree dump
[BTREE] Page 0: type=LEAF num_cells=0 free_space=4080
>insert into users (id, name, email) values (2, 'danimar', 'danimar@email.com');
Insert statement executed successfully (1 rows)
>insert into users (id, name, email) values (1, 'dan', 'd@e');
Insert statement executed successfully (1 rows)
>insert into users (id, name, email) values (3, '', '');
Insert statement executed successfully (1 rows)
>btree dump
[BTREE] Page 0: type=LEAF num_cells=3 free_space=3981
[BTREE]   Cell 0: key=1 (21 bytes)
[BTREE]   Cell 1: key=2 (39 bytes)
[BTREE]   Cell 2: key=3 (15 bytes)
>btree find 2
[BTREE] Find key=2: FOUND (page=0 cell=1)
[BTREE] Row: id=2 name='danimar' email='danimar@email.com'
>update users set name = 'dani' where id = 2;
Update statement executed successfully (1 rows)
[EXEC] rows_examined=1
>btree dump
[BTREE] Page 0: type=LEAF num_cells=3 free_space=3984
[BTREE]   Cell 0: key=1 (21 bytes)
[BTREE]   Cell 1: key=2 (36 bytes)
[BTREE]   Cell 2: key=3 (15 bytes)
>delete from users where id = 1;
Delete statement executed successfully (1 rows)
[EXEC] rows_examined=1
>btree dump
[BTREE] Page 0: type=LEAF num_cells=2 free_space=4013
[BTREE]   Cell 0: key=2 (36 bytes)
[BTREE]   Cell 1: key=3 (15 bytes)
>.exit
exiting.. good bye!

Things to notice. The first dump shows an empty leaf with 4080 bytes free. The rows went in as 2, 1, 3 and the cells list them as 1, 2, 3. Shortening danimar to dani gave 3 bytes back, and deleting row 1 gave back its 21 bytes and 8 more.

Common bugs in this stage

• Sorting the records instead of the slots. Moving whole records on every insert works, and it is the thing slotted pages exist to avoid. Keep the slots in order and let the records sit where they landed.
• Free space that forgets the key or the slot. A cell costs row size + 8, not row size.
• Splitting on a count. A leaf of short rows that splits at 8 cells, or at any fixed number, is full too early. A leaf is full when the next cell does not fit.
• A split that ignores sizes. Halving by count is allowed in this stage, but check that each half fits its page; three long rows and many short ones can put too much in one half.
• 00407 after the tree has changed. Check the row's size before the duplicate check and before touching any page, and build every new row of an UPDATE before writing the first.
• 00407 for a string over 1000 bytes. That is still 00405, checked first.
• Reading the key out of the row. It works for users, where id is at a known offset, but the cell starts with the key so that the search never decodes a row. Read the key the cell gives you.
• A root leaf without its record start. An empty leaf has a record start of 4096, 00 10. A zero there makes the first cell land at a negative offset.
• The old leaf left behind in a code path. btree find, the cursor, DELETE and UPDATE all read leaves. Change them all, or one of them reads 64-byte cells out of a slotted page.

Language notes

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

• C and C++: the slotted-page code of the previous stage can serve the leaf as it is, if it takes the page type as an argument. Inserting a slot in the middle is one memmove of the slots after it.
• Rust: a leaf view over &mut [u8; 4096] with methods for slot i keeps the offsets in one place. copy_within shifts the slot directory.
• Zig: a struct holding a *[4096]u8 with inline functions for the header fields and slots does the same; std.mem.copyBackwards shifts slots towards the end.