Question 2 of 8

Question 2 (4+4+12=20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) Equality search vs. range search (condensed — see Q1(d)). An equality search retrieves the record(s) matching one exact key value and can stop at the first qualifying leaf; a range search retrieves every record whose key lies within a bounded interval and must keep scanning — via a sorted file's physical order or a B+-tree's linked leaf chain — until the upper bound is exceeded. The two share the same index descent but differ entirely in how much of the leaf level they must subsequently visit.

(b) Does insertion order affect the final B+-tree structure? Yes. The final set of keys stored is always the same regardless of insertion order, but the tree's shape — which keys get promoted as internal separators, how many levels the tree grows to, and how keys are grouped across leaves — is a direct consequence of exactly when each node happened to overflow, and overflow timing depends entirely on the sequence of insertions. Part (c) below is itself a demonstration of this fact: reconstructing "the original tree" from a final B+-tree turns out to be ambiguous precisely because different insertion histories (different original trees, different inserted keys) can converge on the exact same final structure — the tree "forgets" its own construction history once built.

(c) Reconstruct the pre-insertion tree and the inserted key.

Given. The final B+-tree (order 3: at most 2 keys / 3 children per node): root key 16; its left child (internal) holds key 8 over leaves [1] and [10,15]; its right child (internal) holds key 19 over leaves [17] and [19,20]; all four leaves linked left to right.

Find. The tree that existed immediately before the one insertion, the key that was inserted, and whether that reconstruction is unique.

Approach. A single leaf split that cascades into a root split always leaves the new root holding exactly one key (the promoted median of the temporarily-overflowed 3-key root) with two brand-new internal children — that signature is present here (the root holds only 1 key), so work backwards: recover the overflowed root's 3 keys, identify which pair of adjacent leaves is structurally consistent with having just been split, then reconstruct the leaf's pre-insertion contents.

1. Recover the temporarily-overflowed root's 3 keys. An internal-node split promotes its median key to the new parent and keeps the smallest key in the left half, the largest in the right half. So the overflowed root's 3 keys, sorted, are exactly {left-child's key, root's key, right-child's key} = {8, 16, 19}.
2. Identify which leaf pair was just split. A leaf split promotes precisely the smallest key of the newly-created right leaf into its parent. Checking the left pair, [1] / [10,15]: the right leaf's minimum is 10, which is not one of {8,16,19} — so this pair was not just split; both leaves, and the separator 8 between them, already existed before this insertion. Checking the right pair, [17] / [19,20]: the right leaf's minimum is 19, which is one of the recovered root keys — consistent with 19 being the just-promoted separator. $$\boxed{\text{The split happened under the right subtree, promoting } 19}$$
3. Reconstruct the pre-insertion root and leaves. Since 19 was promoted just now, the two original root keys (before insertion) were the other two recovered values, {8, 16}. Before insertion the tree therefore had only 2 levels: a root with keys [8, 16] directly over 3 leaves — [1], [10,15], and a third leaf holding 2 of the 3 keys currently split across [17] and [19,20], i.e. 2 of {17, 19, 20}. The insertion added the missing third key, overflowing that leaf to 3 keys, splitting it into [17] / [19,20], and promoting 19 — which then overflowed the (now 3-key) root, triggering the second, cascading root split that produced the final 3-level shape.
4. Enumerate every candidate for the inserted key. Because a leaf split only depends on the final sorted set of keys that overflowed it — not on which one arrived last — all three ways of choosing "2 of {17,19,20} as the original leaf, the third as the inserted key" reconstruct to the identical final tree: inserting 17 into a leaf that already held {19,20}; inserting 19 into a leaf that already held {17,20}; or inserting 20 into a leaf that already held {17,19}. $$\boxed{\text{3 equally valid reconstructions} \Rightarrow \text{the solution is NOT unique}}$$

Is the solution unique? No. A B+-tree records only the final, sorted arrangement of keys — it keeps no memory of the order in which those keys arrived. Once three keys have overflowed one leaf and it has split, there is no way to tell from the resulting structure alone which one of the three was the "new" arrival; any of them is equally consistent with the observed final tree. The original root's OTHER two keys (8 and 16, over the unchanged leaves [1] and [10,15]), and the fact that exactly one leaf on the right side must have held 2 of {17,19,20}, are uniquely determined — only the specific identity of the newly-inserted key among the three is ambiguous.