Problem

1. If a key in a B-tree is not in a leaf, prove that both its immediate predecessor and immediate successor (under the natural order) are in leaves.

2. Suppose that disk hardware allows us to choose the size of a disk record any way we wish, but that the time it takes to read a record from the disk is a+bd, disk accesses where a and b are constants and d is the order of the B-tree. (One node in the B-tree is stored as one record on the disk.) Let n be the number of entries in the B-tree. Assume for simplicity that all the nodes in the B-tree are full (each node contains d - 1 entries).

(a) Explain why the time needed to do a typical B-tree operation (searching or insertion, for example) is approximately (a + bd)logd n.

(b) Show that the time needed is minimized when the value of d satisfies d(ln d-1)= a/b. (Note that the answer does not depend on the number n of entries in the B-tree.)

(c) Suppose a is 20 milliseconds and b is 0.1 millisecond. (The records are very short.) Find the value of d (approximately) that minimizes the time.

(d) Suppose a is 20 milliseconds and b is 10 milliseconds. (The records are longer.) Find the value of d (approximately) that minimizes the time.