Tom Lane <tgl@sss.pgh.pa.us> writes:
> Greg Stark <gsstark@mit.edu> writes:
> > Bruno Wolff III <bruno@wolff.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