Questions: Physical Storage: Pages, Records, and Heap Files

Question 1

A table has 500,000 rows, each 200 bytes. Pages are 8KB. A query needs exactly one row. How many pages must the database read in the worst case (assuming a heap file with no index)?

• A. 1 page — the database reads only the page containing the needed row
• B. 500 pages — one page per thousand rows
• C. Approximately 12,500 pages — the entire heap file must be scanned
• D. 200 pages — one page per byte in the row

Answer: (C)

A heap file stores records in no particular order, so without an index the database has no way to know which page holds the target row — it must read every page until it finds the row (or confirms it is absent). Pages hold 8192 / 200 ≈ 40 rows each, so 500,000 rows ÷ 40 rows/page = 12,500 pages. Even for a single-row query, the database may read all 12,500 pages. This is the cost that indexes are designed to eliminate — but understanding the baseline page-scan cost explains why indexes matter.

Question 2

When a record is moved within a page during compaction, the database must update every external reference (such as index entries) pointing to that record's location.

• A. True — every reference stores the physical byte offset, so any move requires updating all references
• B. False — the slot array provides indirection so only the slot pointer needs updating, not external references
• C. True — slot arrays only help within a page, not for cross-page references
• D. False — records can never be moved once written; compaction is not possible

Answer: (B)

The slot array is specifically designed to handle this. External references (such as index entries) point to a record ID that includes the page number and slot number — not the raw byte offset within the page. When a record moves during compaction, only its slot entry (byte offset within the page) is updated. All external references continue to point to the same slot, which now reflects the new position. This indirection is the reason slot arrays exist: they decouple external references from the physical layout within a page.

Question 3

The database reads a minimum of one full page from disk even if the query only needs a single column from a single row.

• T. True
• F. False

Answer: True

The page is the atomic unit of disk I/O — disks are optimized for reading fixed-size sequential blocks, not random byte access. When the database needs any data from a page, the entire page is transferred into the buffer pool. There is no mechanism to read 'just the column you need' from disk at a sub-page granularity. This is why column-oriented storage (a more advanced topic) offers I/O advantages for analytical queries that read few columns from many rows — it physically groups column data so that reading a column requires fewer pages.

Question 4

Variable-length columns (VARCHAR, TEXT) are stored at the beginning of a record so the database can quickly locate them.

• T. True
• F. False

Answer: False

It is the opposite: fixed-length columns are stored first (in a fixed-length portion), precisely because their byte offsets are arithmetically predictable — to reach the 3rd fixed-length column, you add up the sizes of the first two. Variable-length columns follow in a separate portion, with offset pointers indicating where each one starts and ends. This layout lets the database jump directly to any fixed column without parsing variable-length data, which would require scanning from the beginning of the record each time.

Question 5

Why is the page the fundamental unit of disk I/O in a database system, and what consequence does this have for query performance?

Model answer: Disk hardware is designed for sequential block access, not random byte access. Reading a single byte requires the same mechanical seek and rotational latency as reading a full 4KB or 8KB block, so the database always reads in page-sized units to amortize that fixed cost. The consequence is that I/O cost is measured in pages, not rows. A query that touches one row on each of 10,000 pages costs as much as reading 10,000 complete pages, even if only tiny fractions of those pages are needed. This makes the number of pages accessed — not the number of rows — the primary predictor of query cost, and it explains why index structures (which reduce page accesses) and physical data layout (which clusters related rows on the same page) are the main levers of database performance optimization.

Understanding page-level I/O is the foundation for reasoning about any database optimization. When evaluating whether an index helps, you ask: does it reduce the number of pages read? When evaluating whether to cluster a table by a key, you ask: does it ensure that rows likely to be queried together live on the same pages? Every higher-level optimization technique (indexes, buffer pools, partitioning) ultimately works by reducing page-level I/O.