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. An equality search asks for the record(s) whose search-key value equals one specific value (e.g. "find the student with SID = 12345"); a range search asks for every record whose key falls between two bounds (e.g. "find all students with GPA between 3.0 and 4.0"), potentially returning many records. On a B+-tree, both start with the identical top-down traversal — comparing the target/lower-bound key against each internal node's separators to descend to the correct leaf — but they differ at the leaf level: an equality search stops once it finds (or fails to find) the matching key in that one leaf, while a range search continues scanning forward along the leaf-level linked list from that starting point, collecting every key up to the upper bound, hopping across leaf boundaries via the sibling pointers until the range is exhausted. This is precisely why B+-trees (unlike plain B-trees, which do not chain their leaves) are the standard database index: the same structure answers both query types efficiently, with range search cost proportional to the number of leaves the range actually spans plus one initial descent.

(b) Does insertion order affect the final B+-tree structure? Yes. Although the final set of keys stored in the leaves is always the same (a B+-tree is a valid search structure for any key set), the exact shape — which keys become internal separators, how deep the tree grows, and how the keys are grouped across leaves — depends on the sequence in which splits occur, and splits are triggered purely by insertion order. Question 1(c) inserted {18, 10, 7, 14, 8, 9, 21} in that specific order and produced a 3-level tree with leaves [7,8] | [9] | [10] | [14] | [18,21]. Inserting the exact same seven keys in sorted order (7, 8, 9, 10, 14, 18, 21) instead produces a different shape — the same 3-level height, but with leaves [7,8] | [9,10] | [14,18] | [21] — four leaves grouped differently, and different keys promoted as separators — because the overflow points fall at different moments. Both trees are equally valid (correct, balanced, and searchable), which is the point: B+-tree shape is a function of insertion history, not just of the final key set.

(c) Fill, insert, and delete on a partially specified B+-tree.

Given. Root (1 of 2 cells filled) → two internal nodes (each 1 of 2 cells filled) → four leaves [abc] | [acc] | [bb,bcd] | [bce,bxy], linked left to right, as shown (internal separators blank as given):

Find. (i) the missing separator keys; (ii) the tree after inserting "bbb"; (iii) the tree after then deleting "abc".

Approach. Every B+-tree internal separator equals the smallest key in the subtree immediately to its right (the standard "copy-up" invariant) — that alone determines the fill-in with no new keys added. Insertion and deletion then follow the same split/borrow/merge rules used throughout this subject.

1. (i) Fill in the separators. Root's separator = smallest key under its right child = "bb" (first key of the [bb,bcd] leaf). Left internal node's separator = smallest key under its right child = "acc". Right internal node's separator = smallest key under its right child = "bce".
2. (ii) Insert "bbb". Compare "bbb" against the root key "bb": since "bb" is a prefix of "bbb", "bb" < "bbb" lexicographically, so the search goes right. At the right internal node, "bbb" < "bce" (2nd character 'b' < 'c'), so it descends left, into leaf [bb, bcd]. Inserting gives [bb, bbb, bcd] — 3 keys, overflow. Split into [bb, bbb] and [bcd]; copy up "bcd". The right internal node, which had only 1 of 2 slots used, absorbs it directly as [bcd, bce] with NO further split. The root is unaffected (its separator "bb" still correctly routes into the same right subtree).
3. (iii) Delete "abc" from the result of (ii). "abc" is the sole key of the leftmost leaf; removing it leaves that leaf empty (underflow, minimum 1 key required). Its only sibling, leaf [acc], is also already at the minimum (1 key), so nothing can be borrowed — the two leaves merge into a single leaf [acc], and the left internal node's separator "acc" is removed with it. The left internal node now holds 0 keys with a single child — itself underflowing. Its sibling, the right internal node [bcd, bce], has 2 keys (above its minimum of 1), so it CAN lend: the standard through-the-parent rotation moves the old root separator "bb" down into the left internal node, and the right internal node's smallest key "bcd" moves up to become the new root separator, carrying its leftmost pointer (leaf [bb,bbb]) across to the left internal node. Final shape: root [bcd] → left internal [bb] → leaves [acc] | [bb,bbb]; right internal [bce] → leaves [bcd] | [bce,bxy].