# B+ trees: insertion, deletion and an interactive visualiser

> The d-degree B+ tree with the lecture’s rules – leaf and internal splits on insert, borrowing, merging and rotations on delete – and a visualiser that steps through every operation on the lecture’s example trees.

Source: https://laszlonemes.com/university/algorithms/b-plus-trees · Author: László Nemes

Interactive · Algorithms and Data Structures II

The d-degree B+ tree with the lecture’s rules – leaf and internal splits on insert, borrowing, merging and rotations on delete – and a visualiser that steps through every operation on the lecture’s example trees.

20 min read `B+ tree invariants` `Parenthesised form` `Leaf and internal splits` `Borrow, merge, rotate` `Degree from block size` `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.

After this session you can

- state the invariants of a d-degree B+ tree and check a tree against them
- read and write a tree in the lecture’s parenthesised form
- insert a key: split a full leaf, copy its separator up, split internal nodes and the root
- delete a key: borrow from the left or right sibling, merge leaves, rotate or merge internal nodes
- choose the degree for a given disk block size and explain why the height is O(log n)

## 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.

Good to know

**Predict first, then press Play**

The visualiser is most useful as a check. Before you press Delete, say out loud which case will happen – borrow left, borrow right or merge – and what the separator will be afterwards. Then step through and compare.

## 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).

> **Fig. 1** · Choosing the degree: a node is one block, so the degree is the largest d whose keys and pointers still fit.
>
> *Diagram:* One B+ tree node fills one 4096-byte disk block. With 4-byte keys and 6-byte pointers a node of degree d needs 4(d − 1) + 6d bytes, so the largest degree that fits is d = 410: 409 keys and 410 pointers, exactly 4096 bytes.

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.

> **Fig. 2** · One internal node and one leaf, degree 4. Each pointer of an internal node owns a key range; a leaf points to records and to the next leaf.
>
> *Diagram:* An internal node with keys 11, 14, 18 has four pointers. Pointer i leads to the subtree of keys x with k(i−1) ≤ x < k(i): below 11, from 11 to 14, from 14 to 18, and from 18 up. A leaf holds up to d − 1 keys with a pointer to each data record, and a last pointer to the next leaf.

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).

> **Fig. 3** · The lecture's insertion example, drawn and in parenthesised form.
>
> *Diagram:* A degree-4 B+ tree and its parenthesised form { [ (1 2) 3 (5 6 7) ] 8 [ (9 10) 11 (12 13) 14 (14 16 17) 18 (19 20) ] }. Curly braces mark the root, square brackets the other internal nodes, round brackets the leaves; between two subtrees stands the separator key that divides them.

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.

> **Fig. 4** · Searching 16: one node per level, and the comparison in each node picks the pointer.
>
> *Diagram:* Searching 16 reads one node per level. In the root, 16 ≥ 8, so follow the second pointer; in [11 14 18], 14 ≤ 16 < 18, so follow the third; the leaf (14 16 17) contains 16.

bplus.ts – which pointer to follow

```ts
// 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. Search the leaf where x belongs. If x is already there, stop: keys are unique.
2. If the leaf has fewer than d − 1 keys, insert x in order. Done.
3. Otherwise 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. If 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. If 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).

> **Fig. 5** · A leaf split: the four keys are shared 2 + 2 and the first key of the new right leaf is copied into the parent.
>
> *Diagram:* Inserting 4 into the lecture's example tree. The key belongs in the full leaf (5 6 7); the four keys 4 5 6 7 are split into (4 5) and (6 7), and 6, the first key of the new right leaf, is copied up into the parent, which becomes [3 6].

bplus.ts – splitting a leaf

