Re: B-Tree in PostgreSQL

Xiaolei Li wrote:
> hi, i'm new to PostgreSQL and have just been briefly reading the feature
> list. i think i remember seeing somewhere that PostgreSQL can index
> using the B-Tree. does this literally mean the original B-Tree? or is
> it a variation such as B+Tree or B*Tree? the reason i ask is that i
> need sequential access to the data as provided by the B+Tree. (that has
> all the data in the leaves and has links between the leaves.) thank you.

It's nbtree, or new btree, or specifically:

This directory contains a correct implementation of Lehman and Yao's
high-concurrency B-tree management algorithm (P. Lehman and S. Yao,
Efficient Locking for Concurrent Operations on B-Trees, ACM Transactions
on Database Systems, Vol 6, No. 4, December 1981, pp 650-670). We also
use a simplified version of the deletion logic described in Lanin and
Shasha (V. Lanin and D. Shasha, A Symmetric Concurrent B-Tree Algorithm,
Proceedings of 1986 Fall Joint Computer Conference, pp 380-389).

There is a README in /src/backend/access/nbtree that explains the
details. I am not sure about the links you describe.

--
Bruce Momjian | http://candle.pha.pa.us
pgman(at)candle(dot)pha(dot)pa(dot)us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073