SP-GiST

A General Index Framework for Space Partitioning Trees

Emerging database applications require the use of new indexing structures beyond B-trees and R-trees. Examples are the k-d tree, the trie, the quadtree, and their variants. They are often proposed as supporting structures in data mining, GIS, CAD/CAM and biological database applications. A common feature of all these indexes is that they recursively divide the space into partitions.

SP-GiST Version 2 is an indexing tool that works under PostgreSQL. It allows the creation of non-traditional disk-based indexes that belong to the class of space-partitioning trees to serve the needs of emerging database applications.. Examples of indexes one can instantiate in PostgreSQL using SP-GiST are disk-based versions of the trie and its variants (e.g., patricia tries), quad-trees and their variants (e.g., the point quad-tree, the PMR quad-tree, and the oct-tree), and k-d trees.