Re: Brain dump: btree collapsing

"Curtis Faith" <curtis(at)galtcapital(dot)com> writes:
> Another way this could be handled is by not merging onto one of the
> existing pages but to a brand new page, a kind of special case shadow
> index page.

Hmmm ... that might be made to work, but it would complicate inserts.
By the time an insert navigates to the page it should insert on, it
might find the page is dead, and then it would have no easy way to get
to the replacement page (unless you want to dedicate another link field
in every index page for that one use). I suppose it could recover by
starting the search over again.

Another problem is that the two dead pages are now outside of the btree
structure and so their left and right links won't get updated in the
face of subsequent splits and merges of the nearby pages. I spent quite
a bit of time sweating over the recovery navigation details in my
original proposal; I can assure you it's not easy to get right. You can
chain right from a dead page with some reliability, but left is another
matter. There's no good way to know, when following a left link,
whether you've arrived at the proper place or need to chain right to
make up for a subsequent split. The recovery procedure I proposed works
for removing single pages, but it won't work with substituted pages.

regards, tom lane