Store the B+Tree's leaves as slotted pages holding variable-length rows: a cell is a key and a row in a record, its slot sits in key order, and a leaf is full when the next cell does not fit, not after a fixed count. Lift the string limit to 1000 bytes and refuse rows over 1000.
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.
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:
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.
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 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.
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.
A leaf is the slotted page of slotted-page with type 1. Its header fields keep their Core Engine meanings.
i is found through slot i: its offset and length point at a record that holds the 4-byte key, then the row of the previous stages.i holds the i-th smallest key; a leaf has no deleted slots; every slot points inside the record area and no two records overlap.The search of btree-search, over slots instead of cells.
Check first, then place the cell, then split only if it does not fit.
4 + row size bytes of record and 4 of slot. If the leaf's free space covers both, write the record into the record area (compacting first if the room is only in holes) and insert its slot at the key's position, moving the later slots one place. The records do not move.Rows change size now, and the leaf keeps count in bytes.
These are the exact lines the tests check. The full definition is on the output contract page, sections 14, 15 and 17.
| Input | Output |
|---|---|
btree dump [page], a leaf | [BTREE] Page <p>: type=LEAF num_cells=<n> free_space=<f>, then per cell [BTREE] Cell <i>: key=<k> (<row size> bytes) |
btree dump, an internal node; btree find; btree structure | unchanged |
a row over 1000 bytes, in INSERT, UPDATE or serialize | [ERROR:00407] <message> |
| a string over 1000 bytes | [ERROR:00405] <message> |
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.
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', '[email protected]');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)>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)>.exitexiting.. 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.
row size + 8, not row size.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.00 10. A zero there makes the first cell land at a negative offset.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.The page above is the same for every language. These are the only language-specific hints.
memmove of the slots after it.&mut [u8; 4096] with methods for slot i keeps the offsets in one place. copy_within shifts the slot directory.*[4096]u8 with inline functions for the header fields and slots does the same; std.mem.copyBackwards shifts slots towards the end.