B+ trees: insertion, deletion and an interactive visualiser

A B+ tree (B+ fa) is the search tree databases and file systems use for their indexes. It looks like an ordinary search tree that has been flattened: every node holds many keys, so the tree is wide and very shallow, and every key lives in a leaf. The rules for inserting and deleting are short, but they interact – one insert can split nodes all the way up to the root, one delete can borrow, merge and shrink the tree in a single run. That is much easier to follow when you watch it happen, so this page starts with an interactive visualiser and then explains each rule with the examples from the lecture.

A B+ tree keeps every leaf at the same depth by changing shape only at the top: it grows when the root splits and shrinks when the root is left with a single child. Everything else is local – a node borrows from or merges with a sibling under the same parent.

Try it: the visualiser

The visualiser runs the lecture’s algorithm on a tree of degree 4 to 7. Type one or more keys (whole numbers from 1 to 9999, separated by commas or spaces) and press Insert (or Enter), Delete or Search. Every operation is recorded as a list of steps – the search path, the overflow, the split, the borrowed key, the merge – and the player steps through them: play and pause, one step back or forward, or jump to the end. The node a step is about is drawn in blue, a node that breaks an invariant in red, and the line under the tree says whether the current state is a valid B+ tree.

It starts from the lecture’s deletion example. The examples menu also has the insertion example and the two operation scripts of the original app, fa.dat and fa1.dat. Random keys inserts 20 new keys, Suggest deletions picks five keys that are in the tree. The parenthesised form of the tree is shown under it with a copy button, and the operation history can be exported, downloaded and replayed in the original i:20 / d:49 format. Changing the degree rebuilds the tree by replaying its history on an empty tree.

Why B+ trees: one node per disk block

A balanced binary search tree with a million keys is about 20 levels deep. In memory that is fine. On a disk, or any storage that is read in blocks, every level is one block read, and a block read is thousands of times slower than comparing two numbers. The fix is to make a node exactly as big as a block and pack as many keys into it as will fit: the comparisons inside a node are almost free, and the tree gets very flat.

The lecture’s example: keys take 4 bytes, pointers 6 bytes, a block is 4096 bytes. A node of degree d has at most d − 1 keys and d pointers, so it needs 4(d − 1) + 6d bytes. From 10d − 4 ≤ 4096 we get d ≤ 410, and that is the degree to choose (Fig. 1).

With d = 410, three levels already hold up to 68 million keys, and every search reads exactly three blocks – usually two, because the root stays in memory. The cost section below works out the numbers.

Definition and invariants

The degree (fokszám) d ≥ 4 is the maximum number of pointers in a node. The keys of the data set are stored in the leaves; the keys in internal nodes are only separators (hasító kulcsok) that tell the search which way to go, so a key can appear both in a leaf and as a separator above it.

leaf

holds the data keys, each with a pointer to its record, and a pointer to the next leaf

internal node

k separator keys and k + 1 child pointers

separator

a key in an internal node; it divides the key ranges of the two subtrees next to it

overflow

a node with one key (leaf) or one child (internal node) more than allowed – it must split

underflow

a node with fewer keys or children than the minimum – it must borrow or merge

The invariants of a d-degree B+ tree

• —Every leaf holds at most d − 1 keys and at least ⌊d/2⌋. A root that is the only node may hold as few as one.
• —Every internal node has at most d children and at least ⌈d/2⌉, and always one more child than keys. The root, if it is internal, has at least 2 children.
• —In an internal node with keys k1 … km, child i holds the keys x with k(i−1) ≤ x < k(i): the first child the keys below k1, the last child the keys ≥ km (Fig. 2).
• —Every leaf is at the same depth.
• —Every key of the data set appears in a leaf, and the leaves read left to right are strictly increasing – no duplicates.

For d = 4, the degree of every lecture example, a leaf holds 2 or 3 keys and an internal node has 2 to 4 children. The minimums are not arbitrary: they are exactly what a split leaves behind. A leaf of d keys splits into ⌈d/2⌉ + ⌊d/2⌋, an internal node with d + 1 children into ⌈(d+1)/2⌉ + ⌊(d+1)/2⌋, and ⌊(d+1)/2⌋ = ⌈d/2⌉.

The chain of next-leaf pointers is what makes a B+ tree good at range queries: find the first key with one search, then walk along the leaves. The visualiser draws the chain as dashed arrows.

The parenthesised form

On paper and in exams the lecture writes a tree on one line, in its parenthesised form (zárójelezett alak). A leaf is a list of keys in round brackets, an internal node lists its subtrees with the separator keys between them, in square brackets, and the root uses curly braces (Fig. 3).

