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