Question 1 of 8

Question 1 (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.

Given. An order-3 B+-tree (at most 2 keys per node, so at most 3 child pointers), initially empty. The 7 keys Edith, Carol, Betty, Debbie, Alice, Zelda, Wilma are inserted one at a time, in that order, and are compared alphabetically (all 7 first letters are distinct, so alphabetical order on the whole name and on the first letter agree).

Find. (a) equality vs. range search; (b) whether insertion order affects the final tree shape; (c) the tree after EACH of the 7 insertions.

Part (a) — equality search vs. range search. An equality search looks up ONE specific key value (e.g. "find the record for Debbie"): the search descends the tree once, comparing the target key against each node's separators to pick a single child at every level, until it reaches the one leaf that can hold that key — cost is a single root-to-leaf path, O(log N). A range search asks for every record whose key falls between two bounds (e.g. "every name from Carol to Edith inclusive"): it descends once to find the leaf holding the LOWER bound, exactly like an equality search, but then walks SIDEWAYS along the leaf-level sibling-pointer chain — visible as the double-headed arrows between leaves in every diagram below — reading entries in sorted order until a key exceeds the upper bound, with no further root-to-leaf descents needed. This sideways chain is exactly why a B+-tree (unlike a plain B-tree, which also stores data in internal nodes) keeps every data key in the leaves, linked in order: it turns a range query into one descent plus a linear scan, instead of repeated whole-tree lookups.

Part (b) — does insertion order change the final tree? Yes. A B+-tree's shape is a side effect of exactly when each leaf happens to overflow and split, and that timing depends on which keys have already accumulated in a leaf at the moment a new key arrives — which is a property of the ARRIVAL order, not just of the final key set. Part (c) below builds one tree by inserting Edith, Carol, Betty, Debbie, Alice, Zelda, Wilma in exactly that order; inserting the same 7 names in a different order (say, alphabetically: Alice, Betty, Carol, Debbie, Edith, Wilma, Zelda) would trigger splits at different points and can leave keys grouped into different leaves and a different-shaped internal structure, even though both trees necessarily index the same 7 names in the same sorted leaf-chain order — the one invariant insertion order can never change, since every B+-tree keeps its leaves in sorted order regardless of how they filled up.

Part (c) — approach. Standard B+-tree insertion (Ramakrishnan & Gehrke / Silberschatz algorithm, order 3: at most 2 keys/leaf, at most 2 keys & 3 pointers/internal node): descend to the correct leaf and insert the key in sorted position; if the leaf now holds 3 keys it OVERFLOWS and SPLITS into a 2-key left leaf and a 1-key right leaf, and the smallest key of the new right leaf is COPIED up into the parent (data always stays in the leaves); if an internal node is pushed to 3 keys it splits too, but its middle key MOVES up (it is not duplicated, since internal keys are pure routing separators, not data). Traced below and cross-checked against a Python implementation of this exact algorithm.

1. Insert Edith. Tree is empty — Edith becomes the sole entry of the one root leaf. No overflow (1 key, capacity 2).
After inserting Edith
2. Insert Carol. Carol < Edith, so it takes the left slot: leaf = [Carol, Edith]. 2 keys, exactly at capacity but not overflowing.
After inserting Carol
3. Insert Betty. Betty < Carol < Edith would give [Betty, Carol, Edith] — 3 keys, OVERFLOW. Split into left=[Betty, Carol] (2 keys) and right=[Edith] (1 key); copy up the smallest key of the right leaf, "Edith", as the new root's separator.
After inserting Betty — first split, tree gains a level
4. Insert Debbie. Debbie < Edith routes LEFT of the root separator, into the single leaf [Betty, Carol]; Debbie sorts after both, giving [Betty, Carol, Debbie] — OVERFLOW. Split into [Betty, Carol] and [Debbie]; copy up "Debbie". Root becomes [Debbie, Edith] with 3 leaf children.
After inserting Debbie
5. Insert Alice. Alice < Betty routes to the leftmost leaf [Betty, Carol], giving [Alice, Betty, Carol] — OVERFLOW. Split into [Alice, Betty] and [Carol]; copy up "Carol" into the root. The root now holds [Carol, Debbie, Edith] — 3 keys, itself OVERFLOWING (root capacity is 2 keys). The root splits: middle key "Debbie" MOVES up (not copied) into a brand-new root; left half keeps key [Carol] with the first 2 children, right half keeps key [Edith] with the last 2 children. The tree gains a level.
After inserting Alice — root splits, tree grows to 3 levels
6. Insert Zelda. Zelda ≥ Debbie routes right, then Zelda ≥ Edith routes to the rightmost leaf [Edith], giving [Edith, Zelda] — 2 keys, within capacity, no split.
After inserting Zelda
7. Insert Wilma. Wilma ≥ Debbie routes right; Wilma < Zelda but Wilma ≥ Edith routes to the [Edith, Zelda] leaf, giving [Edith, Wilma, Zelda] — OVERFLOW. Split into [Edith, Wilma] and [Zelda]; copy up "Zelda". The right internal node [Edith] gains a key and child, becoming [Edith, Zelda] with 3 children — within the order-3 capacity (2 keys), so no further propagation. Root stays [Debbie].
After inserting Wilma — final tree