Thread: btree page merging

Hackers,

I'm starting to read the existing algorithms for btree index shrinking.
Right now I'm at 1996 SIGMOD proceedings, Zou and Salzberg "On-line
Reorganization of Sparsely-populated B+-trees".

What I want to know is how different from B+-trees are PostgreSQL
B-trees; I've read the README in src/backend/access/nbtree/, and it
indicates some areas in which they are different from B-Trees (Lehmann
and Yao's?).  But I don't really know how B-Trees are different from
B+-Trees (is my ignorance starting to show?).  Where can I read about
that?

Also, Tom said some time ago that there is some literature on the
concurrent page merging camp.  I haven't been able to found anything
else than the proceedings I have right now...  is there something else?
I'm not used to searching for this kind of things, and ACM won't let me
in (althought my university has a subscription, I can't get any papers
on SIGMOD).

Thank you,

-- 
Alvaro Herrera (<alvherre[a]atentus.com>)
"Un poeta es un mundo encerrado en un hombre" (Victor Hugo)

Alvaro Herrera <alvherre@atentus.com> writes:
> What I want to know is how different from B+-trees are PostgreSQL
> B-trees;

PG's "btrees" are in fact B+-trees according to the more formal
academic notation.  IIRC the + just indicates allowing any number
of keys/downlinks in an internal tree node.
I've read the README in src/backend/access/nbtree/, and it
> indicates some areas in which they are different from B-Trees (Lehmann
> and Yao's?).

The L-Y paper omits some details, and it makes some unrealistic
assumptions like all keys being the same size.  nbtree/README is
just trying to tell you how we filled in those holes.  It's not really
a new algorithm, just L-Y brought from academic to production status.

> I'm not used to searching for this kind of things, and ACM won't let me
> in (althought my university has a subscription, I can't get any papers
> on SIGMOD).

Complain --- I have half a dozen btree-related papers stashed that
I got from ACM's online library.  They are an essential resource.

BTW, SIGMOD is presently selling DVDs with every durn paper they ever
published for the last couple or three decades.  I was fortunate enough
to get a set for US$25 when I went to their conference this summer.
The price for non-members is about triple that, but it's still a steal.
        regards, tom lane