B-tree and B+ tree — motivation (disk storage), properties: Worked examples

The scenario matrix

Every situation a B/B+ tree problem can throw at you falls into one of these cells. Each worked example below is tagged with the cell(s) it covers.

#	Case class	The tricky thing	Covered by
A	Degenerate: empty tree	first insert creates the root	Ex 1
B	Insert, no split	node has room, just slot it in	Ex 1
C	Insert forces a leaf split	median rises one level	Ex 2
D	Insert forces the ROOT to split	tree grows taller (only way!)	Ex 2
E	Cascading split	a split makes the parent full too	Ex 3
F	Delete, no underflow	plenty of keys, easy	Ex 4
G	Delete causes underflow → borrow	steal a key from a sibling	Ex 4
H	Delete causes underflow → merge	no sibling to lend → fuse + shrink	Ex 5
M	Delete from an INTERNAL node	replace by predecessor/successor	Ex 6
N	Cascading merge (deep underflow)	merge makes the parent underflow too	Ex 7
I	Limiting case: height bound	how tall can it get / disk-read count	Ex 8
J	B+ range query (word problem)	walk the linked leaves	Ex 9
K	Exam twist: choose $t$ from block size	fit one node into one disk block	Ex 10
L	B vs B+ insertion + contrast	B+ splits & where the data lives	Ex 11

Prerequisite links if any cell feels shaky: Binary Search Tree, Big-O Notation, Disk and Memory Hierarchy.

Worked examples

Example 1 — Cells A & B: empty tree, then painless inserts

Worked example Build a B-tree with

$t = 2$ : insert 10, 20, 5 into an empty tree. With $t = 2$ : max keys $= 2 t - 1 = 3$ , min (non-root) $= t - 1 = 1$ .

Forecast: Guess before reading — after all three inserts, is the root full? How many nodes total?

Steps

Insert 10 into the empty tree → create the root, put 10 in it. Root $= [10]$ . Why this step? An empty tree has no root; the first key always becomes the root (cell A). No parent to notify.
Insert 20. Root has room ( $1 < 3$ keys). Keep keys sorted → $[1020]$ . Why this step? Space exists, so we just slide it into sorted position (cell B). Sorted order is what makes the node a valid set of separators.
Insert 5. Still room ( $2 < 3$ ). Sorted insertion → $[51020]$ . Why this step? Now the root holds exactly $2 t - 1 = 3$ keys — full, but full is still legal. A split only happens when we try to insert into a node that is already full.

Verify: Node has 3 keys $= 2 t - 1$ ✓ (at capacity, not over). Keys sorted: $5 < 10 < 20$ ✓. One node, height 0 ✓.

Figure s01 shows the single root node filling up one key at a time — trace the blue node growing left to right, and note the last frame is drawn in pale yellow to flag "full but still legal".

Figure — B-tree and B+ tree — motivation (disk storage), properties

Example 2 — Cells C & D: the insert that splits the root (tree grows taller)

Worked example Continue Example 1's tree (root

$= [51020]$ , $t = 2$ ). Insert 15.

Forecast: The root is already full. Which key rises to become the new root — 5, 10, or 15? And does the tree get taller?

Steps

Target node = the root $[51020]$ , which is full ( $3 = 2 t - 1$ ). We split before inserting. Why this step? B-trees split a full node proactively on the way down. Splitting first guarantees we never overflow.
We split the four sorted values $[5, 10, 15, 20]$ . Definition of the median we promote: for a node that momentarily holds $2 t$ keys (here $2 t = 4$ , an even count), we promote the element at index $t$ counting from 1 — i.e. the $t$ -th smallest. With $t = 2$ that is the 2nd smallest $= 10$ . (This "lower median" tie-break is the standard convention; the "upper median" 15 also produces a valid tree, but we fix lower median for every example so answers are unique.) Push 10 up. Why this step? Promoting the $t$ -th value guarantees the left part gets $t - 1 = 1$ key and the right part gets $t - 1 = 1$ key — both meet the minimum-fill rule immediately.
Left child $= [5]$ , right child gets the rest sorted with 15 inserted $= [1520]$ . New root $= [10]$ . Why this step? Everything $< 10$ goes left, everything $> 10$ goes right — the BST-generalised separator property.
Height went from 0 to 1. Why this step? This is cell D: the only way a B-tree grows taller is a root split. That is why all leaves stay at the same depth — growth happens at the top, not the bottom.

Verify: Root $[10]$ has 1 key (root is allowed as few as 1) ✓. Children $[5]$ and $[1520]$ each have $\geq t - 1 = 1$ key ✓. Both leaves at depth 1 — same level ✓.

