Bruno Wolff III <[EMAIL PROTECTED]> writes:
> Greg Stark <[EMAIL PROTECTED]> 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
---------------------------(end of broadcast)---------------------------
TIP 1: subscribe and unsubscribe commands go to [EMAIL PROTECTED]
