SP-GiST
SP-GiST is an index structure in database systems that organizes data by repeatedly partitioning the space into unequal, non-overlapping regions. It is particularly well suited for irregular data such as geographic coordinates, phone numbers, or text, where classical indexing methods become slow.
If a database contains millions of entries, it would be far too slow to check every single entry individually for each search. That’s why a database creates an index — a kind of table of contents that points directly to the relevant locations. SP-GiST is a special type of such an index. The abbreviation stands for Space-Partitioned Generalized Search Tree. That sounds cumbersome, but it describes a concrete principle: SP-GiST repeatedly splits the area in which data resides into smaller sections — similar to how one subdivides a map into regions, then into cities, then into neighborhoods. Crucially, these sections do not overlap and may be of different sizes.
What SP-GiST is used for in practice
Classical index structures like the B-tree work well when data is evenly distributed — for example, customer numbers or prices. But much real-world data is irregular: addresses cluster in cities, phone numbers follow country codes, geographic points cluster in inhabited areas. For such data, an index that partitions evenly is inefficient.
SP-GiST adapts its partitioning to the actual distribution of the data. Where many entries lie close together, finer subdivisions emerge. Sparsely populated areas remain grouped coarsely. This makes search queries on such data considerably faster, because the index can skip large empty areas in a single step. In this way, SP-GiST fills a gap that B-trees and similar structures leave open.
The principle behind the spatial partitioning
SP-GiST internally builds a tree structure — a hierarchy of nodes, each pointing to smaller sub-nodes. Every inner node represents a region. It splits this region into sub-regions that do not overlap with one another. Only at the very bottom of the tree, in the so-called leaf nodes, do the actual data records reside.
A typical example is the quadtree: it repeatedly divides a two-dimensional area into four quadrants. SP-GiST can use this principle as one of several possible strategies. Likewise, it supports kd-trees, which alternately split horizontally and vertically, or trie structures, which break down strings letter by letter. All these variants follow the same basic idea: non-overlapping, hierarchical partitioning.
The “Generalized” in the name means that SP-GiST does not prescribe a fixed method. Instead, it provides a framework into which various partitioning strategies can be plugged. Database developers can implement their own strategies, as long as these adhere to the non-overlap principle. This makes SP-GiST more flexible than many specialized competing structures.
SP-GiST in databases and geo-services
SP-GiST is best known from PostgreSQL, a widely used open-source database system. There, this index type has been available since version 8.2 and can be created with a single command. PostgreSQL ships ready-made SP-GiST strategies for point coordinates, geometric shapes, IP address ranges, and text.
SP-GiST is particularly common in connection with geodata. Anyone searching for all restaurants within two kilometers of a certain point is making what’s called a radius query. Without an index, the database would have to check every address individually. With an SP-GiST index on the coordinates, it can exclude entire regions that lie too far away, arriving at the result in a fraction of the time.
A common misconception is to confuse SP-GiST with GiST. GiST — without the “SP” — is also a generalized search tree, but it allows overlapping regions. This is useful for certain kinds of data, but it costs more effort during search, since multiple overlapping branches must be followed simultaneously. SP-GiST deliberately forgoes overlap and is therefore faster for suitable data. Which of the two index types is the better fit depends on the specific use case.