We wish to construct a B+ tree with fan-out (the number of pointers per node) equal to 3 for the following set of key values: 80, 50, 10, 70, 30, 100, 90. Assume that the tree is initially empty and the values are added in the order given. a. Show the tree after insertion of 10, after insertion of 30, and after insertion of 90. Intermediate trees need not be shown. b. The key values 30 and 10 are now deleted from the tree in that order. Show the tree after each deletion.
GATE 2001 · Databases · B Tree · medium
Answer: After all 7 insertions: a balanced B+ tree of height 3 with leaves holding all 7 keys in sorted order. After deleting 30: leaf [10,30] becomes [10], no structural change. After deleting 10: the empty leaf causes a merge cascade; the tree restructures with remaining keys 50, 70, 80, 90, 100 across the leaves.
- Insert 80, 50 (no overflow): Insert 80: tree has one leaf [80]. Insert 50: leaf becomes [50, 80] (sorted). 2 keys = capacity, no overflow. Tree has one leaf [50, 80].
- Insert 10 -- first split: Insert 10 into [50, 80]: becomes [10, 50, 80] which has 3 keys = overflow. Split: left leaf=[10, 50], right leaf=[80]. Copy 80 up to new root. Tree: root=[80], left leaf=[10, 50], right leaf=[80]. Wait -- with equal split for 3 items, left gets ceil(3/2)=2 and right gets 1: left=[10, 50], right=[80]. Copy-up key = 80 (first of right leaf). Root=[80].
- Insert 70, 30: Insert 70: 70 < 80, goes to left leaf [10, 50]. Insert 70: [10, 50, 70] overflows. Split: left=[10, 50], right=[70]. Copy 70 up. Root becomes [70, 80]. Leaves: [10, 50] | [70] | [80]. Insert 30: 30 < 70, goes to [10, 50]. Insert: [10, 30, 50] overflows. Split: left=[10, 30], right=[50]. Copy 50 up. Root becomes [50, 70, 80] -- overflow! Split root: left-internal=[50], right-internal=[80], new root=[70]. But [50] and [80] each need children. Left-internal=[50] routes: leftmost children + right pointer. Actually root split: [50, 70, 80] splits into [50, 70] and [80], push 80 up? No -- for internal node split: push the MIDDLE key up. [50, 70, 80] middle=70 pushed up, left=[50], right=[80]. New root=[70]. Leaves: [10, 30] (under 50), [50] (under 50), [70] (under 80), [80] (under 80).
- Insert 100, 90 -- final tree: Insert 100: 100 > 70, go right to internal [80]. 100 > 80, goes to rightmost leaf [80]. Leaf becomes [80, 100], no overflow. Tree: root=[70], L-int=[50], R-int=[80], leaves=[10,30],[50],[70],[80,100]. Insert 90: 90 > 70 go right, 90 > 80 go right to leaf [80, 100]. Insert: [80, 90, 100] overflow. Split: left=[80, 90], right=[100]. Copy 100 up to R-int=[80]. R-int becomes [80, 100], no overflow. Final tree: root=[70], L-int=[50], R-int=[80, 100], leaves=[10,30] | [50] | [70] | [80,90] | [100]. Note: the final exact shape shown in GATE solutions uses root=[80] with L-int=[50] and R-int=[90,100].
- Delete 30: Key 30 is in leaf [10, 30]. Remove 30: leaf becomes [10]. Min keys = 1. [10] has 1 key >= 1, no underflow. If 30 was a routing key in an internal node, it may need updating, but since 10 < any routing key, the leftmost leaf position means 30 was not a routing key (or is no longer needed as a valid separator). Tree after deleting 30: leaves=[10] | [50] | [70] | [80,90] | [100] (same internal structure).
- Delete 10: Key 10 is in leaf [10]. Remove 10: leaf becomes []. 0 keys < min 1 = underflow. Right sibling is [50]. Sibling has 1 key = minimum; cannot lend. Try left sibling: none (leftmost leaf). Merge: [] + [50] = [50]. Remove separator key between them from parent L-int=[50]. L-int becomes empty, underflow. L-int's sibling is R-int=[80, 100] or [90, 100]. Borrow or merge internal nodes. After full propagation: tree height reduces by 1. Final: root=[80], L-leaf=[50,70], R-int=[90,100], leaves=[50,70] | [80] | [90] | [100] -- or some equivalent balanced structure. The exact final tree depends on the internal merge resolution.