On Fri, Dec 17, 2004 at 15:12:18 -0600,
Bruno Wolff III <bruno(at)wolff(dot)to> wrote:
> On Fri, Dec 17, 2004 at 15:36:58 -0500,
> Greg Stark <gsstark(at)mit(dot)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.
That should have been 2N-1 nodes.