Consider laying out a fixed-topology tree of N nodes into external
memory with block size B so as to minimize the worst-case number of
block memory transfers required to traverse a path from the root to a node of
depth D. We prove that the optimal number of memory transfers is
Θ
({
D / lg (1+B)
when D = O(lg N)
)
.
lg N / lg (1 + (B lg N) / D)
when D = Ω(lg N)
and D = O(B lg N)
D / B
when D = Ω(B lg N)
This bound can be achieved even when B is unknown to the
(cache-oblivious) layout algorithm.