Final answer:
The worst-case height h of a B-tree with degree d and n keys is bounded by the inequality (h <= log_d(n)). This comes from considering that in the worst case, a B-tree of height h has at least dh-1 keys, which leads to solving for h by taking the logarithm base d of n.
Step-by-step explanation:
We want to find an upper bound on the height (h) of a B-tree of degree (d) with a total of (n) keys. The worst-case time complexity for both search and insertion operations in a B-tree is proportional to the height of the tree. To find the upper bound on the height, we use properties of B-trees:
In a B-tree of degree d, each non-root node can have at least d-1 and at most 2d-1 keys. The root node can have a minimum of 1 key and similarly a maximum of 2d-1 keys. Each node can have a number of children that is one more than the number of keys, so for a non-root node, it can have at least d and at most 2d children.
To maximize the height of the tree, we need to minimize the number of keys per node, which will require the maximum number of levels to store all n keys. Since each node has at least d children (except for the root which has at least 2 if not empty), in the worst-case scenario, a B-tree of height h has at least dh-1 keys.
Therefore, we need to solve the inequality dh-1 <= n to find the upper bound for h. We can solve this by taking the logarithm of both sides, which gives us:
- log_d(dh-1) <= log_d(n)
- h - 1 <= log_d(n)
- h <= log_d(n) + 1
As the height h must be an integer, and considering the tree's height can only increase by full levels, we can drop the '+1' providing a more general and non-strict inequality:
h <= log_d(n)
The correct inequality that shows an upper bound on the height of a B-tree in terms of degree d and number of keys n is (h <= log_d(n)), which corresponds to option b.