# B+ and Hashtable Homework Solution

## Question 1

![](q1Soln.jpg)

## Question 2

(a)

$$
\begin{align}
8M+8(M-1)\leq& 8192\\
16M \leq& 8200\\
M \leq& 512.5\\
M=&512
\end{align}
$$

(b)

$$
\begin{align}
(8+56)L+8 \leq& 8192\\
64L \leq& 8184\\
L \leq& 127.9\\
L=&127
\end{align}
$$

(c) We can solve this problem one level at a time, or all at once.

*How many key-value pairs could we store with a single hard drive access?* To
do it in one hard drive access, we would access only the leaf, so we can
store at most 127 key-value pairs.

*How many key-value pairs could we store with two hard drive accesses?* To
do it in two hard drive accesses, we would access one internal node, and one
leaf. The internal node has at most 512 children. $512\times 127 = 65,024$
key-value pairs.

*How many key-value pairs could we store with three hard drive accesses?* To
do it in three hard drive accesses, we would access two internal nodes, and one
leaf. The root node as at most 512 children, each of which have at most 512
child leaf nodes. $512\times 512 \times 127 = 512^2 \times 127 = 512^2 \times
127 = 512^2 \times 127 = 512^2 \times 127 = 512^2 \times 127 = 33,292,288$
key-value pairs.

*How many key-value pairs could we store with four hard drive accesses?* To
do it in four hard drive accesses, we would access three internal nodes, and one
leaf. The root node as at most 512 children, each of which have at most 512
child nodes, each of which has at most 512 child leaf nodes. $512^3 \times 127
= 17,045,651,456$ key-value pairs. This number is larger than 1 billion.
**Our tree needs 4 accesses if storing 1 billion key-value pairs.**

To solve this all at once, we first calculate that if each leaf holds up to
127 key-value pairs, we can store 1 billion key-value pairs in
1000000000/127=7,874,016 leaf nodes. $\log_{512}(7874016)= ~2.5$, meaning the
height of the tree must be larger than 2.5. A tree with height 3 requires 4
node accesses to reach a leaf.

## Question 3

(a)

![](q3aSoln.jpg)

(b)

![](q3bSoln.jpg)

## Question 4

![](q4Soln.jpg)