Probably five questions.

1 or 2 exercise

• E.g., What would this linear hash look like after the addition of a record with key 27 is added?

1 or 2 short answer

• E.g., Which of the following indexes would be most appropriate for use with this query? Why?

1 or 2 analysis

• E.g., Consider a buffer pool that accommodates variable size pages... What would be the performance issues?

Basically chapters 8–11, & 13 from the textbook. We have covered the first third of the course, the physical database.

Only topics covered in the reading and in class are fair game.

1. Storage & Indexing (Ch.8 & 9)
   1. disk space manager
   2. cost model: how to count I/O's
   3. buffer pool manager
   4. types of indexes
      1. clustered vs. unclustered
      2. alternatives 1, 2, &3 arrangements
      3. matching to search keys
      4. differences between tree and hash-based indexes for useage
   5. file and page organization
2. Tree Indexes (Ch.10)
   • B+ Trees
     1. mechanics
     2. balance rules
     3. design choices
     4. optimization issues, like prefix key compression
3. Hash-based Indexes (Ch.11)
   1. extendable
   2. linear
4. External Sorting (Ch.13)
   1. What are the issues for sorting externally?
   2. the basic algorithm
   3. variations to improve performance (e.g., tournament sort)
   4. I/O-boundedness & CPU-boundedness

The test will be closed-note, closed-book. You may bring a calculator, but the test will be designed so that any math shouldn't need one.

There will be space on the text packet for writing answers. I will bring extra paper, in case anyone needs it, to attach.

The test will be for the class lecture time, so 75 minutes.