Reading the form back is a good invariant check: between two subtrees there is always exactly one key, every key of the left subtree is smaller than it, every key of the right subtree is greater or equal. In [ (9 10) 11 (12 13) ] that means 9, 10 < 11 ≤ 12, 13.

Search

Start at the root. In an internal node with keys k1 … km, follow the pointer of the child whose range contains x: pointer 1 if x < k1, pointer i if k(i−1) ≤ x < k(i), the last pointer if x ≥ km. In a leaf, look for x among its keys (Fig. 4). Note the ≤ on the left: a key equal to a separator is always in the right subtree, because the separator was copied from the first key of that subtree.

// pointer i covers k(i−1) ≤ x < k(i): skip every key that is ≤ x
function childIndex(keys: number[], x: number): number {
  let i = 0;
  while (i < keys.length && keys[i] <= x) i++;
  return i;
}

A search always ends in a leaf, even when the key is equal to a separator higher up: the separators only guide, the leaves decide. Insert and delete both start with exactly this search.

Insertion: split and copy up

1. 01Search the leaf where x belongs. If x is already there, stop: keys are unique.
2. 02If the leaf has fewer than d − 1 keys, insert x in order. Done.
3. 03Otherwise the leaf now has d keys. Split it: the left leaf keeps ⌈d/2⌉ keys, the new right leaf gets ⌊d/2⌋. Copy the first key of the right leaf up into the parent, as the separator between the two leaves.
4. 04If the parent now has d + 1 children, split it too: the left node keeps ⌈(d+1)/2⌉ children, the right node gets the rest, and the key between them moves up into the grandparent – it is not kept below.
5. 05If the root splits, a new root is created above the two halves, with that one key. This is the only way the tree gets taller.

The lecture’s example tree is { [ (1 2) 3 (5 6 7) ] 8 [ (9 10) 11 (12 13) 14 (14 16 17) 18 (19 20) ] }. Inserting 11 is the easy case: its leaf (12 13) has room, so it becomes (11 12 13). Inserting 4 is not – the leaf (5 6 7) is full (Fig. 5).

// the leaf now holds d keys – one too many
const keep = Math.ceil(d / 2);                   // the left leaf keeps ⌈d/2⌉ keys
const right = newLeaf(leaf.keys.slice(keep));    // the right one gets ⌊d/2⌋
leaf.keys = leaf.keys.slice(0, keep);
insertIntoParent(leaf, right.keys[0], right);    // COPY the right leaf's first key up

Inserting 15 into the original tree goes one level further. The leaf (14 16 17) splits into (14 15) and (16 17), 16 is copied up, and the parent [11 14 18] now has five children – one more than allowed (Fig. 6).

// the node now has d + 1 children and d keys
const keep = Math.ceil((d + 1) / 2);             // children that stay on the left
const up = node.keys[keep - 1];                  // MOVES up – it is not kept below
const right = newInner(node.keys.slice(keep), node.children.slice(keep));
node.keys = node.keys.slice(0, keep - 1);
node.children = node.children.slice(0, keep);
insertIntoParent(node, up, right);

The split can travel all the way up. When the root splits, there is no parent to receive the key, so a new root is created – that is how the tree grows taller, and it is why all leaves stay at the same depth (Fig. 7).

Deletion: borrow or merge

1. 01Search the leaf of x. If x is not there, stop. Otherwise remove it from the leaf.
2. 02A root leaf is fine with one key; when its last key goes, the tree is empty. Any other leaf with at least ⌊d/2⌋ keys is fine too. Done.
3. 03Otherwise the leaf underflows. Try, in this order: (1) if the left sibling (same parent) has more than the minimum, move its last key over, and the separator between them becomes that key; (2) if the right sibling has more than the minimum, move its first key over, and the separator becomes the new first key of the right sibling; (3) otherwise merge the leaf into its right sibling – or the left one if there is no right – and remove the separator between them from the parent.
4. 04A merge takes a child away from the parent, which may now underflow. An internal node first tries to borrow a child from its left, then its right sibling (a rotation through the parent), otherwise it merges with a sibling, taking the separator from the parent down between the two halves. Repeat upwards.
5. 05If the root is left with a single child, that child becomes the root. This is the only way the tree gets shorter.

Borrowing a key

The lecture’s deletion example is { [ (6 9) 14 (14 15) 16 (16 17) ] 18 [ (18 20) 21 (21 25 30) ] }, and it is deleted from three times in a row: 18, then 20, then 6. Deleting 18 leaves (20) with one key. The leaf has no left sibling under the same parent – (16 17) is a neighbour along the chain but belongs to another parent – so it looks right (Fig. 8).

