Bruno Wolff III <bruno@wolff.to> writes:
> 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.
Besides, we don't read any non-leaf pages except the ones down the left
edge of the btree. An indexscan just visits the leaf pages using their
sibling links to get from one to the next. (If it did otherwise, we'd
not produce the output in sorted order, which would make this discussion
moot...)
regards, tom lane