```ts
// 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).

> **Fig. 6** · An internal split: the key in the middle moves up into the root instead of being copied.
>
> *Diagram:* Inserting 15. The leaf (14 16 17) splits into (14 15) and (16 17) and 16 is copied up, but the parent [11 14 18] is already full. With five children it splits too: [11 14] keeps three children, [18] gets two, and 16 – the key between them – moves up into the root, which becomes [8 16].

bplus.ts – splitting an internal node

```ts
// 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);
```

Common mistake

**Copy up from a leaf, move up from an internal node**

When a leaf splits, its separator stays in the right leaf as well – every data key must remain in a leaf. When an internal node splits, the middle key leaves the node: `[11 14 16 18]` becomes `[11 14]` and `[18]`, with 16 only in the root. Writing `[16 18]` on the right is the most common mistake in this exercise – it leaves a node with as many keys as children.

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).

> **Fig. 7** · A root split: the smallest case is a full root leaf.
>
> *Diagram:* A split that reaches the root creates a new root above it – the only way a B+ tree grows taller. Inserting 40 into the full root leaf (10 20 30) gives four keys; they split into (10 20) and (30 40), and a new root [30] points to both.

## Deletion: borrow or merge

1. Search the leaf of x. If x is not there, stop. Otherwise remove it from the leaf.
2. A 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. Otherwise 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. A 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. If the root is left with a single child, that child becomes the root. This is the only way the tree gets shorter.

Good to know

**Separators are not refreshed on a plain delete**

Delete 14 from the insertion example: its leaf becomes `(16 17)` and still has two keys, so the algorithm stops – and 14 stays in the parent `[11 14 18]`, although it is no longer in the tree. That is fine. The separator only has to divide the ranges correctly, and 12, 13 < 14 ≤ 16, 17 still holds. Separators change only when a borrow or a merge needs them to.

### 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).

> **Fig. 8** · Borrowing from the right sibling: one key moves over, and the separator becomes the right sibling's new first key.
>
> *Diagram:* Deleting 18 from the lecture's deletion example. The leaf (18 20) is left with only 20, below the minimum of two keys. Its right sibling (21 25 30) has a key to spare, so 21 moves over, and the separator between them in the parent changes from 21 to 25, the new first key of the right sibling.

bplus.ts – the three cases of a leaf underflow

```ts
// 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).

> **Fig. 9** · A leaf merge that makes the parent underflow, fixed by a rotation through the root.
>
> *Diagram:* Deleting 20 next. The leaf (21) can't borrow – its right sibling (25 30) has only the minimum – so the two leaves merge into (21 25 30) and the separator 25 leaves the parent. That parent is left with one child and underflows. Its left sibling [14 16] has three children, so it rotates: 18 comes down from the root, the child (16 17) moves over, and 16 goes up into the root.

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.

bplus.ts – borrowing a child from the left sibling

