. Let T be a B-tree with minimum degree t = 8. If T stores one billion (that is,

ID: 3527404 • Letter: #

Question

. Let T be a B-tree with minimum degree t = 8. If T stores one billion (that is, 10

9 ? 2

) keys, what are the

possible heights of T ? (8)

(Hint: Derive lower and upper bounds on the height h of T in terms of the number n of keys stored in T. Recall that in a non-empty

B-tree with minimum degree t, the root contains at least two and at most 2t children, and a non-leaf non-root node contains at least

t and at most 2t children. The number of keys in a node is one less than the number of its children

For a given height h of T, the number n of keys in T is smallest when the root has exactly two children (one

key), every non-root non-leaf node has exactly t children (t - 1 keys), and each leaf node stores exactly t - 1

keys. We, therefore, have

n > 1 + 2(t - 1) + 2t(t - 1) + 2t2(t - 1) +

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.