5.5.2 · B-tree search and insertion with node splits

0 · Recall Warm-up

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

B-tree of order 5: max keys and min children of a non-root internal node? from Lesson 5.5.1
In an m-way search tree, how is a search done? from Lesson 5.4.1
What is the order of a B-tree with B = 1024, K = 9, P = 6, Pr = 7? from Lesson 5.5.1

1 · The Hook

Insert 10, 20, 30, 40, 50, 60, 70 one by one into an empty B-tree whose nodes hold at most 2 keys. Where does the tree grow: at the bottom like most trees, or at the top? B-trees grow upwards: a full node splits and pushes its middle key to its parent, and only a root split adds a new level. That is why all leaves always stay on the same level.

2 · Predict First

A leaf holds 10 and 20 (full, max 2 keys). You insert 30. What happens?

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

3 · Core Concept

Predict First — the answer

The leaf would hold 10, 20, 30: one too many. It splits: 10 stays left, 30 goes right, and the middle key 20 moves up to the parent. There is no parent, so 20 becomes a new root. The tree now has 2 levels.

Search

Start at the root. In a node with keys k₁ < … < k_m: if the key equals some kᵢ, stop (B-trees can find a key in an internal node). Otherwise go to the child between the two keys around it. Repeat. Cost ≤ height (one block per level).

Insertion

Search for the key; it is always inserted into a leaf, in sorted position.
If the leaf now has at most p − 1 keys, stop.
Overflow (p keys): split the node into two; the median key moves up into the parent; left keys go to the left node, right keys to the right node.
The parent gained a key; if it overflows, split it too (median moves up again).
If the root splits, its median becomes a new root: the height grows by 1.

With an odd number of keys at overflow (p odd), the median is unique. For an even count, books differ (left- or right-biased); GATE questions using such orders state the rule.

Full trace: max 2 keys per node (order 3), insert 10, 20, 30, 40, 50, 60, 70

Insert	Result (level by level)	Splits
10, 20	[10 20]	0
30	[20] / [10] [30]	1 (root grows)
40	[20] / [10] [30 40]	0
50	[20 40] / [10] [30] [50]	1
60	[20 40] / [10] [30] [50 60]	0
70	[40] / [20] [60] / [10] [30] [50] [70]	2 (leaf, then root)

Total 4 splits, final height 3.

Cost of an insert

Read the path down (height blocks), then write the changed nodes: a split writes two nodes and changes the parent. In the worst case splits propagate to the root.

4 · Visual

After inserting 10 … 70 with at most 2 keys per node: 4 splits, height 3. Every leaf is on level 3.

5 · Worked Examples

Example 1 Easy

Order 5 (max 4 keys). Insert 10, 20, 30, 40, 50 into an empty B-tree. What does the tree look like?

Solution

After 40 the root leaf is full [10 20 30 40]. Inserting 50 gives 5 keys: split, median 30 moves up: root [30], leaves [10 20] and [40 50]. 1 split.

Example 2 Medium

Continue: insert 60, 70, 80, 90.

Solution

60, 70 go to [40 50] → [40 50 60 70]. 80 overflows it: [40 50 60 70 80], median 60 up: root [30 60], leaves [10 20], [40 50], [70 80]. 90 → [70 80 90]. Final: root [30 60], leaves [10 20], [40 50], [70 80 90]; 2 splits in all.

Example 3 GATE

Max 2 keys per node. Insert 3, 7, 1, 9, 5, 11, 13, 2 into an empty B-tree. How many splits, and what is the root at the end?

Solution

3, 7 → [3 7]; 1 → split, root [3], leaves [1] [7]; 9 → [7 9]; 5 → [5 7 9] splits, 7 up: root [3 7], leaves [1] [5] [9]; 11 → [9 11]; 13 → [9 11 13] splits, 11 up → root [3 7 11] overflows, splits, 7 up. 2 → [1 2]. 4 splits, root [7].

6 · GATE Traps

New keys always go into a leaf first.
The median moves up (B-tree): it does not stay in either half.
Height grows only when the root splits.
One insert can cause several splits (a cascade up the path).
Count splits per node split, including the root split.

7 · Memory Hook

"Fill, overflow, split, push the middle up." The tree grows from the top, like a tower that lifts its own roof.

8 · Connect the Dots

Lesson 5.5.1 defined the B-tree; this lesson grew one by splitting full nodes. Next: shrinking: deletion with borrowing and merging, and the formulas for the smallest and largest number of keys a B-tree of given height can hold.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Splits

Max 2 keys per node. Insert 10, 20, 30, 40, 50 into an empty B-tree. How many splits?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Height

Max 2 keys per node. After inserting 10, 20, 30, 40, 50, 60, 70 (in order), what is the height (levels)?

Numerical answer: ________

Q3 · MCQ · 2 mark(s) — Root

Order 5 (max 4 keys). After inserting 1, 2, 3, 4, 5, 6, 7, 8, 9 into an empty B-tree (median moves up on a 5-key overflow), the root holds:

(A) [3]
(B) [3 6]
(C) [3 6 9]
(D) [5]

Q4 · MCQ · 1 mark(s) — Growth

A B-tree's height increases when:

(A) the root splits
(B) a key is inserted into a full leaf
(C) a node has fewer than ⌈p/2⌉ children
(D) any leaf splits

Q5 · MSQ · 2 mark(s) — Insertion

Which are true for B-tree insertion?

(A) A new key is first placed in a leaf.
(B) Leaves may end up on different levels.
(C) On overflow the median key moves to the parent.
(D) A single insertion can cause more than one split.

10 · Rule Card

Search: compare in node, stop if found, else follow the matching child; ≤ height accesses.
Insert into a leaf; on overflow (p keys) split, median moves up; cascade; root split → height + 1.
Trace format: level-by-level brackets; count every node split.

11 · Concept Ledger

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

B-tree searchB-tree insertionoverflownode splitmedian moves uproot split (height growth)split cascade

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

4 keys; 3 children.
Compare with the node's keys, follow the child between the right keys, one node per level.