SP-GiST (Space-Partitioned GiST)
|Beginning of an SP-GiST leaf page|
SP-GiST is unique among index access methods whose index structure is tree-like, in that it supports tree structures that are unbalanced. SP-GiST operator classes exist that support k-d trees, quadtrees, and suffix trees. These structures are traditionally only suited to a fully in-memory representation, with dynamically-allocated nodes that contain a small number of simple pointers (byte addresses) pointing to other nodes.
SP-GiST presents a generalized interface through which all of these space-partitioned trees can be constructed for a given datatype, in a way that minimizes disk seeks (PDF) and works well with block-orientated storage. Essentially, SP-GiST maps tree nodes onto disk blocks in an adaptive fashion, rather than simply having a block directly correspond to a tree node, as happens with other access methods.
There are particularly intricate data structures needed to support all of this. Space utilization can be an issue with SP-GiST indexes, though that's probably very workload dependent. This is something that pg_hexedit can be effective at representing visually.
SP-GiST is a good example of the PostgreSQL community implementing a concept that comes directly from state of the art database research (PDF). I suspect that we have yet to fully realize the benefit of SP-GiST for specific application domains, due to a simple lack of awareness among users and potential users that work in those domains. Perhaps this enhancement can contribute in some small way towards a better understanding of what is possible.
BRIN (Block Range Index)
|BRIN "revmap" page|
|BRIN summary page|