- **Description**: "Space-Partitioned GiST". It's a framework for non-balanced trees where the search space can be recursively partitioned into non-overlapping regions (e.g., Quadtrees, Octrees, or Tries). - **Data Structure**: - **The Configuration (`spgConfig`)**: Each SP-GiST opclass defines how the space is split. For example, a Quadtree splits into 4 nodes, while a Radix Tree (Trie) might split by the next character in a string. - **Internal Nodes (`spg_opaque`)**: Unlike B-Tree internal pages which have a dynamic number of children, SP-GiST internal pages contain a **Fixed-size Array of Nodes**. Each node corresponds to a specific partition (e.g., "Quadrant 1" or "Letter A"). - **Leaf Suffixes**: Because SP-GiST partitions are non-overlapping, the path to a leaf already implies a common prefix. To save space, leaf nodes only store the **Suffix** (the part of the data not already defined by the parent nodes). - **Non-Balanced Architecture**: Because it follows the data's natural distribution rather than forced height-balancing, depth can vary. A deeply nested "heavy" prefix will result in a long chain of pages, while sparse areas stay shallow. - **Supported Operators**: Varies (e.g., `<<`, `>>`, `~=`, `<@`). - **Special Features**: - **Prefix Search**: Highly efficient for phone numbers, IP addresses, or strings with common prefixes. - **Clustering**: Naturally clusters similar items together in the same physical pages. - **Metaphor**: A radar map partitioned into quadrants. If you're looking for something in the North-East, you go to that quadrant's desk. That desk might then split the room into four even smaller cubicles. You don't bother looking elsewhere!