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@candle.pha.pa.us               |  (610) 359-1001
  +  If your life is a hard drive,     |  13 Roberts Road
  +  Christ can be your backup.        |  Newtown Square, Pennsylvania 19073