In figure s02 the pink node on the left is the overfull node; follow the yellow arrow across to the split result — the promoted median 10 sits in the yellow root, its two blue children hang below at one common depth.

Example 3 — Cell E: a cascading split

Worked example

$t = 2$ tree with root $[1020]$ and three children $[258]$ , $[121518]$ , $[2530]$ . Insert 16.

Forecast: 16 belongs in the middle child, which is already full. When it splits, what happens to the root — is it full too?

Steps

Route from root: $10 < 16 < 20$ → descend into middle child $[121518]$ , which is full. Why this step? We compare against separators to pick the subtree; 16 lies between 10 and 20.
Split $[121518]$ (plus incoming 16 → sorted values $[12, 15, 16, 18]$ ). Lower median = the $t$ -th = 2nd smallest $=$ 15 rises; children become $[12]$ and $[1618]$ . Why this step? Same lower-median rule as Example 2, applied at a leaf this time.
Insert separator 15 into the parent (root). Root was $[1020]$ → becomes $[101520]$ . Why this step? Every split hands one key up. The parent must absorb it.
Check the root: now $[101520]$ has 3 keys $= 2 t - 1$ — full but still legal. No further split needed this time. Why this step? This is the edge of cascading. Had the root already held 3 keys, absorbing 15 would overflow it and it too would split — pushing height up by 1. Cascades stop as soon as a node has room.

Verify: Root $[101520]$ : 3 keys $\leq 3$ ✓, and it now has 4 children $= k + 1 = 3 + 1$ ✓. Middle region split correctly: $12 < 15 < 16 < 18$ ✓.

Example 4 — Cells F & G: delete with no underflow, then delete with a borrow

Worked example

$t = 2$ (min non-root keys $= t - 1 = 1$ ). Root $[10]$ ; left leaf $[357]$ ; right leaf $[20]$ . (a) Delete 5. (b) From the result, delete 20.

Forecast: (a) is easy — why? (b) leaves the right leaf with zero keys, below the minimum. Where does its replacement come from?

Steps — part (a), cell F

5 is in leaf $[357]$ ; that leaf has 3 keys, deleting one leaves 2. Why this step? $2 \geq t - 1 = 1$ , so no rule is broken — a plain removal.
Result: left leaf $[37]$ , everything else unchanged. Why this step? No underflow means no restructuring — cheapest case.

Steps — part (b), cell G

Delete 20 from right leaf $[20]$ → it would become empty (0 keys $< t - 1 = 1$ ): underflow. Why this step? A non-root node must keep $\geq t - 1$ keys; empty is illegal.
Look at the sibling $[37]$ — it has $2 > t - 1$ , i.e. a spare key to lend. So we borrow. Why this step? Borrowing is preferred over merging whenever a sibling has more than the minimum — it avoids shrinking the tree.
Rotate through the parent: the sibling's largest key 7 moves up into the root; the old root separator 10 moves down into the deficient right leaf. Now left leaf $[3]$ , root $[7]$ , right leaf $[10]$ . Why this step? Keys must stay sorted around the separator. The parent key can't simply vanish; it slides down and the sibling's extreme key slides up to keep every separator valid.

Verify: After (b): $3 < 7 < 10$ across the tree ✓. Both leaves have $\geq 1$ key ✓. Root has 1 key ✓. Leaves at equal depth ✓.

Example 5 — Cell H: delete forcing a merge (tree shrinks)

Worked example

$t = 2$ . Root $[10]$ ; left leaf $[5]$ ; right leaf $[20]$ . Delete 20.

Forecast: The right leaf hits 0 keys. Its only sibling $[5]$ has just 1 key — exactly the minimum, nothing to lend. What happens now?

Steps

Delete 20 → right leaf empty → underflow. Why this step? Same rule: non-root needs $\geq t - 1 = 1$ key.
Check sibling $[5]$ : it has exactly $t - 1 = 1$ key. It cannot lend (lending would make it underflow). Why this step? Borrow is impossible when every sibling is at the minimum — so we merge.
Merge: pull the parent separator 10 down and fuse it with the sibling into one node. Result node $= [510]$ . Why this step? The separator's job (dividing left from right) disappears once the two children become one, so it joins the merged node as data.
The root loses its only key and becomes empty → the merged node becomes the new root. Height drops from 1 to 0. Why this step? This is the mirror image of Example 2: B-trees shrink from the top too. That symmetry is exactly what keeps all leaves at one depth.

Verify: Final single node $[510]$ : sorted ✓, $2 \leq 2 t - 1 = 3$ keys ✓, height 0 ✓. Total keys before delete $= 3$ (5,10,20), after $= 2$ ✓.

