SAL Home DBASE Utilities & Other DBMS


n the beginning there was the B-tree. All database search trees since the B-tree have been variations on its theme. Recognizing this, a new kind of index called a Generalized Search Tree (GiST) was developed. GiST provides the functionality of all these trees in a single package, and is an extensible data structure, which allows users to develop indices over any kind of data, supporting any lookup over that data. This package unifies a number of popular search trees in one data structure (the long list of potentials includes R-trees, B+-trees, hB-trees, TV-trees, Ch-Trees, partial sum trees, ranked B+-trees, and many, many others), eliminating the need to build multiple search trees for handling diverse applications. In addition to unifying all these structures, the GiST has one key feature that previous trees lacked: both data and query extensibility.

There currently two different GiST implementations available:

  • libGiST: a C++ library that implements the GiST. Includes 3 test programs which demonstrate how to get B+-tree, R-Tree, and R*-tree functionality.
  • A GiST access method is now incorporated as a standard feature of the PostgreSQL Object-Relational DBMS. Documentation and example "opclasses" are available for indexing integers, text, boxes and polygons within PostgreSQL.

Current Version:   0.9 beta 1 (libGiST)

License Type:   Free and Copyrighted

Home Site:

Source Code Availability:   Yes

Available Binary Packages:

  • Debian Package:   No
  • RedHat RPM Package:   No
  • Other Packages:   No

Targeted Platforms:

libGiST was developed under HP/UX with g++ and under Windows NT with the Microsoft Visual C++ 4.1 compiler. It is also known to work on Solaris with g++ and Linux with g++.
GiST for PG95 was developed on HP/UX. It also works on Linux.

Software/Hardware Requirements:


Other Links:

Mailing Lists/USENET News Groups:


User Comments:

  • None

See A Screen Shot? (Not Yet)

  SAL Home   |   Database Systems   |   Utilities & Other DBMS

Comments? SAL@KachinaTech.COM
Copyright © 1995-2001 by Herng-Jeng Jou
Copyright © 1997-2001 by Kachina Technologies, Inc.
All rights reserved.