Question 1 of 8

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

(a) RAID 0 vs. RAID 1. RAID 0 is pure striping: consecutive blocks of data are spread round-robin across all N disks in the array with no redundant information stored anywhere. It delivers the full aggregate capacity (N × one disk) and the best possible throughput (reads/writes parallelize across all N disks), but it offers zero fault tolerance — the failure of any single disk destroys data belonging to every file, since each file's blocks are scattered across the whole array. RAID 1 is pure mirroring: every block is written identically to two (or more) disks, so usable capacity is only that of one disk per mirrored pair, but a single disk failure loses nothing — the surviving mirror still holds every block. Mirroring also lets read requests be split across both copies for a read-throughput gain, though every write must still be duplicated. In short: RAID 0 trades all redundancy for capacity and speed; RAID 1 trades capacity for redundancy.

(b) RAID 5 vs. RAID 3. Both stripe data and compute a parity block (the XOR of the corresponding blocks on every other disk) so that any one disk's failure can be reconstructed from the rest. They differ in where parity lives and at what granularity data is striped. RAID 3 stripes at the byte (or bit) level and keeps a single, dedicated parity disk: because a byte-level stripe unit is smaller than almost any real request, every I/O — even one reading a single small record — must touch all the data disks simultaneously to reassemble it, and every write must also touch the one parity disk, which becomes a serialization bottleneck under concurrent small writes. RAID 5 stripes at the block level and rotates the parity block across all disks in the array (no disk is "the" parity disk). Because a typical small request now falls entirely within one disk's stripe unit, independent I/O requests to different blocks can be serviced by different disks in parallel, and because parity duty rotates, concurrent writes to different stripes no longer all pile onto one physical disk. RAID 5 is therefore the far better choice for OLTP-style workloads with many small, independent requests, while RAID 3's per-request full-array access pattern only pays off for large sequential transfers.

(c) Rationale for fillfactor < 1. A fillfactor deliberately leaves each newly built page/node only partially full, trading initial space efficiency for room to absorb future insertions without immediately triggering an expensive reorganization.

• i. Sorted indices. A sorted (sequential) file/index must keep its physical records in key order. If every page were packed 100% full at build time, the very next insertion anywhere except the current end of the file would have no room on its page and would force a cascading shift of every subsequent record (or an overflow-chain page) to preserve sort order. Leaving free slots per page lets a moderate number of new keys be inserted directly into their correct sorted position on the same page, deferring a full reorganization until the free space is actually exhausted.
• ii. B+-tree indices. A B+-tree node split is itself expensive (it allocates a new node, moves half the entries, and may cascade a new key up to the parent, occasionally all the way to a new root). If leaf and internal nodes are built at maximum occupancy, the very first insertion into any node forces a split. A fillfactor of, say, 67–80% leaves headroom in every node so a run of insertions can be absorbed with ordinary key-copies into existing free slots, and splits — along with the I/O and locking they cost — happen far less often as the tree fills back up.
• iii. Hash indices. A hash index maps keys into buckets by their hash value; if every bucket is built exactly full, almost any subsequent insertion whose key hashes into an already-full bucket immediately overflows into an overflow-chain page, and search cost for that bucket degrades from O(1) toward the length of the chain. Leaving spare capacity per bucket (fillfactor < 1) keeps the average chain length near zero for longer as the file grows, preserving the O(1) expected-cost property that is the entire point of hashing.

(d) Equality search vs. range search. An equality search asks for the record(s) whose search-key value equals one specific value (e.g. "find the customer with ID = 4471"); a range search asks for every record whose key falls between two bounds (e.g. "find all orders placed between March 1 and March 31"), potentially returning many records spread across several storage pages. Both begin with the identical descent through an index — comparing the target/lower-bound key against separators to find the right leaf — but an equality search stops as soon as that one leaf has been checked, while a range search must continue scanning forward from that point (via a sorted/clustered file's physical ordering, or a B+-tree's linked leaf level) until the upper bound is passed. This is exactly why data structures that support ordered traversal (sorted files, B+-trees) are preferred over hash indices whenever range queries matter: a hash index scatters keys with no usable order at all, so it can answer (d)'s equality searches in O(1) but cannot answer a range search without a full scan.