The number of disk pages access in B-tree search, where h is height, n is the…
2015
The number of disk pages access in B-tree search, where h is height, n is the number of keys and t is the minimum degree, is
- A.
\(\theta (\log_n h*t)\) - B.
\(\theta (\log_t n*h)\) - C.
\(\theta (\log_h n)\) - D.
\(\theta (\log_t n)\)
Attempted by 116 students.
Show answer & explanation
Correct answer: D
Answer: θ(log_t n)
Reasoning:
Branching factor: In a B-tree of minimum degree t, every internal node (except possibly the root) has at least t children, so the number of nodes grows by a factor of at least t per level.
Height relation: Because the tree expands by roughly a factor of t each level, the total number of keys n is Θ(t^h). Solving for h gives h = Θ(log_t n).
Disk accesses: A search inspects one node per level (one disk page access per level), so the number of disk page accesses is Θ(h) = Θ(log_t n).
Notes: The root may have fewer children but this affects only constant additive factors; the asymptotic cost remains Θ(log_t n).