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 beings
have 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 their
date of death, an 8 byte foreign key to their mother and an 8 byte
foreign key to their father. Then we have 10 bytes to encode the
characteristics of the persons life (their outlook, tastes, cause of
death, basic life trajectory, etc.). Assume that disk blocks are 8K
and with 64-bit addresses. Further assume that B+tree pointers are
64-bits and main memory pages/blocks are also 8K.

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

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

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

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

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

2. 

brainz.zip