On Fri, Dec 17, 2004 at 15:12:18 -0600,
Bruno Wolff III <bruno@wolff.to> wrote:
> 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.
That should have been 2N-1 nodes.
