B+ and Hashtable Homework Solution#
Question 1#
Question 2#
(a)
(b)
(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)
(b)
Question 4#
