3. B-Trees.

B-tree is a structured tree whose nodes except for the root contain at least q, and at most 2q keys. The root must contain at least 1 key, and at most 2q. This provides high branching of the B-tree internal nodes for fast searching.

A utilization d(T) of a B-tree T composed of n nodes is defined to be the ratio of the total number |T| of keys in the tree to the maximal possible number 2qn of keys in an n-node B-tree. Since the minimal number of keys is qn, and the maximal is 2qn the utilization is bounded by

The 1/2 lower bound seems to be fine, but in practice the things look different. Indeed, in an implementation of a B-tree it is natural to use a fixed size blocks to store the tree nodes – one block per node. According to the definition of the B-tree each block must fit 2q keys. Suppose that the key set K consists of keys of different lengths, and that the maximal length is l. Then the block size should be at least 2ql. This means that if node stores keys of size l/10, then it is only 1/10 full even if the number of keys is maximal. Therefore, actually we cannot guarantee any lower bound for the utilization of the tree when lengths of keys are taken into account.