Recitation #2

**** NOTE THAT THIS IS NOT YET COMPLETE! MORE PROBLEMS WILL BE ADDED. ****

1.

It is supposed that through time, 107 billion individual human beingshave lived. Let us assume that each of these people have an 8 byte id,a 3 byte encoding of their date of birth, a 3 byte encoding of theirdate of death, an 8 byte foreign key to their mother and an 8 byteforeign key to their father. Then we have 10 bytes to encode thecharacteristics of the persons life (their outlook, tastes, cause ofdeath, basic life trajectory, etc.). Assume that disk blocks are 8Kand with 64-bit addresses. Further assume that B+tree pointers are64-bits and main memory pages/blocks are also 8K.

a. For person data, what is the blocking factor for a B+ tree leafnode with forward and backward pointer to sequential blocks.

b. How many disk blocks do we need to represent every person who everlived?

c. What is the order of an internal B+tree node?

d. Assuming that we cluster on person ids with completely filled leafblocks. What is the maximum height B+tree for an index built over idas the search key.

e.. For d. above, what is the minimum height tree?