CSE Roadmap

Common tier · about 2 hours · 5 parts

Part 5 of 5 · 4 min read

Exercises

Easy

Easy 1: Name the organization (15 minutes)

State whether a file with no guaranteed row order is a heap file or a sorted file.

Done when: heap file is correctly named.

Hint

A heap file.

Easy 2: Find the trade-off (15 minutes)

State which file organization is faster to insert into, and which is faster for a range query on its sort column.

Done when: heap files are correctly named as faster to insert, and sorted files as faster for range queries on their sort column.

Hint

Heap files insert faster; sorted files answer range queries on their sort column faster.

Easy 3: Predict a scan requirement (15 minutes)

State what finding a specific record in a heap file, with no index, requires.

Done when: scanning the file from the start is correctly described.

Hint

A full scan of the file from the start, checking each record, until the matching one is found.

Medium

Medium 1: Predict the insert cost (25 minutes)

Explain what happens when a new record is inserted into a file sorted by placed_on, if its date falls in the middle of the existing range.

Done when: the explanation correctly describes needing to shift later records to make room in the correct sorted position.

Hint

Records physically after the new record's sorted position need to shift to make room, costing real write work beyond just adding the new record.

Medium 2: Choose the better organization (25 minutes)

A table receives constant inserts and is almost never queried by range. Decide between heap and sorted file organization, and justify the choice.

Done when: heap is correctly chosen, with insert speed cited as the dominant concern given the rare range queries.

Hint

Heap, since insert speed dominates given the described workload, and the rare range queries don't justify the sorted file's constant insert cost.

Medium 3: Why an index avoids the sorted-file cost (25 minutes)

Explain how storing a table as a heap, with a separate index on one column, avoids paying the sorted file's insert cost on every single write to the main table.

Done when: the explanation correctly notes the main table's rows can be inserted anywhere, with only the smaller, separate index structure needing to maintain order.

Hint

The main table's rows can be inserted anywhere, cheaply; only the separate, smaller index structure pays an ordering-maintenance cost on each insert.

Hard

Hard 1: Sorted file versus index, concretely (30 minutes)

Explain the practical difference between physically sorting an entire table by customer_id, versus keeping the table as a heap and building a separate index on customer_id.

Done when: the explanation correctly notes a full sort affects every row's physical location and every insert, while a separate index is a smaller additional structure maintained alongside, without reordering the main table.

Hint

A full table sort reorders every row physically and burdens every insert with maintaining that order; a separate index is a distinct, additional structure that can be updated without moving the main table's rows at all.

Hard 2: A workload that genuinely benefits from a sorted file (35 minutes)

Describe a realistic workload, read-heavy and dominated by range queries on one column, with rare inserts, where paying a sorted file's insert cost is actually a reasonable trade.

Done when: a realistic read-heavy, rarely-inserted, range-query-dominated workload is described, with the trade-off reasoning correctly applied.

Hint

A reporting table, updated rarely but queried constantly for date-range reports, reasonably accepts a sorted file's insert cost in exchange for consistently fast range reads.

Hard 3: Multiple access patterns, one table (40 minutes)

A table needs fast range queries on placed_on and fast single-row lookups by customer_id, with frequent inserts. Explain why neither a heap file alone nor a sorted file alone serves both needs well, and what Level 5 offers instead.

Done when: the explanation correctly identifies that satisfying both patterns well, with frequent inserts, points toward using indexes (potentially more than one) rather than physically sorting the main table by either column alone.

Hint

Neither single organization serves both a range-query column and a separate lookup column well at once; Level 5's indexes let the table stay heap-organized for fast inserts, while separate indexes on both placed_on and customer_id each provide fast access along their own column independently.