On Sat, 21 Jan 2006, Tom Lane wrote:
> Ron <rjpeace@earthlink.net> writes:
>> At 07:23 PM 1/20/2006, Tom Lane wrote:
>>> Well, we're trying to split an index page that's gotten full into
>>> two index pages, preferably with approximately equal numbers of items in
>>> each new page (this isn't a hard requirement though).
>
>> Maybe we are over thinking this. What happens if we do the obvious
>> and just make a new page and move the "last" n/2 items on the full
>> page to the new page?
>
> Search performance will go to hell in a handbasket :-(. We have to make
> at least some effort to split the page in a way that will allow searches
> to visit only one of the two child pages rather than both.
does the order of the items within a given page matter? if not this sounds
like a partial quicksort algorithm would work. you don't need to fully
sort things, but you do want to make sure that everything on the first
page is 'less' then everything on the second page so you can skip passes
that don't cross a page boundry
> It's certainly true though that finding the furthest pair is not a
> necessary component of that. It's reasonable if you try to visualize
> the problem in 2D or 3D, but I'm not sure that that geometric intuition
> holds up in such a high-dimensional space as we have here.
I will say that I'm not understanding the problem well enough to
understand themulti-dimentional nature of this problem.
David Lang