![[assets/str_idx_spgist.png|256]] - **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**: - **Internal Nodes**: Contain a set of non-overlapping "nodes" that partition the space. Each node points to a child page. - **Leaf Nodes**: Contain the actual TIDs. Unlike GiST or B-Tree, SP-GiST can store "suffix" values in leaves if the common prefix was already handled by internal nodes (Trie-like behavior). - **Non-Balanced**: The tree depth can vary significantly depending on the data distribution. - **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!