You are creating a DBMS capable of handling a terabyte table. This introduces a few challenges. For starters, you want this to run on the FAT-32 (old windows) file system, which has a 4GB file size limit. This means that a single table may have multiple files. Assume 4KB blocks. For an index, this means that your block pointer needs to include both the file name, and the block within the file.

For purposes of this question, assume that Kilo/Giga/Tera refer to powers of 2 (1024/2²⁰/2³⁰), rather than the decimal values.

3. B+-tree

Assume that we use 8 bytes to store each record pointer (this isn't the correct answer to 3.1(2), but is a reasonable approximation.) Our search key is the ID number (10 decimal digits), stored as a 40 bit unsigned integer (yes, I know you can do it in 33 bits, but bit-packing makes things more complicated.)

a. What is the fan-out of our B+-tree? In other words, what is the minimum and maximum number of nodes in the next layer that a B+-tree node points to? Is this number different for leaf nodes? Assume leaf nodes store pointers to the block containing the actual record, not the record itself.

b. Assuming 100 byte person records, and a dense index, what is the maximum number of I/Os required to view a person's record given the ID? How long would you estimate this would take (in milliseconds)?

c. What is the maximum number of disk blocks needed for the B+-tree?

d. Repeat the preceding questions, but assuming a sorted file and a sparse index, with the index only having one pointer to each block.

e. What is the maximum number of I/Os if we were to search for a record using the (unindexed) person's name? How long would you estimate this would take? Assume the database is completely full.

f. Hopefully you've figured out that you want an index on name. Repeat parts a-d, assuming the name is stored as a 32 byte character string.

g. I've had you build a sparse index on both the ID and name. What is wrong with this?