From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
---|---|
To: | Alvaro Herrera <alvherre(at)atentus(dot)com> |
Cc: | PgSQL Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: btree page merging |
Date: | 2002-09-13 05:11:04 |
Message-ID: | 15618.1031893864@sss.pgh.pa.us |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-hackers |
Alvaro Herrera <alvherre(at)atentus(dot)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
From | Date | Subject | |
---|---|---|---|
Next Message | Justin Clift | 2002-09-13 05:28:12 | An opportunity to prove PostgreSQL and our requirement of Case Study info |
Previous Message | Alvaro Herrera | 2002-09-13 04:59:59 | Re: |