SPGiST

SP-GiST, or Space-Partitioned Generalized Search Tree, is an index access method in PostgreSQL designed to support non-balanced, space-partitioning data structures. It provides a framework for implementing specialized index types by partitioning the data space into subspaces, rather than maintaining a single linear ordering. SP-GiST builds on the GiST (Generalized Search Tree) interface and relies on a family of functions that describe how to partition, compare, and navigate index keys.

In SP-GiST, index types are created by supplying a set of methods that govern how nodes are split, stored, and searched. Key functions include those that determine how to select a split of entries (picksplit), how to measure the cost of inserting new entries (penalty), and how to merge or compare keys (union and consistency). This design enables the creation of various space-partitioning strategies where different data distributions can be indexed efficiently.

Common SP-GiST partitioning schemes include quadtrees, k-d trees, prefix trees, and radix trees. Each scheme partitions the data space in a distinct way to support different query patterns, such as multi-dimensional range queries, nearest-neighbor lookups, or prefix-based matches. The leaves of an SP-GiST index store pointers to table rows or heap tuples, while internal nodes contain partition descriptors that guide searches toward relevant subspaces.

Usage and considerations: SP-GiST is suitable for workloads involving spatial or multi-dimensional data, or data with natural partitions that can be exploited by a space-partitioning tree. Performance depends on the chosen partitioning strategy, data distribution, and query types. Not all data types or operators are supported; implementing a new SP-GiST index type requires defining the appropriate functions within PostgreSQL’s extension framework.

See also: GiST, PostgreSQL, spatial indexing.