Figure s03: on the left, the pink node is the leaf that emptied and its min-sized sibling; the yellow arrow points to the fused result where separator 10 has dropped in to form the new single root.

Example 6 — Cell M: deleting a key that lives in an INTERNAL node

Worked example

$t = 2$ . Root $[15]$ ; left child $[510]$ ; right child $[2025]$ . Delete 15 — the key sitting inside the internal root.

Forecast: 15 is a separator, not a leaf key. If we just erase it, the root has no key to divide left from right. What replaces it?

Steps

Locate 15 — it is in an internal node (the root), separating child $[510]$ (all $< 15$ ) from child $[2025]$ (all $> 15$ ). Why this step? Deleting a leaf key is easy; deleting a separator is not — its slot must stay filled by some key or the ordering breaks.
Find the predecessor of 15: the largest key in the left subtree $= 10$ . (Equivalently we could take the successor, the smallest key of the right subtree $= 20$ ; either works — we pick predecessor by convention here.) Why this step? The predecessor is the closest value that still keeps everything-left $<$ separator $<$ everything-right. It is the natural stand-in — exactly like deleting a two-child node in a Binary Search Tree.
Overwrite the separator: root becomes $[10]$ . Now recursively delete 10 from the left leaf $[510]$ (it has moved up, so its old copy must go). Why this step? We've copied 10 upward; leaving it also in the leaf would duplicate a key, violating our distinct-keys rule.
Left leaf $[510]$ → delete 10 → $[5]$ . It has $1 = t - 1$ key: legal, no underflow. Final tree: root $[10]$ , children $[5]$ and $[2025]$ . Why this step? The recursive delete happens at a leaf, where removal is simplest; here it luckily stays at the minimum without triggering a borrow/merge.

Verify: Ordering holds: $5 < 10 < 20 < 25$ with 10 as separator ✓. Left leaf has $\geq t - 1 = 1$ key ✓, right leaf 2 keys ✓. Total keys before $= 5$ (5,10,15,20,25), after $= 4$ ✓.

Figure s04 shows the swap: the pink separator 15 in the root is crossed out, the blue predecessor 10 is lifted from the left leaf along the yellow arrow into the root, and the leaf shrinks to $[5]$ .

Example 7 — Cell N: a cascading merge (underflow that propagates up)

Worked example

$t = 2$ (min non-root keys $= 1$ ). A three-level tree:

root $[30]$
internal children $A = [1020]$ and $B = [40]$
leaves under $A$ : $[5]$ , $[15]$ , $[25]$ ; leaves under $B$ : $[35]$ , $[45]$ .

Delete 35.

Forecast: Deleting 35 empties a leaf under $B$ . $B$ has only one key — watch how one leaf-merge dominoes into an internal-node merge and shrinks the whole tree.

Steps

