On Fri, Dec 17, 2004 at 15:36:58 -0500,
Greg Stark <gsstark@mit.edu> wrote:
>
> Isn't that still nlog(n)? In the end you're going to have read in every page
> of the index including all those non-leaf pages. Aren't there nlog(n) pages?
The depth of the tree is log N, but there are only N nodes. I think you
can treat the amount of information at each node as constant.