Worst-Case Optimal Tree Layout in External Memory

Consider laying out a fixed‐topology binary 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 $\begin{array}{r}\{\begin{array}{ll}\mathrm{\Theta <!--\; T\; -->}(\frac{D}{\lg <!--\; ?\; -->(1+B)})& whenD=O(\lg <!--\; ?\; -->N),\\ \mathrm{\Theta <!--\; T\; -->}(\frac{\lg <!--\; ?\; -->N}{\lg <!--\; ?\; -->(1+\frac{B\lg <!--\; ?\; -->N}{D})})& whenD=\mathrm{\Omega <!--\; O\; -->}(\lg <!--\; ?\; -->N)andD=O(B\lg <!--\; ?\; -->N),\\ \mathrm{\Theta <!--\; T\; -->}(\frac{D}{B})& whenD=\mathrm{\Omega <!--\; O\; -->}(B\lg <!--\; ?\; -->N).\end{array}\end{array}$