Re: sorting problem

Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Greg Stark <gsstark(at)mit(dot)edu> writes:
> > Bruno Wolff III <bruno(at)wolff(dot)to> writes:
> >> Using an index to do an order by is an order N operation.
>
> > No, using an index to do an order by is actually still n*log(n). You have to
> > traverse all the parent pages in the binary tree of the index as well.
>
> Only if you searched afresh from the root for each key, which an
> indexscan is not going to do.

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?

--
greg