// leaf = child i of parent, it has ⌊d/2⌋ − 1 keys
if (left && left.keys.length > minLeaf) {          // 1. borrow the left sibling's last key
  leaf.keys.unshift(left.keys.pop()!);
  parent.keys[i - 1] = leaf.keys[0];
} else if (right && right.keys.length > minLeaf) { // 2. borrow the right sibling's first key
  leaf.keys.push(right.keys.shift()!);
  parent.keys[i] = right.keys[0];
} else {                                           // 3. merge – into the right sibling if there is one
  mergeIntoSibling(leaf);                          //    and drop the separator between them
  fixInternal(parent);
}

Merging leaves, then rotating an internal node

Deleting 20 leaves (21), and now the right sibling (25 30) has only the minimum. The leaves merge into (21 25 30), and their parent loses its only separator – a non-root node with one child. It looks at its left sibling [14 16], which has three children and can spare one (Fig. 9).

The rotation is the internal-node version of borrowing. A child can’t simply move from one parent to another, because the separators would be wrong; instead the separator from the grandparent comes down into the underflowing node, the sibling’s last child moves across, and the sibling’s last key goes up to take the separator’s place. Read it as keys rotating clockwise: 16 → root, 18 → node.

// node has ⌈d/2⌉ − 1 children, its left sibling has more than ⌈d/2⌉
node.keys.unshift(parent.keys[i - 1]);           // the separator comes down
node.children.unshift(left.children.pop()!);     // the sibling's last child moves over
parent.keys[i - 1] = left.keys.pop()!;           // the sibling's last key goes up

Merging internal nodes and shrinking the tree

Deleting 6 from the result starts the same way – (9) merges into (9 14 15), and its parent is left with one child. But this time the only sibling, [18], has exactly two children, so there is nothing to borrow. The two internal nodes merge, and the root’s separator 16 comes down between them. The root is left with a single child, which becomes the new root (Fig. 10).

Cost: why the height stays small

Every operation walks one root-to-leaf path and, on the way back, touches at most a node and its sibling per level. With L levels a search reads L nodes, an insert or delete reads and writes O(L) nodes. Each node costs O(d) work in memory, but on a disk the node reads are what you pay for.

The height follows from the minimums. A tree with L ≥ 2 levels has at least 2 children at the root, ⌈d/2⌉ at every other internal node and ⌊d/2⌋ keys in every leaf, so n ≥ 2·⌈d/2⌉^(L−2)·⌊d/2⌋. At most it has d^(L−1) leaves with d − 1 keys each. Taking the logarithm, L ≤ 2 + log base ⌈d/2⌉ of n / (2⌊d/2⌋): the height is O(log n), with a base around d/2, which for a disk-sized node is in the hundreds.

Four block reads for 28 billion keys – and since the top levels are read by every query, they stay cached, so in practice a lookup touches the disk once or twice.

Practice

Solve these on paper first, in the parenthesised form or as a drawing, then open the solution: every task with a tree has its solution as a runnable, step-by-step replay on the task's own starting tree.

{ [ (1 2) 3 (4 5) 6 (6 7) ] 8 [ (9 10) 11 (12 13) 14 (14 16 17) 18 (19 20) ] }

{ [ (1 2) 3 (5 6 7) ] 8 [ (9 10) 11 (12 13) 14 (14 15) ] 16 [ (16 17) 18 (19 20) ] }

{ [ (6 9) 14 (14 15) 16 (16 17) ] 18 [ (20 21) 25 (25 30) ] }

{ [ (6 9) 14 (14 15) ] 16 [ (16 17) 18 (21 25 30) ] }

{ (9 14 15) 16 (16 17) 18 (21 25 30) }

{ (20 30) 40 (40 50) 60 (60 70) 80 (80 90) }

{ [ (20 30) 33 (33 36) 40 (40 50 55) ] 60 [ (60 70) 80 (80 90) ] }

Summary

• —A d-degree B+ tree: leaves hold ⌊d/2⌋ to d − 1 keys, internal nodes have ⌈d/2⌉ to d children, the root is the exception, and all leaves are at the same depth.
• —Data keys live only in the leaves, which are chained left to right; internal keys are separators: child i holds k(i−1) ≤ x < k(i).
• —Insert: a full leaf splits ⌈d/2⌉ + ⌊d/2⌋ and its separator is copied up; a full internal node splits and its middle key moves up; a root split adds a level.
• —Delete: an underflowing leaf borrows from the left, then the right sibling, otherwise merges (into the right one if there is one). Internal nodes rotate or merge the same way, and a root with one child is replaced by it.
• —Separators are not refreshed on a plain delete – a stale separator is still a correct one.
• —One node per disk block gives a degree in the hundreds, so the height is O(log n) with a huge base: three or four levels for any realistic index.