![[Home]](/~megera/oddmuse/zen3.gif)
SP-GiST is an abbreviation of space-partitioned GiST - the search tree, which allows to implement a wide range of different non-balanced disk-based data structures, such as quadtree, kd-tree, tries - popular data structures, originally developed for memory storage. Main memory access structures usually designed as a set of dynamically allocated nodes linked by pointers, which is not suitable for direct storing on disk, since these chains of pointers can be rather long and require too many disk accesses. In opposite, disk based data structures have a high fanout to minimize I/O. The challenge is to map nodes of tree to disk pages in such a way, so search algorithm accesses only a few disk pages, even if it traverse many nodes.
Logically, tree is a set of tuples, each of different number of children, each of which can also be an inner or leaf tuple. It's important to note, tha