Question 2 of 8

Question 2 (4+4+(6+6)=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.

Part (a) — equality search vs. range search. An equality search asks for the record(s) matching one specific key value (e.g. "find the record with key = 18"): the tree is descended once, comparing the search key against each node's separators to choose a single child at every level, until a leaf is reached and its (one or few, if duplicates exist) matching entries are read directly — cost is O(log₀ N) node reads and no more. A range search asks for every record whose key falls between two bounds (e.g. "find all keys between 10 and 28"): the tree is descended once to locate the leaf holding the lower bound, exactly as for an equality search, but from there the search does not re-descend from the root for each additional match — it walks sideways along the leaf level using the leaf-to-leaf sibling pointers (the horizontal chain shown in every diagram in this paper), reading entries in sorted key order until a leaf value exceeds the upper bound. This sideways chain is precisely why B+-trees keep all data in the leaves linked in sorted order, unlike a plain B-tree that also stores data in internal nodes: a plain B-tree's range scan would have to interleave in-order tree traversal with data reads, which is markedly less efficient for sequential/range access than following one linked list.

Part (b) — does insertion order change the final tree? Yes. A B+-tree's shape is a byproduct of exactly when each split happens, and a split's timing depends on which keys have already accumulated in the leaf being inserted into — which in turn depends on the arrival order, not merely the final key set. Two databases holding the identical 11 keys of Question 1 could therefore end up with structurally different trees: Question 1 built its tree by inserting 2, 5, 8, ..., 33 in ascending order and obtained the 2-level tree with root [15] shown above (5 leaves, one 3-key leaf). Inserting the SAME 11 keys in a different order — say, largest-first (33, 31, 28, ..., 2) — produces a different sequence of overflowing leaves and a different final grouping of keys into leaves: with the same order-4 rules, descending insertion ends with leaves [2,5,8] | [10,15] | [18,23] | [25,28] | [31,33], versus [2,5] | [8,10] | [15,18] | [23,25] | [28,31,33] for ascending insertion (though it must still end up with the same total key count and the same in-order leaf traversal, since both trees index the same 11 keys). A bulk-load routine that instead sorts the keys once and packs leaves at maximum fill (rather than inserting one at a time) commonly produces a shorter, more compact tree than either incremental order, because it never wastes half-empty leaves created mid-sequence by a split. The one thing insertion order can never change is the sorted left-to-right order of keys along the leaf chain, since a B+-tree's defining invariant is that the leaves always hold every key in sorted order regardless of how they arrived.

Part (c)(i) — given. An order-3 B+-tree (2 keys/3 pointers per node) with its leaf level fully specified: [abc] ↔ [acc] ↔ [bb,bcd] ↔ [bce,bxy], grouped under two internal nodes whose own key cells are blank, under a root whose key cell is also blank.

Find. The correct separator key for each blank internal-node cell, using only keys already present in the leaves (no new keys may be introduced).

Approach. In a B+-tree, every internal separator is simply a copy of the smallest key that appears anywhere in its right subtree — so each blank cell is filled by reading off the first key of the leaf (or leftmost leaf, for a multi-level subtree) immediately to its right.

1. Left internal node. Its two children are leaf [abc] and leaf [acc]; the separator between them copies the smallest key of the right child, "acc". Left internal node = [acc].
2. Right internal node. Its two children are leaf [bb,bcd] and leaf [bce,bxy]; the separator copies the smallest key of the right child, "bce". Right internal node = [bce].
3. Root. Its two children are the left and right internal nodes just filled; the separator copies the smallest key anywhere in the right subtree, which is the first key of ITS leftmost leaf, [bb,bcd] → "bb". Root = [bb].

Part (c)(ii) — insert "bbb". Comparing lexicographically, bb < bbb < bcd (bbb shares the prefix "bb" with bb but is longer, and bbb < bcd because the third character b < c), so a search for bbb follows: root "bb" → bbb ≥ bb routes right; right-internal key "bce" → bbb < bce routes left; lands in leaf [bb,bcd]. That leaf is already at its 2-key capacity, so inserting bbb overflows it to [bb,bbb,bcd] (3 keys). Splitting keeps ⌈3/2⌉=2 keys on the left, [bb,bbb], and 1 on the right, [bcd]; the smallest right-hand key, "bcd", is copied up into the parent. The right internal node, previously [bce] with 2 children, now has 3 children and needs 2 keys: [bcd, bce] — exactly the order-3 capacity, so no further (root) split is triggered.