Consider a B-tree of height h. minimum degree \(𝑡≥2\) that contains any…
2022
Consider a B-tree of height h. minimum degree \(𝑡≥2\) that contains any \(n\)-key, where \(𝑛≥1\). Which of the following is correct ?
- A.
\(h \geq \log _{t} \frac{n+1}{2}\) - B.
\(h \leq \log _{t} \frac{n+1}{2}\) - C.
\(h \geq \log _{t} \frac{n-1}{2}\) - D.
\(h \leq \log _{t} \frac{n-1}{2}\)
Attempted by 128 students.
Show answer & explanation
Correct answer: B
Key result: the minimal number of keys n in a B-tree of height h with minimum degree t satisfies n >= 2*t^h - 1, which leads to h <= log_t((n+1)/2).
Minimum per-node keys: every non-root node has at least t-1 keys; the root has at least 1 key.
Count nodes level by level: if h > 0, the root has at least 2 children, and each subsequent level multiplies the minimum number of children by at least t. So the number of nodes at level i (1 ≤ i ≤ h) is at least 2 * t^{i-1}.
Lower bound on keys: every non-root node contributes at least t-1 keys, so
n >= 1 + (t-1) * sum_{i=1..h} 2 * t^{i-1} = 1 + 2(t-1) * (t^{h}-1)/(t-1) = 2 * t^{h} - 1.
Solve for h: n >= 2 * t^{h} - 1 => n + 1 >= 2 * t^{h} => t^{h} <= (n+1)/2 => h <= log_t((n+1)/2).
Conclusion: The correct relation between height h, number of keys n, and minimum degree t is h <= log_t((n+1)/2).
A video solution is available for this question — log in and enroll to watch it.