On Sat, 21 Jan 2006, Tom Lane wrote:
Ron <rjpeace@xxxxxxxxxxxxx> 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
