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) — why only one clustered index per file. A clustered index is one whose search key order matches the PHYSICAL storage order of the underlying data records — the records themselves are sorted on disk (or grouped into pages) according to that key. A file's records can only be laid out on disk in ONE physical order at a time, so at most one index can have this "index order = storage order" property; every other index on the same file must be unclustered (its key order necessarily disagrees with the one physical order actually used). Trying to cluster on two different keys simultaneously would require the data to be physically sorted two different ways at once, which is impossible for a single copy of the file.

Part (b) — why a secondary (unclustered) index must be dense. A sparse index stores only one entry per DATA PAGE (not per record), which only works if the index key's order matches the physical page order — the index can point at a page and rely on the target record being found by scanning nearby records that are known to be adjacent to it. A secondary index's key is, by definition, NOT the clustering key, so records with nearby secondary-key values are scattered across unrelated, non-adjacent data pages. A sparse secondary entry pointing at "roughly the right page" would give no way to locate the actual matching record(s) among all the OTHER pages holding the rest of that key range. A secondary index must therefore be dense: it needs one entry per distinct search-key value (pointing directly at every matching record, or record group), because there is no physical adjacency left to exploit.

Given (c). An order-3 B+-tree (2 keys/3 pointers per node) already containing the 6 leaf-level keys 1, 10, 15, 17, 19, 20 under root [16] → [8], [19] → leaves [1], [10,15], [17], [19,20].

Find. The tree after inserting 3, 5, 11, 16, 18, 21 one at a time, in that order.

Approach. Same order-3 insertion algorithm as Question 1(c): descend to the target leaf, insert in sorted position, split-and-copy-up a 3-key leaf, split-and-move-up a 3-key internal node. every intermediate leaf state is nonetheless listed in the results table).

1. Insert 3. 3 < 8 routes to leaf [1]; becomes [1,3] (2 keys, no split).
2. Insert 5. 5 < 8 routes to [1,3]; becomes [1,3,5] — OVERFLOW. Split into [1,3] and [5]; copy up "5". Internal node [8] becomes [5,8] (3 children: [1,3],[5],[10,15]).
3. Insert 11. 11 < 16 routes into the left subtree; 11 ≥ 8 routes to leaf [10,15]; becomes [10,11,15] — OVERFLOW. Split into [10,11] and [15]; copy up "15". The left internal node [5,8] gains a key/child, becoming [5,8,15] — itself OVERFLOWING (3 keys). Splits: middle key "8" MOVES up; left=[5]→{[1,3],[5]}, right=[15]→{[10,11],[15]}. Root gains a level: [8,16] with 3 children (int[5], int[15], int[19]).
4. Insert 16. 16 ≥ 16, so it takes the right side of the root (the ≥16 subtree), landing under int[19]; 16 < 19 routes to leaf [17]; becomes [16,17] (2 keys, no split).
5. Insert 18. Routes under int[19], which currently holds just one key (19) over 2 children ([16,17], [19,20]); 18 < 19 routes to the LEFT child [16,17], giving [16,17,18] — OVERFLOW. Split into [16,17] and [18]; copy up "18". Internal node [19] becomes [18,19] (3 children: [16,17],[18],[19,20]).
6. Insert 21. Routes under int[18,19]; 21 ≥ 19 routes to the rightmost leaf [19,20], giving [19,20,21] — OVERFLOW. Split into [19,20] and [21]; copy up "21". Internal node [18,19] gains a key/child, becoming [18,19,21] — itself OVERFLOWING. Splits: middle key "19" MOVES up; left=[18]→{[16,17],[18]}, right=[21]→{[19,20],[21]}. This pushes the ROOT [8,16] to gain a key too — it becomes [8,16,19], OVERFLOWING again. Root splits: middle key "16" MOVES up into a brand-new root; left=[8]→{int[5],int[15]}, right=[19]→{int[18],int[21]}. The tree gains a level, now 4 levels deep (root → 2 internal levels → leaves).