5.5.3 · B-tree deletion basics; min/max keys; height bounds

0 · Recall Warm-up

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

What happens to the median key when a B-tree node splits? from Lesson 5.5.2
When does a B-tree's height increase? from Lesson 5.5.2
Max nodes in a full m-ary tree with h levels? from Lesson 5.4.1

1 · The Hook

Deleting from a B-tree must keep every non-root node at least half full. A node that drops below the minimum borrows a key from a sibling or merges with one. GATE asks more about the consequences than the steps: "what is the minimum number of keys a B-tree of order p and height h can hold?" and "what is the maximum height for n keys?"

2 · Predict First

A B-tree of order 3 (max 2 keys, min 1 key per non-root node) has 3 levels. What is the largest number of keys it can hold? The smallest?

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

3 · Core Concept

Predict First — the answer

Largest: every node full: 1 + 3 + 9 = 13 nodes × 2 keys = 26 = 3³ − 1. Smallest: root with 1 key and 2 children, every other node with 1 key and 2 children: 1 + 2 + 4 = 7 nodes × 1 key = 7 = 2 × 2² − 1.

Deletion (outline)

Key in an internal node: replace it by its predecessor (largest key in the left subtree) or successor (smallest in the right subtree), which is in a leaf; then delete that key from the leaf.
Delete from a leaf. If the leaf still has ≥ ⌈p/2⌉ − 1 keys (or it is the root), stop.
Underflow (too few keys):
- Borrow (redistribute): if an adjacent sibling has more than the minimum, move the separating parent key down into the underflowing node and the sibling's nearest key up into the parent.
- Merge: otherwise, merge the node with a sibling and the separating key from the parent. The parent loses one key and may underflow in turn.
If the root loses its last key (its two children merged), the merged child becomes the new root: height decreases by 1.

Capacity bounds (order p = max children, height h in levels)

Let m = ⌈p/2⌉ (minimum children of a non-root internal node).

Maximum keys: all nodes full, (p^h − 1)/(p − 1) nodes × (p − 1) keys = p^h − 1.
Minimum keys: root has 1 key and 2 children; every other internal node has m children and m − 1 keys; all leaves have m − 1 keys: 2·m^(h−1) − 1.

Height bounds for n keys

Minimum height: smallest h with p^h − 1 ≥ n → h_min = ⌈log_p (n + 1)⌉.
Maximum height: largest h with 2·m^(h−1) − 1 ≤ n → h_max = 1 + ⌊log_m ((n + 1)/2)⌋.

Example

p = 5 (m = 3), h = 3: max keys 5³ − 1 = 124; min keys 2·3² − 1 = 17. n = 1000 keys, p = 5: h_min = ⌈log₅ 1001⌉ = 5 (5⁴ = 625 < 1001 ≤ 3125); h_max = 1 + ⌊log₃ 500.5⌋ = 1 + 5 = 6 (3⁵ = 243 ≤ 500.5 < 729).

4 · Visual

Merge on underflow (order 3: min 1 key per non-root node)

      [20 40]                      delete 30            [40]
     /   |   \                     ---------->         /    \
  [10]  [30]  [50]          [30] becomes empty;    [10 20]  [50]
                            sibling [10] has no spare key,
                            so merge [10] + 20 (from parent) + []

5 · Worked Examples

Example 1 Easy

Order p = 4 (m = 2). Max and min keys for height 2?

Solution

Max 4² − 1 = 15. Min 2·2¹ − 1 = 3.

Example 2 Medium

Order p = 3. What is the maximum height of a B-tree holding 20 keys?

Solution

m = 2: 2·2^(h−1) − 1 ≤ 20 → 2^h ≤ 21 → h ≤ 4. h_max = 4. (Check: height 4 needs at least 15 keys; height 5 needs 31.)

Example 3 GATE

Order p = 3. A B-tree with keys in the root [20 40] and leaves [10], [30], [50]. Delete 30. Describe the result.

Solution

Leaf [30] becomes empty (minimum 1). Siblings [10] and [50] have no spare key, so merge with a sibling: [10] + 20 (pulled down from the parent) + [] = [10 20]. The parent becomes [40] with children [10 20] and [50]. Height unchanged.

6 · GATE Traps

Max keys = p^h − 1 (height in levels), not p^h.
Min keys uses ⌈p/2⌉ for every node except the root, which has 1 key.
Merging pulls the separating key down from the parent; borrowing rotates a key through the parent.
Height only decreases when the root empties.

7 · Memory Hook

"Borrow if your neighbour is rich, merge if you are both poor." Bounds: "Full tree: p^h − 1. Skinny tree: 2m^(h−1) − 1."

8 · Connect the Dots

Chapter 5.5 is complete: structure, insertion, deletion and capacity of B-trees. Next: the Chapters 5.4–5.5 Lock-in, then the B+ tree, the variant almost every real DBMS uses: data only in the leaves, leaves linked in a chain.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · NAT · 2 mark(s) — Max keys

B-tree of order 6 (max children), height 3 levels. Maximum number of keys?

Numerical answer: ________

Q2 · NAT · 2 mark(s) — Min keys

B-tree of order 6 (m = 3), height 3 levels. Minimum number of keys?

Numerical answer: ________

Q3 · NAT · 2 mark(s) — Max height

B-tree of order 5 holding 100 keys. Maximum height?

Numerical answer: ________

Q4 · NAT · 1 mark(s) — Min height

B-tree of order 10 holding 999 keys. Minimum height?

Numerical answer: ________

Q5 · MCQ · 1 mark(s) — Underflow

A leaf underflows and its sibling has exactly the minimum number of keys. The fix is to:

(A) borrow from the sibling
(B) delete the parent
(C) merge with the sibling and the separating parent key
(D) split the leaf

10 · Rule Card

Delete internal key → swap with predecessor/successor in a leaf. Leaf underflow → borrow (rotate through parent) or merge (with parent's separator). Root emptied → height − 1.
Max keys (height h) = p^h − 1. Min keys = 2⌈p/2⌉^(h−1) − 1.
h_min = ⌈log_p(n + 1)⌉; h_max = 1 + ⌊log_⌈p/2⌉((n + 1)/2)⌋.

11 · Concept Ledger

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

B-tree deletionunderflowborrow (redistribution)mergepredecessor / successor replacementmax keys p^h − 1min keys 2⌈p/2⌉^(h−1) − 1height bounds

12 · Answer Vault

Reveal answers when you’re ready

Recall Warm-up

It moves up into the parent.
When the root splits.
(m^h − 1)/(m − 1).