Delete 35 from leaf $[35]$ → empty → underflow. Its sibling under $B$ is $[45]$ , which has only $1 = t - 1$ key → cannot lend → merge the two leaves, pulling $B$ 's separator 40 down. Merged leaf $= [4045]$ . Why this step? Standard leaf merge (cell H) — but now $B$ has lost its only key.
Node $B$ is now empty (0 keys $< t - 1 = 1$ ): the underflow has propagated up one level. $B$ 's sibling is $A = [1020]$ , which has $2 > 1$ keys → it can lend! So instead of merging, we borrow through the root. Why this step? At every level we re-ask "borrow or merge?". Here $A$ has a spare, so we rotate: cheaper than merging.
Rotate: root separator 30 comes down into $B$ ; $A$ 's largest key 20 goes up into the root. Also move $A$ 's rightmost child (leaf $[25]$ ) over to become $B$ 's new leftmost child. Why this step? When an internal node borrows, it must also inherit one child pointer from the sibling, or the child count would be wrong. The leaf $[25]$ (everything between 20 and 30) rides along with separator 30.
Final: root $[20]$ ; child $A = [10]$ with leaves $[5]$ , $[15]$ ; child $B = [30]$ with leaves $[25]$ , $[4045]$ . Height stays 2. Why this step? Because a borrow was possible at the internal level, the cascade stopped — the tree did not shrink. (Had $A$ also been minimal, we'd have merged $A$ , $30$ , and $B$ into one node, the root would empty, and height would drop to 1 — the deeper cascade.)

Verify: Full in-order sequence: $5, 10, 15, 20, 25, 30, 40, 45$ — strictly increasing ✓. Every internal node has $\geq 1$ key and (keys $+ 1$ ) children ✓. Deleted 35 is gone; total keys $8$ → wait, before $= 9$ (5,15,25,10,20,30,40,45,35), after $= 8$ ✓. All leaves still at depth 2 ✓.

Figure s05: the pink path traces the delete of 35 causing $B$ to empty; the yellow arrows show separator 30 dropping into $B$ , key 20 rising to the root, and the orphan leaf $[25]$ sliding across to $B$ .

Example 8 — Cell I: limiting case — how tall can it get, how many disk reads?

Worked example A B-tree stores

$N = 1 0^{6}$ keys with minimum degree $t = 100$ . What is the maximum height, and hence the worst-case number of disk reads per lookup? Compare with a binary Binary Search Tree.

Forecast: Guess the height. Two? Ten? Thirty?

Steps

Use the parent's proven bound $h \leq lo g_{t} (\frac{N + 1}{2})$ . Why this step? This bound came from packing the fewest keys per level — that produces the tallest legal tree, i.e. the worst case.
Plug in: $h \leq lo g_{100} (\frac{1 0 ^{6} + 1}{2}) = lo g_{100} (500000.5) \approx lo g_{100} (5 \times 1 0^{5})$ . Why this step? $(N + 1) /2$ with $N = 1 0^{6}$ is about $5 \times 1 0^{5}$ .
Change of base so we can compute it: $lo g_{100} (5 \times 1 0^{5}) = \frac{lo g _{10} ( 5 \times 1 0 ^{5} )}{lo g _{10} ( 100 )}$ . The denominator is easy: $lo g_{10} (100) = 2$ because $1 0^{2} = 100$ . The numerator: $lo g_{10} (5 \times 1 0^{5}) = lo g_{10} 5 + lo g_{10} 1 0^{5} = 0.699 + 5 = 5.699$ . So $h \leq \frac{5.699}{2} \approx 2.85$ . Why this step? Base-10 logs are the ones we can read off by hand ( $lo g_{10} 5 \approx 0.699$ is worth memorising); change-of-base turns the awkward base-100 log into that. Height is an integer $\leq 2.85$ , so $h \leq 2$ .
Each level = exactly one block read → at most 3 disk reads (root + 2 levels) for any lookup. Why this step? One node lives in one disk block; visiting a level costs one I/O (see Disk and Memory Hierarchy).

Verify (sanity / contrast): A binary BST needs $lo g_{2} 1 0^{6} \approx 20$ reads. Ratio $\approx 20/3 \approx 7 \times$ fewer reads — and this is the whole reason B-trees exist. Bound value $2.85$ ✓.

Example 9 — Cell J: B+ tree range query (word problem)

Worked example A database index is a B+ tree on

age. The leaves, in sorted order and linked, are: [8 12] ⇄ [15 19] ⇄ [22 27] ⇄ [31 40]. Run WHERE age BETWEEN 14 AND 28. How many leaf blocks are read?

Forecast: Does the query bounce back up to the root between matches, or slide sideways?

Steps

Descend from the root once to find the leaf containing the lower bound 14. That is leaf $[1519]$ (14 would sit here; 15 is the first key $\geq 14$ ). Why this step? In a B+ tree all data is in leaves (see Database Indexing); the search always ends at a leaf, never at an internal separator.
Emit 15, 19 (both $\leq 28$ ). Reach the end of this leaf. Why this step? Collect every key in $[14, 28]$ from this block.
Follow the leaf link rightward to $[2227]$ . Emit 22, 27 (both $\leq 28$ ). Why this step? The linked leaves let us walk sequentially — no return trip to the root. This is B+ tree's signature advantage for ranges.
Follow the link to $[3140]$ : first key 31 $> 28$ → stop. Why this step? Once a key exceeds the upper bound, no later leaf can contain a match (leaves are globally sorted).
Count leaf blocks touched: $[1519]$ , $[2227]$ , $[3140]$ = 3 leaf reads (the third is read only to discover we're past the range). Why this step? Each leaf visited is one block I/O; we stop the instant we overshoot.

Verify: Result set ${15, 19, 22, 27}$ — all lie in $[14, 28]$ ✓, none outside (12 excluded as $< 14$ , 31 excluded as $> 28$ ) ✓. Blocks read $= 3$ ✓.

Example 10 — Cell K: exam twist — pick $t$ from the disk block size

Worked example Disk block

$= 4096$ bytes. Each B-tree entry stores a key (8 bytes) + a child pointer (8 bytes) $= 16$ bytes. Roughly what maximum degree fits in one block, and what minimum degree $t$ does that imply?

Forecast: Hundreds of children, or thousands?

Steps

Entries per block $\approx \frac{4096}{16} = 256$ . Why this step? We want one node = one block so a node fetch costs exactly one I/O (the parent's core insight).
Each node holds up to $2 t - 1$ keys with $2 t$ child pointers. Approximate max children $= 2 t \approx 256 \Rightarrow t \approx 128$ . Why this step? The block budget caps the fanout; solving $2 t = 256$ gives the largest legal $t$ .
So max keys $= 2 t - 1 = 255$ , children up to $256$ . Why this step? These are the numbers you'd actually configure the index with.

Verify: $2 \times 128 = 256$ pointers, $256 \times 16 = 4096$ bytes $=$ one block ✓. Max keys $2 (128) - 1 = 255$ ✓. A bigger $t$ would need a node larger than one block → multiple I/Os per node, killing the benefit (see the parent's "make $t$ enormous" mistake).

Example 11 — Cell L: B+ tree insertion (with a leaf split) vs the B-tree on the same keys

Worked example Insert 1, 2, 3, 4, 5 with

$t = 2$ into (a) a B-tree and (b) a B+ tree, showing the B+ split mechanics. Where do the actual records 1..5 end up in each?

Forecast: In which structure does a key appear twice? And when a B+ leaf splits, does the median move up or get copied up?

Steps — (a) B-tree

As derived in the parent: after all inserts, root $= [2]$ , leaves $= [1]$ and $[345]$ . Why this step? Splits push medians up; 2 becomes the separator and holds the real record 2 in the internal node.
Each value appears once. A search for 2 can stop at the internal node. Why this step? In a plain B-tree, data lives in every node, so a hit can end anywhere.

Steps — (b) B+ tree (watch the split rule differ)

Insert 1,2 → single leaf $[12]$ (this leaf is also the root for now). Max leaf keys with $t = 2$ is $2 t - 1 = 3$ . Why this step? Same capacity rule; a B+ leaf holds up to $2 t - 1$ real records.
Insert 3 → leaf $[123]$ — full. Why this step? At capacity, next insert triggers a leaf split.
Insert 4 → leaf must split. Sorted values $[1, 2, 3, 4]$ . Key B+ difference: the median 3 is copied up (not moved) — it becomes a router in a new internal root and stays as real data in the right leaf. Leaves: $[12] ⇄ [34]$ , internal root $[3]$ . Why this step? In a B+ tree every record must remain in a leaf, so on a leaf split the separator is a copy. (Contrast: in a B-tree the median moves up and leaves no copy.) This is the single most-tested B/B+ distinction.
Insert 5 → goes to right leaf $[34]$ → $[345]$ (room, no split). Final B+: internal root $[3]$ ; leaves $[12] ⇄ [345]$ . Why this step? $[34]$ had room for one more before hitting $2 t - 1 = 3$ .
The key 3 now appears twice: once as a router upstairs, once as real data in the leaf. Searching for 3 must descend to the leaf. Why this step? A separator that equals your search key is not the record — see the parent's steel-manned mistake. You always finish at a leaf in a B+ tree.

Verify: B-tree total stored keys $= 5$ (no duplicates) ✓. B+ tree leaf keys $= {1, 2, 3, 4, 5}$ (all 5 records present in leaves) ✓, with router 3 duplicated → 6 key-slots total ✓. B+ leaf link $[12] \to [345]$ keeps global order ✓.

Recall Quick self-test (cover the answers)

Why is $t = 1$ forbidden? ::: Then min keys $= t - 1 = 0$ and max $= 1$ ; nodes could be empty and there is no median to promote — the algorithms break. Empty tree, first insert 42 with $t = 3$ — what is the tree? ::: A single root node $[42]$ ; the first key always becomes the root. $t = 2$ , splitting the four values $[5, 10, 15, 20]$ — which rises, by what rule? ::: The lower median, the $t$ -th (2nd) smallest $= 10$ . A B-tree's height only increases when… ::: the root splits (growth happens at the top → all leaves stay level). Deleting a key that sits in an internal node — what replaces it? ::: Its predecessor (largest of left subtree) or successor (smallest of right subtree), then delete that copy from the leaf. A leaf merge empties its parent internal node — then what? ::: The underflow cascades up: borrow from an internal sibling if possible, else merge again (possibly shrinking the tree). $N = 1 0^{6}$ , $t = 100$ — worst-case disk reads per lookup? ::: $\leq 3$ , since $h \leq lo g_{100} (5 \times 1 0^{5}) \approx 2.85$ . On a B+ leaf split, is the median moved or copied up? ::: Copied — the record must stay in a leaf.