Leaf Splits and the First Internal Node

Why this stage exists

At the end of the previous stage the table is one sorted leaf, and the ninth row is refused with 00702. A table that stops at eight rows is not a table. This stage removes the limit. A full leaf splits in two, and a new kind of node, the internal node, sits above the two leaves and tells a search which one to read.

That is the whole idea of a B+Tree. Rows live only in leaves, and leaves stay a fixed size. When one fills up it becomes two half-full leaves, and the node above gains a key. Nothing is ever shifted across the whole table, and a search reads one node per level, not every row.

The split happens in the leaves, and in this stage the root internal node gets up to 3 keys, which is 4 leaves. What happens when the internal node is full is the next stage.

What changes: one leaf becomes three nodes

Insert rows 1 to 8 and the root leaf is full. The ninth row arrives:

Three things to notice.

The root stays on page 0. Every search starts at page 0, so the root can never move. When the root leaf splits, it is its cells that move out, into two new pages, and page 0 is rewritten as an internal node. The file grows from one page to three.

The separator is a copy. Key 5 is in two places: in the right leaf with its row, as a cell like any other, and in the root as a bare 4-byte number. The root holds no rows. It only says: keys below 5 are in page 1; 5 and above are in page 2.

The halves are 4 and 5, either way round. Nine cells do not divide evenly. You may keep 4 on the left and move 5 right, as above, or keep 5 and move 4, which puts 6 in the root. Both are correct and the tests accept both. Pick one and always use it. What is not allowed is anything more lopsided: a split that leaves 8 and 1 makes a leaf that is full again at the next insert, and the tests count on every leaf holding at least 4 cells.

The split, cell by cell

The same split seen as cells. The new key takes its place among the eight first, so the nine keys are in order before they are divided:

A split below the root

Keep inserting and the right leaf fills: rows 5 to 12 are eight cells. Row 13 splits it, and this time the leaf is not the root:

The parent needs the new key and the new child at the right position: just after the child that split. In a node with keys [5], a split of the right child puts 9 after 5. A split of the left child would put its separator before 5, and every key and child after it moves along, as cells did in a sorted leaf.

A split never allocates anything else. After it, the pages in the file are exactly the nodes of the tree, which pager status and btree structure both show.

The internal node

An internal node is a page with the same 14-byte header as a leaf, and then entries of 8 bytes: the page of a child, then a key. A node with n keys has n entries and n + 1 children. The last child has no key to go with it, so it goes in the header's link field, which in an internal node is called the right child.

Page 0 after the split above, with the one entry that points at page 1 and the right child, page 2:

The two leaves have headers too, and a split must keep them true: node type 1; is root 0, since only page 0 is the root; parent 0, because page 0 is their parent; the count; and the link. Page 1 links to page 2, and page 2 links to 0, the end of the chain. Page 0 can never be a next leaf, so 0 is free to mean "none". The tests read all of this from the file.

How much fits at depth 2

The root can hold 3 keys in this stage, so the tree stops at 4 leaves. The split that would need a fifth leaf needs a fourth key in a full root, and that is still 00702 until the next stage splits internal nodes too.

How many rows get there depends on the order they arrive and on which way your splits go, but never fewer than 20. When a fifth leaf is needed there are already four leaves: the full one with 8 cells and three others that each kept at least 4 from their split. That is 20 rows, and the one arriving is the 21st. The tests never insert more than 20 rows in this stage.

Output contract for this stage

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

Key lists have no spaces: keys=[1,2,3,4]. A tree that is only its root leaf has depth 1 and prints one line, [BTREE] LEAF (page=0 cells=<n> keys=[...]). btree dump with no page still dumps page 0, which is now the internal node.

What you should see when done

This session splits 4 and 5. If yours splits 5 and 4, the root holds 6, page 1 holds 1 to 5, and key 5 is found in page 1, cell 4.

