Question 2 of 8

Question 2 (3+3+14=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 21"): 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 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, 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 on the final key set. Question 1(c) inserted 18, 10, 7, 14, 8, 9, 21 in that (non-sorted) order and obtained root [14] over internal nodes [9, 10] and [18], with five leaves [7,8] ↔ [9] ↔ [10] ↔ [14] ↔ [18,21]. Inserting the SAME seven keys in ascending order (7, 8, 9, 10, 14, 18, 21) first overflows on the third key ([7,8,9] splits to [7,8] / [9]) and, after two more leaf splits and one root split, ends with root [14] over internal nodes [9] and [21] and only four leaves: [7,8] ↔ [9,10] ↔ [14,18] ↔ [21]. Same keys, same sorted leaf sequence, but different separators, a different number of leaves and different leaf occupancy. The one thing insertion order can never change is the sorted left-to-right order of the keys across the leaf chain, because that is the B+-tree's defining invariant; what varies is which keys are promoted as separators, how many nodes result, how full each one is and, for longer sequences, how many levels the tree reaches.

Part (c) — inserting alice, betty, carol, debbie, edith, zelda.

Given. An order-3 B+-tree (at most 2 keys and 3 children per node) on name keys, read from the figure: root [rick] → internal nodes [judy] and [tom]; [judy] → [bob | jane] and [mike | pete]; [tom] → [sol] and [vince]; ten leaves in sorted order: [abe,al] ↔ [bob,edie] ↔ [jane,joe] ↔ [judy,karen] ↔ [mike,nan] ↔ [pete,phil] ↔ [rick,rob] ↔ [sol] ↔ [tom,vera] ↔ [vince].

Find. The final tree after inserting alice, betty, carol, debbie, edith and zelda, one after another.

Approach. Route each key from the root using the separators (a key equal to a separator goes right), insert it into its leaf, and split upward as far as the overflow cascades. Five of the six keys fall between "al" and "jane", so they all land in the crowded left end of the [bob | jane] node and force repeated splits there; zelda goes to the far right.

1. Insert alice. alice < rick → [judy]; alice < judy → [bob | jane]; alice < bob → leaf [abe,al] (al sorts before alice because it is a prefix of it). The leaf becomes [abe,al,alice] and overflows: split into [abe,al] | [alice] and copy "alice" up. The parent would hold {alice, bob, jane} with four children and overflows too: it splits into [alice] (children [abe,al], [alice]) and [jane] (children [bob,edie], [jane,joe]), and the middle key "bob" moves up. [judy] absorbs it and becomes [bob | judy] with three children. No further split.
2. Insert betty. betty < rick; in [bob | judy], betty < bob → [alice]; betty ≥ alice → leaf [alice]. It becomes [alice,betty]. Fits.
3. Insert carol. carol < rick; in [bob | judy], bob ≤ carol < judy → [jane]; carol < jane → leaf [bob,edie]. It becomes [bob,carol,edie] and overflows: split into [bob,carol] | [edie] and copy "edie" up. The parent becomes [edie | jane] with children [bob,carol], [edie], [jane,joe]. Fits.
4. Insert debbie. debbie < rick; bob ≤ debbie < judy → [edie | jane]; debbie < edie → leaf [bob,carol]. It becomes [bob,carol,debbie] and overflows: split into [bob,carol] | [debbie], copy "debbie" up. The parent would hold {debbie, edie, jane} and overflows: it splits into [debbie] (children [bob,carol], [debbie]) and [jane] (children [edie], [jane,joe]), moving "edie" up. The grandparent would hold {bob, edie, judy} and overflows as well: it splits into [bob] (children [alice], [debbie]) and [judy] (children [jane], [mike | pete]), moving "edie" up again. The root [rick] absorbs it and becomes [edie | rick] with three children. The cascade reaches the root but stops there, so the height stays at 4 levels.
5. Insert edith. edie ≤ edith < rick → [judy]; edith < judy → [jane]; edith < jane → leaf [edie] (edie < edith, since "e" < "t" at the fourth letter). It becomes [edie,edith]. Fits.
6. Insert zelda. zelda ≥ rick → [tom]; zelda ≥ tom → [vince]; zelda ≥ vince → leaf [vince]. It becomes [vince,zelda]. Fits. The rest of the right-hand (tom) subtree is untouched.