5.6.3 · B+ tree insertion and deletion traces; height and capacity; B vs B+

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

B = 512, K = 9, P = 6, Pr = 7: internal and leaf orders of a B+ tree? from Lesson 5.6.2
What moves up when a B-tree node splits? from Lesson 5.5.2
How does a range query use a B+ tree? from Lesson 5.6.1

1 · The Hook

B+ tree insertion looks like B-tree insertion with one twist: when a leaf splits, the first key of the new right leaf is copied up (it must stay in the leaf, where the data pointer lives). When an internal node splits, its middle key moves up (internal keys are only signposts). GATE traces test exactly this difference.

2 · Predict First

A B+ tree leaf holds at most 2 keys and is [10 20]. Insert 30. What do the leaves and the parent look like? Is 30 still in a leaf?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

Overflow [10 20 30] → split: left [10 20], right [30] (left keeps the larger half, ⌈3/2⌉ = 2). The first key of the right leaf, 30, is copied up: root [30]. Yes, 30 stays in its leaf.

Insertion

Search down to the correct leaf; insert ⟨key, pointer⟩ in order.
Leaf overflow (p_leaf + 1 entries): split; the left leaf keeps the first ⌈(p_leaf + 1)/2⌉ entries, the right leaf the rest; fix the next-leaf pointers; copy the right leaf's first key into the parent.
Internal overflow (p children, i.e. p keys after insertion, one too many): split; the middle key moves up (it is not kept in either half).
Root split → new root → height + 1.

Full trace: max 2 keys in internal nodes and leaves (p = 3, p_leaf = 2), insert 10, 20, …, 70

Insert	Root / internal	Leaves	Splits
10, 20		[10 20]	0
30	[30]	[10 20] [30]	1 (leaf; 30 copied up)
40	[30]	[10 20] [30 40]	0
50	[30 50]	[10 20] [30 40] [50]	1 (leaf)
60	[30 50]	[10 20] [30 40] [50 60]	0
70	[50] / [30] [70]	[10 20] [30 40] [50 60] [70]	2 (leaf, then root: 50 moves up)

Total 4 splits, height 3. Notice: 30, 50, 70 appear both inside and in leaves; 50 left the old root when it moved up.

Deletion (outline)

Delete the entry from its leaf.
If the leaf underflows (fewer than ⌈p_leaf/2⌉ entries): borrow an entry from a sibling and update the separator in the parent, or merge with a sibling and delete the separator from the parent (which may underflow in turn and borrow/merge the same way, with B-tree rules).
A deleted key may remain as a separator in internal nodes: it still routes correctly.

B-tree vs B+ tree

	B-tree	B+ tree
Record pointers	in every node	only in leaves
Each key appears	once	in a leaf, plus possibly as a separator
Internal fan-out	lower	higher (shorter tree)
Search ends	anywhere	always at a leaf
Range / sequential scan	awkward (tree walk)	easy (leaf chain)
Leaf split	median moves up	first right key copied up
Used by real DBMSs	rarely	almost always

4 · Visual

After inserting 10 … 70 (at most 2 keys per node): leaf splits copied 30, 50, 70 up; the root split moved 50 up.

5 · Worked Examples

Example 1 Easy

p_leaf = 3 (max 3 keys per leaf), internal max 3 keys. Insert 5, 10, 15, 20. What is the tree?

Solution

[5 10 15] then 20 overflows: [5 10 15 20] → left keeps ⌈4/2⌉ = 2: [5 10], right [15 20]; copy 15 up. Root [15], leaves [5 10], [15 20].

Example 2 Medium

Continue with 25, 30, 35.

Solution

25 → [15 20 25]. 30 → [15 20 25 30] splits into [15 20] and [25 30]; copy 25: root [15 25]. 35 → [25 30 35]. Final: root [15 25], leaves [5 10], [15 20], [25 30 35]; 2 splits.

Example 3 GATE

In the 10 … 70 trace, how many keys are stored in internal nodes at the end, and how many in leaves?

Solution

Internal: [50], [30], [70] → 3 keys. Leaves: all 7 keys.

6 · GATE Traps

Leaf split: copy the first key of the right leaf up. Internal split: move the middle key up.
Every key stays in the leaf level; internal keys are extra copies.
Count both leaf and internal splits.
After deletion a separator may name a key that no longer exists; that is allowed.

7 · Memory Hook

"Leaves copy, branches move."

8 · Connect the Dots

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Splits

Max 2 keys in every node (B+ tree, p_leaf = 2). Insert 10, 20, 30, 40, 50 into an empty tree. How many splits?

Numerical answer: ________

Q2 · MCQ · 2 mark(s) — Root

p_leaf = 3 and internal nodes hold at most 3 keys. Insert 5, 10, 15, 20, 25, 30, 35 into an empty B+ tree. The root is:

(A) [15 25]
(B) [20]
(C) [15]
(D) [25]

Q3 · MCQ · 1 mark(s) — Copy vs move

When a B+ tree leaf splits, the key sent to the parent is:

(A) copied, so it stays in the leaf
(B) deleted
(C) moved out of the leaf
(D) sent to the sibling

Q4 · NAT · 1 mark(s) — Keys

In a B+ tree with 7 leaves holding 20 keys in total, how many of those 20 keys appear in the leaf level?

Numerical answer: ________

Q5 · MSQ · 2 mark(s) — Comparison

Which are advantages of a B+ tree over a B-tree?

(A) Higher internal fan-out
(B) Efficient range queries through the leaf chain
(C) Every search can stop at the root
(D) Uniform search cost (always reaches a leaf)

10 · Rule Card

Insert into leaf; leaf overflow → split (left keeps ⌈(p_leaf+1)/2⌉), copy right's first key up; internal overflow → split, move middle key up; root split → height + 1.
Delete from leaf; underflow → borrow (update separator) or merge (remove separator); separators may be stale.
B vs B+: record pointers everywhere vs leaves only; lower vs higher fan-out; awkward vs easy ranges; median up vs copy up.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

B+ tree insertionleaf split copies key upinternal split moves key upB+ tree deletion (borrow / merge)B-tree vs B+ tree comparison

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

34 and 31.
The median key.
Descend to the low key, then follow the leaf chain.