Question :

Suppose we want to build a B+ tree that has space for 200,000 data entries in its leaf pages. Each data entry is made up of a key and its corresponding data value. Let us assume the following specifications.

Each page (leaf or internal) is 4096 bytes long. Each page holds three 8-byte pointers (parent, left sibling, right sibling) in addition to the bytes consumed by all of the keys and their accompanying 8-byte values.

(In the case of leaf pages, these "values" are simply pointers that locate the full data record corresponding to the key (e.g., customer record for the given key.)

We want to use an even number of data entries in the leaf pages. Internally, we also want an even number. The keys have unique values. For all of the following questions, show your work:

a) Suppose each key is 56 bytes long, and suppose we fill the leaf pages to capacity (i.e., as much as possible). Compute the number of leaf pages that we need.

b) Compute the number of internal pages, at each level, that we "need" (i.e., assume that you can fill the parents to capacity (to the maximum even number of keys)). This will result in a structure that has the fewest number of pages. Note, however, that the root can have as few as one key.