$droid --db users.db
Welcome to droid!
>insert into users (id, name, email) values (5, 'eve', 'eve@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (8, 'hal', 'hal@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (1, 'ada', 'ada@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (7, 'gus', 'gus@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (2, 'bob', 'bob@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (6, 'fay', 'fay@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (4, 'dan', 'dan@example.com');
Insert statement executed successfully
>insert into users (id, name, email) values (3, 'cy', 'cy@example.com');
Insert statement executed successfully
>btree structure
[BTREE] Tree depth: 1
[BTREE] LEAF (page=0 cells=8 keys=[1,2,3,4,5,6,7,8])
>insert into users (id, name, email) values (9, 'ivy', 'ivy@example.com');
Insert statement executed successfully
>btree structure
[BTREE] Tree depth: 2
[BTREE] INTERNAL (page=0 keys=[5])
[BTREE]   LEAF (page=1 cells=4 keys=[1,2,3,4])
[BTREE]   LEAF (page=2 cells=5 keys=[5,6,7,8,9])
>btree dump 0
[BTREE] Page 0: type=INTERNAL num_keys=1 right_child=2
[BTREE]   Key 0: key=5 (child_page=1)
>btree find 5
[BTREE] Find key=5: FOUND (page=2 cell=0)
[BTREE] Row: id=5 name='eve' email='eve@example.com'
>btree find 4
[BTREE] Find key=4: FOUND (page=1 cell=3)
[BTREE] Row: id=4 name='dan' email='dan@example.com'
>pager status
[PAGER] Status: total_pages=3 cached=3
>select id, name from users;
id | name
1 | ada
2 | bob
3 | cy
4 | dan
5 | eve
6 | fay
7 | gus
8 | hal
9 | ivy
(9 rows)
>insert into users (id, name, email) values (5, 'mallory', 'm@example.com');
[ERROR:00701] Key 5 already exists
>.exit
exiting.. good bye!

Key 5, the separator, is found on the right, in page 2 cell 0. SELECT did not change at all, and still prints the rows in order: the cursor now starts at page 1 and follows the link to page 2.

Common bugs in this stage

• The root moves. The split writes the new internal node to a fresh page and leaves page 0 as a leaf, or makes the old page 0 the left leaf. The next search starts at page 0 and finds only half the table. The root is page 0, always.
• Splitting before the duplicate check. A duplicate arriving at a full leaf splits it and then reports 00701. The statement failed, and the tree changed anyway. Look for the key first.
• Writing the ninth cell past the end of the page. Eight cells and a header fill most of a page, but nine may not be written there even for a moment. Collect the nine cells outside the page, then write each half.
• The separator from the wrong side. The separator is the first key of the right leaf. The last key of the left leaf works for searches until someone inserts a key between the two, and then that key goes to the wrong leaf.
• Going left on equal. A search for key 5 with separator 5 must go right. With "less than or equal goes left", btree find 5 reports NOT_FOUND for a key that is there.
• Forgetting the link. The left leaf still links to 0 after the split, so SELECT stops after the first leaf and returns four rows. Or the right leaf links to 0 when the left one had a next leaf, and a split in the middle of the chain cuts it in two.
• Stale headers. A new leaf copied from page 0 keeps is root 1. Count, is root, parent and link are all yours to set on every page a split writes.
• The new separator in the wrong place. Appending the new key to the end of the parent's keys works when the rightmost leaf split, which is every split when rows arrive in order. Insert rows backwards and it breaks. The key and its child go just after the child that split.
• btree find reports the wrong page. It reports page 0, or the cell as if all the rows were in one leaf. The page is the leaf's, and the cell counts from 0 in that leaf.
• An extra page. Allocating a page "just in case", or three pages for a root split, leaves a page the tree does not use. pager status must count only the tree's pages.

Language notes

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

• C and C++: a buffer of nine cells on the stack, 64 × 9 bytes, is enough to hold a leaf while it splits. Give the internal node its own read and write functions, rather than reusing the leaf's with different offsets.
• Rust: a split touches two or three pages at once. Borrowing them all mutably from the pager at the same time fights the borrow checker. Copy the cells out, drop the borrow, then write each page.
• Zig: keep the node header in one place and read it the same way for both kinds of node, since only what follows it differs.