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.

(a) Why a file can have only one clustered index. A clustered index is one whose key order determines the physical storage order of the underlying data records — the data file itself is sorted (or grouped into buckets) according to the index key, and the index's leaf level effectively is the data, or points directly at data pages that are kept in that order. Physical storage is a single, one-dimensional arrangement: the records of a file can be laid out on disk in exactly one physical sequence at any given time. Because a clustering index's entire benefit — fast range scans and sequential I/O with no extra fetches — comes from that physical ordering matching the search key, a second clustering index would require the SAME set of data records to be physically sorted in a second, generally different, order simultaneously, which is impossible without duplicating the entire file. A file can carry many unclustered (secondary) indexes, each with its own independent key order, because those indexes are separate structures that merely point at records wherever they physically live; only the one arrangement that the data pages are actually sorted by can be a clustered index.

(b) Why a secondary, unclustered index must be dense. A dense index has one index entry for every search-key value that appears in the data file; a sparse index has only one entry per data page (pointing to the first record of that page) and relies on the fact that all remaining records with nearby key values are physically adjacent on that same page, so a scan forward from the pointer finds them. That reliance is exactly what an unclustered index cannot offer: because the data is NOT sorted by the unclustered index's key, records with the same or nearby key values for that index are scattered across arbitrary, unrelated data pages. If the index held only one entry per page, a lookup for a given key would have no way to locate the specific record(s) with that key among the page's unrelated contents — there is no "keep scanning nearby records" fallback, because "nearby" in this key order does not correspond to "nearby" on disk. A sparse index is therefore only safe when the file is clustered on that same key; every unclustered (secondary) index must be dense so that each and every qualifying record has its own directly-addressable index entry.

(c) B+-tree growth for 18, 10, 7, 14, 8, 9, 21.

Given. An order-3 B+-tree (at most 2 keys / 3 children per node, minimum 1 key per node except a root that is itself a leaf); insert 18, 10, 7, 14, 8, 9, 21 one at a time, starting empty.

Find. The tree's shape after each of the 7 insertions.

Approach. Insert into the correct leaf; when a leaf would exceed 2 keys, split it in half and copy the right half's smallest key up to the parent (leaves keep all data keys); when an internal node would exceed 2 keys, split it and move (not copy) its median key up, growing the tree upward when the root itself splits.

1. Insert 18. The tree is a single empty leaf; 18 is added directly.
2. Insert 10. 10 < 18, so it is added to the same leaf in sorted order: [10, 18]. Still within the 2-key capacity, no split.
3. Insert 7. The leaf would become [7, 10, 18] — 3 keys, overflow. Split into [7, 10] and [18]; copy up 18 as the new root separator.
4. Insert 14. 14 < 18 routes to the left leaf [7, 10], giving [7, 10, 14] — overflow again. Split into [7, 10] and [14]; copy up 14. The root now holds [14, 18] with three leaf children — still within capacity, no further split.
5. Insert 8. 8 < 14 routes to leaf [7, 10], giving [7, 8, 10] — overflow. Split into [7, 8] and [10]; copy up 10. The root would become [10, 14, 18] — 3 keys, overflow. Split the root: the median key 14 moves up (not copied) to a brand-new root; the left half keeps [10] with children ([7,8],[10]), the right half keeps [18] with children ([14],[18]). The tree gains a third level (root, internal, leaf).
6. Insert 9. 9 < 14 → 9 < 10 routes to leaf [7, 8], giving [7, 8, 9] — overflow. Split into [7, 8] and [9]; copy up 9. The left internal node [10] becomes [9, 10] — exactly 2 keys, no split needed.
7. Insert 21. 21 ≥ 14 → 21 ≥ 18 routes to leaf [18], giving [18, 21] — fits within capacity, no split anywhere. This is the final tree.