```ts
// 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).

> **Fig. 10** · An internal merge that empties the root: the tree loses a level.
>
> *Diagram:* Deleting 6 last. The leaf (9) merges into its right sibling, giving (9 14 15), and its parent is left with one child. The parent's only sibling [18] has the minimum two children, so the two internal nodes merge with the root's separator 16 between them into [16 18]. The root now has a single child, which becomes the new root: the tree is one level shorter.

Common mistake

**Only siblings under the same parent count**

The leaves form one chain, so it is tempting to borrow from the neighbouring leaf even when it hangs under another parent. Don’t: the separator you would have to change is not in your parent, and the key would have to cross a separator higher up. Borrow and merge only between children of the same node – an internal underflow one level up will rebalance across parents if needed.

| Underflow in | 1. try | 2. try | 3. otherwise |
| --- | --- | --- | --- |
| a leaf (< ⌊d/2⌋ keys) | left sibling’s last key, separator := moved key | right sibling’s first key, separator := its new first key | merge into the right sibling (else the left), drop the separator |
| an internal node (< ⌈d/2⌉ children) | rotate from the left: separator down, last child over, last key up | rotate from the right: separator down, first child over, first key up | merge with the right sibling (else the left) around the separator, recurse |
| the root | a leaf root: fine with ≥ 1 key | an internal root: fine with ≥ 2 children | one child left: it becomes the root |

## 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.

| Levels (d = 410) | Fewest keys | Most keys | Block reads per search |
| --- | --- | --- | --- |
| 1 | 1 | 409 | 1 |
| 2 | 410 | 167 690 | 2 |
| 3 | 84 050 | 68 752 900 | 3 |
| 4 | 17 230 250 | 28 188 689 000 | 4 |

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.

Task 1

**Choose the degree**

A B+ tree is stored on a disk with 4096-byte blocks. Keys take 4 bytes and pointers 6 bytes. What degree d should you choose? And with 8-byte keys and 8-byte pointers?

**Answer:**

A node holds at most d − 1 keys and d pointers: 4(d − 1) + 6d ≤ 4096, so 10d ≤ 4100 and d = 410. With 8 and 8 bytes: 8(d − 1) + 8d ≤ 4096, 16d ≤ 4104, d ≤ 256.5, so d = 256 (4088 bytes used).

Task 2

**Insert into the lecture's example**

Draw the degree-4 tree `{ [ (1 2) 3 (5 6 7) ] 8 [ (9 10) 11 (12 13) 14 (14 16 17) 18 (19 20) ] }`. Insert 11, 4 and 15 – each into the *original* tree – and write down every split.

**Solution: insert 11:**

The search goes [8] → [11 14 18] → `(12 13)`. The leaf has room: `(11 12 13)`. Note that 11 goes into the leaf right of the separator 11, because 11 ≤ 11.

**Solution: insert 4:**

The leaf `(5 6 7)` is full, so 4 5 6 7 split into `(4 5)` and `(6 7)`; 6 is copied up and the parent becomes `[3 6]`:

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

**Solution: insert 15:**

`(14 16 17)` splits into `(14 15)` and `(16 17)`, 16 is copied up, the parent `[11 14 16 18]` has five children and splits into `[11 14]` and `[18]`, and 16 moves up into the root:

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

Task 3

**Delete from the lecture's example**

Draw the degree-4 tree `{ [ (6 9) 14 (14 15) 16 (16 17) ] 18 [ (18 20) 21 (21 25 30) ] }`. Delete 18, then 20, then 6 – this time one after the other. Name the case at every step.

**Delete 18:**

Underflow in `(20)`, no left sibling under the same parent, the right one can spare 21. Separator 21 → 25:

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

**Delete 20:**

`(21)` merges into `(21 25 30)`; its parent is left with one child and borrows `(16 17)` from the left sibling. The separators change 25 → 18 in the node and 18 → 16 in the root:

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

**Delete 6:**

`(9)` merges into `(9 14 15)`; its parent has one child and its sibling `[18]` only the minimum, so the two merge into `[16 18]`. The root has a single child left, which becomes the root:

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

**Run the solution: delete 18, 20, 6:**

Task 4

**Build a tree from scratch**

Start from an empty degree-4 tree and insert 20, 40, 60, 80, 90, 70, 50, 30 – the first lines of `fa.dat`. Then insert 55, 33 and 36. When does the tree get its second level, and when its third?

**Approach:**

The root leaf fills up with 20 40 60; inserting 80 splits it and creates the root [60]. After the eight inserts the tree has four leaves under a root with three separators:

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

55 and 33 fit into leaves. 36 splits `(20 30 33)`, the root would get five children and splits too – the third level appears:

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

Task 5

**How many keys fit?**

A degree-4 B+ tree has three levels. What is the largest and the smallest number of keys it can hold? Give an example tree for the smallest case.

**Answer:**

Most: 4 · 4 = 16 leaves with 3 keys each, 48 keys. Fewest: the root has 2 children, each of them 2 leaves, each leaf 2 keys – 8 keys, e.g. `{ [ (1 2) 3 (3 4) ] 5 [ (5 6) 7 (7 8) ] }`. Delete any key from it and the tree loses a level – step through it:

Task 6

**A separator that is not in the tree**

In the insertion example, delete 14. The key 14 still appears in an internal node afterwards. Is the result a valid B+ tree? What would go wrong if you replaced the separator with 16?

**Answer:**

It is valid: `(14 16 17)` becomes `(16 17)`, which still has the minimum two keys, and the separator 14 still divides `(12 13)` from `(16 17)` correctly. Replacing it with 16 would also be valid here, but the algorithm doesn’t do it: it would cost an extra write for nothing. Separators change only in a borrow or merge.

## 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.