Message-ID: 
 <16891246.1127951399015.JavaMail.root@elwamui-polski.atl.sa.earthlink.net>
Date: Wed, 28 Sep 2005 19:49:59 -0400 (EDT)
From: Ron Peacetree <rjpeace@earthlink.net>
Reply-To: Ron Peacetree <rjpeace@earthlink.net>
To: pgsql-hackers@postgresql.org, pgsql-performance@postgresql.org
Subject: Re: [PERFORM] A Better External Sort?
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

In the interest of efficiency and "not reinventing the wheel", does anyone know
where I can find C or C++ source code for a Btree variant with the following
properties:

A= Data elements (RIDs) are only stored in the leaves, Keys (actually
KeyPrefixes; see "D" below) and Node pointers are only stored in the internal
nodes of the Btree.

B= Element redistribution is done as an alternative to node splitting in overflow
conditions during Inserts whenever possible.

C= Variable length Keys are supported.

D= Node buffering with a reasonable replacement policy is supported.

E= Since we will know beforehand exactly how many RID's will be stored, we
will know apriori how much space will be needed for leaves, and will know the
worst case for how much space will be required for the Btree internal nodes
as well.  This implies that we may be able to use an array, rather than linked
list, implementation of the Btree.  Less pointer chasing at the expense of more
CPU calculations, but that's a trade-off in the correct direction. 

Such source would be a big help in getting a prototype together.

Thanks in advance for any pointers or source,
Ron