59.4. Implementation
This section covers implementation details and other tricks that are useful for implementers ofSP-GiST operator classes to know.
Individual leaf tuples and inner tuples must fit on a single index page (8kB by default). Therefore, when indexing values of variable-length data types, long values can only be supported by methods such as radix trees, in which each level of the tree includes a prefix that is short enough to fit on a page, and the final leaf level includes a suffix also short enough to fit on a page. The operator class should setlongValuesOK to TRUE only if it is prepared to arrange for this to happen. Otherwise, theSP-GiST core will reject any request to index a value that is too large to fit on an index page.
Another limitation is that when an inner tuple's node points to a set of leaf tuples, those tuples must all be in the same index page. (This is a design decision to reduce seeking and save space in the links that chain such tuples together.) If the set of leaf tuples grows too large for a page, a split is performed and an intermediate inner tuple is inserted. For this to fix the problem, the new inner tuplemust divide the set of leaf values into more than one node group. If the operator class'spicksplit function fails to do that, theSP-GiST core resorts to extraordinary measures described inSection 59.4.3.
WhenlongValuesOK is true, it is expected that successive levels of theSP-GiST tree will absorb more and more information into the prefixes and node labels of the inner tuples, making the required leaf datum smaller and smaller, so that eventually it will fit on a page. To prevent bugs in operator classes from causing infinite insertion loops, theSP-GiST core will raise an error if the leaf datum does not become any smaller within ten cycles ofchoose method calls.
TheSP-GiST core can override the results of the operator class'spicksplit function whenpicksplit fails to divide the supplied leaf values into at least two node categories. When this happens, the new inner tuple is created with multiple nodes that each have the same label (if any) thatpicksplit gave to the one node it did use, and the leaf values are divided at random among these equivalent nodes. TheallTheSame flag is set on the inner tuple to warn thechoose andinner_consistent functions that the tuple does not have the node set that they might otherwise expect.