Internal Node Splits

Why this stage exists

At the end of the previous stage the root is the only internal node, and it holds at most 3 keys. Four leaves, and then the next leaf split has nowhere to put its key: 00702. The table stops at a few dozen rows.

The fix is the same idea one level up. A full internal node splits in two, and the node above it gains a key. When the node that fills up is the root, a new root appears above the two halves, and the tree is one level taller. There is no other way for the tree to grow, which is why every leaf is always at the same depth.

What changes: the root splits

Insert rows 1 to 20 in order and the root is full: 3 keys over 4 leaves. Row 21 fills the last leaf past 8, the leaf splits, and its separator, 17, is a fourth key for the root:

The key that moves up leaves both halves. A leaf split copies the right leaf's first key into the parent, and the key stays in the leaf as well, because that is where its row is. An internal key has no row: it is only a signpost. So when an internal node splits, the key that goes up moves to the parent, and neither half keeps it. Page 6 holds 5 and 9; page 7 holds 17; 13 is only in page 0.

The children follow their keys. Page 6's keys 5 and 9 separate three children: pages 1, 2 and 3. Page 3 is the child just before 13, so it becomes page 6's right child. Page 7's one key, 17, separates pages 4 and 5. Every leaf is still reached by exactly one path, and the separator rule still holds everywhere: 13 is the smallest key under page 7.

2 on the left, 1 on the right. Four keys, one of which goes up, leaves three to divide. Keeping 1 on the left instead, which sends 9 up, would make an equally good tree. The contract fixes the third key so that every exact tree in the later parts, where rows are deleted, pages are freed and the file is compacted, is the tree your engine builds. The tests check it from this stage on.

Pages are allocated from the bottom up. The leaf split runs first and takes page 5. The root split runs after it and takes pages 6 and 7, the left half first. As with a root leaf, the root keeps page 0 and its halves move out.

A split below the root

Keep inserting in order and page 7 fills: keys 17, 21 and 25 over four leaves. The next leaf split gives page 7 a fourth key, 29. Page 7 is not the root, so it splits like a leaf that is not the root: it keeps its page for the left half, one new page takes the right half, and the key that moves up goes into page 0, just after the key for page 7. Page 0 then has two keys over three internal nodes. When it has three keys and a fourth arrives, the root splits again and the tree reaches depth 4.

A split can climb all the way: a leaf split fills its parent, whose split fills its parent, up to the root. Each step hands exactly one key and one page to the level above, and the climb stops at the first node with room.

Parent fields

Every node's header names its parent. In the previous stage that was always page 0. Now it is whichever internal node points at the node, and a split changes it:

• when the root splits, every child it had moves under page 6 or page 7, and each one's parent field must say so;
• when any other internal node splits, the children that go to the new right page now have that page as their parent;
• a new internal node, and every node that moves under it, gets its parent field set when it is written.

Nothing you print shows a parent field, so a tree whose parent fields are wrong prints correctly. The tests read them from the file. Page 1 after the split above, with its header naming page 6:

How deep the tree grows

With the test-mode limits, a tree of depth 2 holds at most 8 × 4 = 32 rows and one of depth 3 at most 8 × 4 × 4 = 128. So 33 rows or more are always at least depth 3, and 129 or more at least depth 4, whatever your splits chose. The tests use 150.

Nothing but the page limit stops the tree now. An INSERT whose splits cannot get all the pages they need is 00602 and changes nothing.

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. Nothing new is printed in this stage: the same commands show a deeper tree.

What you should see when done

This session keeps 4 cells on the left of a leaf split and 2 keys on the left of an internal split. With 1 key on the left, page 0 holds 9, page 6 holds 5 and page 7 holds 13 and 17.

$droid --db users.db
Welcome to droid!
>btree structure
[BTREE] Tree depth: 2
[BTREE] INTERNAL (page=0 keys=[5,9,13])
[BTREE]   LEAF (page=1 cells=4 keys=[1,2,3,4])
[BTREE]   LEAF (page=2 cells=4 keys=[5,6,7,8])
[BTREE]   LEAF (page=3 cells=4 keys=[9,10,11,12])
[BTREE]   LEAF (page=4 cells=8 keys=[13,14,15,16,17,18,19,20])
>insert into users (id, name, email) values (21, 'user21', '[email protected]');
Insert statement executed successfully
>btree structure
[BTREE] Tree depth: 3
[BTREE] INTERNAL (page=0 keys=[13])
[BTREE]   INTERNAL (page=6 keys=[5,9])
[BTREE]     LEAF (page=1 cells=4 keys=[1,2,3,4])
[BTREE]     LEAF (page=2 cells=4 keys=[5,6,7,8])
[BTREE]     LEAF (page=3 cells=4 keys=[9,10,11,12])
[BTREE]   INTERNAL (page=7 keys=[17])
[BTREE]     LEAF (page=4 cells=4 keys=[13,14,15,16])
[BTREE]     LEAF (page=5 cells=5 keys=[17,18,19,20,21])
>btree dump 0
[BTREE] Page 0: type=INTERNAL num_keys=1 right_child=7
[BTREE]   Key 0: key=13 (child_page=6)
>btree dump 7
[BTREE] Page 7: type=INTERNAL num_keys=1 right_child=5
[BTREE]   Key 0: key=17 (child_page=4)
>btree find 17
[BTREE] Find key=17: FOUND (page=5 cell=0)
[BTREE] Row: id=17 name='user17' email='[email protected]'
>pager status
[PAGER] Status: total_pages=8 cached=8
>.exit
exiting.. good bye!

The file already held rows 1 to 20 from an earlier session. Row 21 made two splits and allocated three pages, and none of it printed anything but the usual INSERT line.

Common bugs in this stage

• Copying the middle key instead of moving it. The key goes up and also stays in the right half, like a leaf's separator. The right node then has as many keys as children, and a search that reaches it goes wrong. An internal split leaves one key fewer below than it had.
• The wrong right child. The left half keeps its keys but not the child just before the key that moved up, or the right half forgets to take the old right child. A whole subtree becomes unreachable, and btree structure shows fewer leaves than there are.
• Parent fields left behind. The tree prints correctly, and the file says the leaves still belong to page 0. Every child that moved into a new page must name it. When the root splits, that is all of them.
• Splitting the parent before it has the new key. Give the parent the key and the page first, then split it if it has 4. Splitting first, and then trying to insert into a half, puts the key in the wrong half or loses it.
• The root moves. Writing the new root to a new page and leaving page 0 as one of the halves. Page 0 is the root, always.
• Only the right edge works. Rows inserted in order always split the last node, so the new key always goes at the end of its parent. Insert backwards or shuffled: the key and its page go just after the child that split, wherever that is.
• A recursion that stops one level early. The parent is split, but the key it hands up is dropped instead of being inserted into the grandparent. The tree holds every row and has fewer keys than it should, which the separator check notices.
• Pages allocated top down. Allocating the internal node's page before the leaf's changes every page number after it. The leaf split comes first, then each split above it.

Language notes

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

• C and C++: a split that climbs is naturally recursive; each level returns "no split" or "a key and a page" to the caller. A struct of two numbers is enough.
• Rust: return an Option of the key and page from each level, rather than writing to the parent from inside the child's split. It keeps each level borrowing one page at a time.
• Zig: an optional struct return does the same job; orelse return ends the climb at the first level with room.