Splitting by Bytes; DELETE and UPDATE with Variable Rows

Why this stage exists

In the previous stage a leaf became full when its bytes ran out, but how it split was left open: any division that fit was right, halving the count included. With rows of one size that is a fine answer. With rows of very different sizes it is not.

Take a leaf that holds three rows of 1000 bytes and thirty-seven of 21. Halving by count puts the three long rows and seventeen short ones on the left, 3517 bytes, and twenty short rows on the right, 580. The left leaf is full again after a couple of inserts, and splits again; the right one sits nearly empty. A B+Tree splits so that both halves have room to grow. Room is measured in bytes now, so the split has to be too.

This stage also finishes what variable rows do to UPDATE and DELETE. A row that grows may no longer fit in its leaf; a row that is deleted leaves room another row can take. Both follow from one idea: a leaf's free space is the only thing that decides whether a cell fits.

What changes: where the leaf divides

A cell weighs its row, 4 bytes of key and 4 of slot. Line the cells up in key order, the new one in its place, and cut where the two halves weigh closest to the same:

The rule has three parts.

• The halves' bytes are as close as they can be. Walk the points between cells, from after the first to before the last, and keep the one where the difference is smallest. With the cut in the best place, moving one cell across can only make it worse, so the halves differ by at most one cell and its slot.
• The new cell counts. It is weighed in its place among the keys, not added to a half afterwards. A 1000-byte row arriving at the front of a leaf of short rows pulls the cut towards itself.
• A tie can go either way. When two points are equally close, both are right. Rows of one size and an odd count tie: 141 rows of 21 bytes divide 70 and 71 or 71 and 70. The tests never build a tie.

Nothing else about the split changes. The page, link, parent and allocation rules are the Core Engine's: the root's halves go to two new pages, any other leaf keeps its page for the left half and the right half goes to one new page, and the separator is the right leaf's first key. Only where the cut goes is new.

A split that follows from the rows

Dividing by count left the Core Engine's tree fixed by the order of the inserts. Dividing by bytes does the same for variable rows: given the rows and the order they arrive in, which keys each leaf holds follows, whatever the internal nodes do above them. The tests use this. They replay hundreds of statements on a model of the leaves and expect btree structure to show exactly those leaves, left to right. A split that is almost by bytes, or by bytes without the new cell, drifts from the model after a few splits.

UPDATE when a row changes size

An UPDATE builds the new row and checks it before touching the tree, as before. What happens next depends only on bytes:

• Take the old cell out, then see if the new one fits. The room that counts is the room the leaf has once the old cell is gone. A row of 21 bytes growing to 41 needs 20 more bytes; a leaf with 20 free has 49 once the old 29 are back, and the new cell needs exactly 49. It fits, and stays at the same page and cell.
• If it does not fit, split as for an insert. The leaf's cells, with the new cell in the old one's place, divide by bytes. The row keeps its key, so it stays in key order; btree find may report a new page and cell.

Checking whether the new row fits before taking the old one out asks for room the leaf already has, and splits a leaf that did not need it.

DELETE and the room it frees

DELETE is unchanged: the cell's slot goes, and its bytes are free at once. What this stage checks is that free really means usable. After deleting a row from a full leaf, a new row as large as the room freed goes in without a split, even though the bytes it takes back sit in the middle of the record area, behind other records. The slotted page compacts when the gap between the slots and the records is too small but the free space is not; the leaf does the same.

No leaf is merged and no page is freed. A leaf can end up empty, and a separator can point at keys that are gone: both are valid, as in the Core Engine.

Output contract for this stage

Nothing new is printed. The lines the tests check are those of the previous stages; the full definition is on the output contract page, sections 9, 10 and 17.

What the tests pin down is which keys land where:

• a full leaf's cells, in key order with the new one among them, divide where the halves' used bytes, each cell's row plus 8, are closest; either point on a tie;
• an UPDATE keeps its page and cell when the new cell fits once the old one is gone, and otherwise splits the leaf as an insert of the new cell would;
• a DELETE frees row size + 8 at once, and the next cell that fits uses it without a split.

No earlier case is retired: the previous stage allowed any division that fit, and none of its cases depended on which.

What you should see when done

The file holds the rows of split-by-bytes: three rows of 1000 bytes, keys 1 to 3, then keys 4 to 39 with 21 bytes each. The leaf has 12 bytes left. Open it again, look, and insert key 40:

Welcome to droid!
>btree structure
[BTREE] Tree depth: 1
[BTREE] LEAF (page=0 cells=39 keys=[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39])
>insert into users (id, name, email) values (40, 'dan', 'd@e');
Insert statement executed successfully (1 rows)
>btree structure
[BTREE] Tree depth: 2
[BTREE] INTERNAL (page=0 keys=[3])
[BTREE]   LEAF (page=1 cells=2 keys=[1,2])
[BTREE]   LEAF (page=2 cells=38 keys=[3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40])
>btree dump 0
[BTREE] Page 0: type=INTERNAL num_keys=1 right_child=2
[BTREE]   Key 0: key=3 (child_page=1)
>btree dump 1
[BTREE] Page 1: type=LEAF num_cells=2 free_space=2064
[BTREE]   Cell 0: key=1 (1000 bytes)
[BTREE]   Cell 1: key=2 (1000 bytes)
>btree find 40
[BTREE] Find key=40: FOUND (page=2 cell=37)
[BTREE] Row: id=40 name='dan' email='d@e'
>delete from users where id = 2;
Delete statement executed successfully (1 rows)
[EXEC] rows_examined=1
>btree dump 1
[BTREE] Page 1: type=LEAF num_cells=1 free_space=3072
[BTREE]   Cell 0: key=1 (1000 bytes)
>.exit
exiting.. good bye!

Things to notice. Key 40 is 21 bytes, and it moved 38 cells to a new page: the split weighs every cell, and two 1000-byte rows balance thirty-eight short ones. Page 1 holds two cells and has 2064 bytes free; page 2, with 38, has 1999. Deleting row 2 gave back its 1000 bytes and 8 more, and left the separator 3 where it was.

Common bugs in this stage

• Cutting in the middle of the count. It passes every test with rows of one size and fails the first one with long and short rows mixed.
• Leaving the new cell out. Dividing the old cells by bytes and then adding the new one to whichever half it belongs in puts the cut in the wrong place whenever the new cell is large.
• Weighing rows without their key and slot. A cell takes row size + 8. Weighing only the rows moves the cut when the halves have different numbers of cells.
• An empty half. The first division point is after the first cell and the last is before the last cell. A leaf of one huge cell and many small ones still leaves a cell on each side.
• Checking room before removing the old row. An UPDATE that grows a row in a full leaf asks for the extra bytes only. Take the old cell out first, then check.
• Weighing the old row in an UPDATE's split. The split divides the cells as they will be: with the new row, not the one it replaces.
• Freed bytes that cannot be used. Free space says 49 and a 49-byte cell is refused, or splits the leaf, because the free bytes are in holes. Compact, then write.
• Moving a separator on DELETE. Separators change only when a leaf splits.

Language notes

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

• C and C++: gather the cells to divide, the new one included, into a buffer the size of two pages before writing either half; dividing in place while reading the same page overwrites cells you have not copied yet.
• Rust: collect the cells as owned byte vectors before writing either half; borrowing them from the page you are about to rewrite will not pass the borrow checker, and should not.
• Zig: a fixed array of slices over a scratch buffer holds the cells; std.mem.copyForwards writes them into the halves.