65.3. Extensibility
SP-GiST 提供了具有高度抽象的接口，要求访问方法开发人员仅实现特定于给定数据类型的方法。 SP-GiST 核心负责高效的磁盘 Map 和搜索树结构。它还考虑了并发性和日志记录注意事项。
SP-GiST 树的叶 Tuples 包含与索引列相同的数据类型的值。根级别的叶 Tuples 将始终包含原始索引数据值，但较低级别的叶 Tuples 可能仅包含压缩的表示形式，例如后缀。在那种情况下，操作员类别支持功能必须能够使用从内部 Tuples 累积的信息重建原始值，这些内部 Tuples 通过这些信息到达叶级别。
内部 Tuples 更为复杂，因为它们是搜索树中的分支点。每个内部 Tuples 包含一组一个或多个* node ，它们代表相似叶值的组。一个节点包含一个下行链路，该下行链路通向另一个较低级别的内部 Tuples，或通向全部位于同一索引页上的叶 Tuples 的简短列表。每个节点通常都有一个描述它的“标签”；例如，在基数树中，节点标签可以是字符串值的下一个字符。 (或者，如果操作符类对所有内部 Tuples 使用一组固定的节点，则可以省略节点标签；请参见Section 65.4.2。)可选地，内部 Tuples 可以具有 prefix *值来描述其所有成员。在基数树中，这可能是所表示字符串的通用前缀。前缀值不一定是 true 的前缀，而可以是运算符类所需的任何数据；例如，在四叉树中，它可以存储相对于四个象限进行测量的中心点。然后，四叉树内部 Tuples 还将包含与该中心点周围的象限相对应的四个节点。
一些树算法需要了解当前 Tuples 的级别(或深度)，因此 SP-GiST 核心为操作员类提供了在树下降时 Management 级别计数的可能性。还支持在需要时以增量方式重建表示的值，并支持在树下降期间传递附加数据(称为“遍历值”)。
Note
SP-GiST 核心代码负责空条目。尽管 SP-GiST 索引确实将空条目存储在索引列中，但这在索引运算符类代码中是隐藏的：绝不会将空索引条目或搜索条件传递给运算符类方法。 (假定 SP-GiST 运算符是严格的，因此对于空值无法成功执行.)因此，此处不再讨论空值。
SP-GiST 的索引运算符类必须提供五种用户定义的方法，其中一种是可选的。所有五个强制方法都遵循接受两个internal参数的约定，第一个参数是指向包含支持方法 Importing 值的 C 结构的指针，而第二个参数是指向必须放置输出值的 C 结构的指针。四个强制方法只返回void，因为它们的所有结果都出现在输出结构中；但leaf_consistent另外会返回boolean结果。这些方法不得修改其 Importing 结构的任何字段。在所有情况下，在调用用户定义的方法之前，将输出结构初始化为零。可选的第六种方法compress接受要索引的数据作为唯一参数，并返回适合物理存储在叶 Tuples 中的值。
用户定义的五种强制性方法是：
-
config- 返回有关索引实现的静态信息，包括前缀的数据类型 OID 和节点标签数据类型。
该函数的 SQL 声明必须如下所示：
CREATE FUNCTION my_config(internal, internal) RETURNS void ...
第一个参数是指向spgConfigIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgConfigOut C 结构的指针，该函数必须用结果数据填充。
typedef struct spgConfigIn
{
Oid attType; /* Data type to be indexed */
} spgConfigIn;
typedef struct spgConfigOut
{
Oid prefixType; /* Data type of inner-tuple prefixes */
Oid labelType; /* Data type of inner-tuple node labels */
Oid leafType; /* Data type of leaf-tuple values */
bool canReturnData; /* Opclass can reconstruct original data */
bool longValuesOK; /* Opclass can cope with values > 1 page */
} spgConfigOut;
传递attType是为了支持多态索引运算符类；对于普通的固定数据类型运算符类，它将始终具有相同的值，因此可以忽略。
对于不使用前缀的运算符类，可以将prefixType设置为VOIDOID。同样，对于不使用节点标签的运算符类，可以将labelType设置为VOIDOID。如果操作符类能够重建原始提供的索引值，则应将canReturnData设置为 true。仅当attType的长度可变并且操作员类能够通过重复后缀来分割长值时，才应将longValuesOK设置为 true(请参见Section 65.4.1)。
leafType通常与attType相同。出于向后兼容性的原因，方法config可以使leafType未初始化；与设置leafType等于attType的效果相同。如果attType和leafType不同，则必须提供可选方法compress。方法compress负责将要从attType索引到leafType的原点转换。注意：两个一致的函数都将保持scankeys不变，而无需使用compress进行转换。
-
choose- 选择一种将新值插入内部 Tuples 的方法。
该函数的 SQL 声明必须如下所示：
CREATE FUNCTION my_choose(internal, internal) RETURNS void ...
第一个参数是指向spgChooseIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgChooseOut C 结构的指针，该函数必须用结果数据填充。
typedef struct spgChooseIn
{
Datum datum; /* original datum to be indexed */
Datum leafDatum; /* current datum to be stored at leaf */
int level; /* current level (counting from zero) */
/* Data from current inner tuple */
bool allTheSame; /* tuple is marked all-the-same? */
bool hasPrefix; /* tuple has a prefix? */
Datum prefixDatum; /* if so, the prefix value */
int nNodes; /* number of nodes in the inner tuple */
Datum *nodeLabels; /* node label values (NULL if none) */
} spgChooseIn;
typedef enum spgChooseResultType
{
spgMatchNode = 1, /* descend into existing node */
spgAddNode, /* add a node to the inner tuple */
spgSplitTuple /* split inner tuple (change its prefix) */
} spgChooseResultType;
typedef struct spgChooseOut
{
spgChooseResultType resultType; /* action code, see above */
union
{
struct /* results for spgMatchNode */
{
int nodeN; /* descend to this node (index from 0) */
int levelAdd; /* increment level by this much */
Datum restDatum; /* new leaf datum */
} matchNode;
struct /* results for spgAddNode */
{
Datum nodeLabel; /* new node's label */
int nodeN; /* where to insert it (index from 0) */
} addNode;
struct /* results for spgSplitTuple */
{
/* Info to form new upper-level inner tuple with one child tuple */
bool prefixHasPrefix; /* tuple should have a prefix? */
Datum prefixPrefixDatum; /* if so, its value */
int prefixNNodes; /* number of nodes */
Datum *prefixNodeLabels; /* their labels (or NULL for
* no labels) */
int childNodeN; /* which node gets child tuple */
/* Info to form new lower-level inner tuple with all old nodes */
bool postfixHasPrefix; /* tuple should have a prefix? */
Datum postfixPrefixDatum; /* if so, its value */
} splitTuple;
} result;
} spgChooseOut;
datum是spgConfigIn的原始基准。 attType要插入索引的类型。 leafDatum是spgConfigOut的值。 leafType类型，最初是在提供方法compress时将方法compress应用于datum的结果，否则是与datum相同的值。如果choose或picksplit方法将其更改，则leafDatum可以在树的较低级别更改。当插入搜索到达叶子页面时，leafDatum的当前值将存储在新创建的叶子 Tuples 中。 level是当前内部 Tuples 的级别，从根级别的零开始。如果当前内部 Tuples 被标记为包含多个等效节点，则allTheSame为 true(请参见Section 65.4.3)。如果当前内部 Tuples 包含前缀，则hasPrefix为 true；否则为hasPrefix。如果是，则prefixDatum是其值。 nNodes是内部 Tuples 中包含的子节点的数量，nodeLabels是其标签值的数组，如果没有标签，则为 NULL。
choose函数可以确定新值与现有子节点之一匹配，或者必须添加新的子节点，或者新值与 Tuples 前缀不一致，因此必须拆分内部 Tuples 以创建一个限制性较小的前缀。
如果新值与现有子节点之一匹配，则将resultType设置为spgMatchNode。将nodeN设置为节点数组中该节点的索引(从零开始)。将levelAdd设置为通过该节点下降引起的level增量，如果操作员类不使用级别，则将其设置为零。如果操作员类未将基准从一个级别修改到下一个级别，请将restDatum设置为等于leafDatum，否则将其设置为修改的值以用作下一个级别的leafDatum。
如果必须添加新的子节点，请将resultType设置为spgAddNode。将nodeLabel设置为用于新节点的标签，并将nodeN设置为将节点插入节点数组的索引(从零开始)。添加节点后，将使用修改后的内部 Tuples 再次调用choose函数。该调用应导致spgMatchNode结果。
如果新值与 Tuples 前缀不一致，则将resultType设置为spgSplitTuple。该动作将所有现有节点移动到新的较低级内部 Tuples 中，并用具有指向新低级内部 Tuples 的单个下行链路的 Tuples 来替换现有的内部 Tuples。设置prefixHasPrefix以指示新的上级 Tuples 是否应具有前缀，如果是，则将prefixPrefixDatum设置为前缀值。此新前缀值的限制必须比原始限制少得多，以接受要索引的新值。将prefixNNodes设置为新 Tuples 中所需的节点数，并将prefixNodeLabels设置为包含其标签的 palloc 数组，或者将prefixNodeLabels设置为 NULL(如果不需要节点标签)。请注意，新的上层 Tuples 的总大小必须不超过要替换的 Tuples 的总大小；这限制了新前缀和新标签的长度。将childNodeN设置为将下行到新的较低级内部 Tuples 的节点的索引(从零开始)。设置postfixHasPrefix以指示新的较低级内部 Tuples 是否应具有前缀，如果是，则将postfixPrefixDatum设置为前缀值。这两个前缀和下行链路节点标签(如果有)的组合必须具有与原始前缀相同的含义，因为没有机会更改移至新的下级 Tuples 的节点标签，也没有任何更改的机会。子索引条目。拆分节点后，将使用替换内部 Tuples 再次调用choose函数。如果spgSplitTuple操作未创建合适的节点，则该调用可能返回spgAddNode结果。最终choose必须返回spgMatchNode才能使插入下降到下一个级别。
-
picksplit- 决定如何在一组叶 Tuples 上创建新的内部 Tuples。
该函数的 SQL 声明必须如下所示：
CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...
第一个参数是指向spgPickSplitIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgPickSplitOut C 结构的指针，该函数必须用结果数据填充。
typedef struct spgPickSplitIn
{
int nTuples; /* number of leaf tuples */
Datum *datums; /* their datums (array of length nTuples) */
int level; /* current level (counting from zero) */
} spgPickSplitIn;
typedef struct spgPickSplitOut
{
bool hasPrefix; /* new inner tuple should have a prefix? */
Datum prefixDatum; /* if so, its value */
int nNodes; /* number of nodes for new inner tuple */
Datum *nodeLabels; /* their labels (or NULL for no labels) */
int *mapTuplesToNodes; /* node index for each leaf tuple */
Datum *leafTupleDatums; /* datum to store in each new leaf tuple */
} spgPickSplitOut;
nTuples是提供的叶子 Tuples 的数量。 datums是其spgConfigOut的基准值的数组。 leafType类型。 level是所有叶 Tuples 共享的当前级别，它将成为新内部 Tuples 的级别。
设置hasPrefix以指示新的内部 Tuples 是否应具有前缀，如果是，则将prefixDatum设置为前缀值。设置nNodes以指示新内部 Tuples 将包含的节点数，并将nodeLabels设置为其标签值的数组，或者将nodeLabels设置为 NULL(如果不需要节点标签)。将mapTuplesToNodes设置为一个数组，该数组给出每个叶 Tuples 应分配给的节点的索引(从零开始)。将leafTupleDatums设置为要存储在新叶 Tuples 中的值的数组(如果操作员类未将基准从一个级别修改到另一个级别，则这些值将与 Importingdatums相同)。请注意，picksplit函数负责对nodeLabels，mapTuplesToNodes和leafTupleDatums数组进行分配。
如果提供了多个叶 Tuples，则预期picksplit函数会将它们分类为多个节点；否则，否则，不可能将叶 Tuples 拆分为多个页面，这是此操作的最终目的。因此，如果picksplit函数最终将所有叶 Tuples 放置在同一节点中，则核心 SP-GiST 代码将覆盖该决策，并生成一个内部 Tuples，其中，叶 Tuples 被随机分配给几个相同标签的节点。这样的 Tuples 标记为allTheSame，表示已发生这种情况。 choose和inner_consistent函数必须适当注意此类内部 Tuples。有关更多信息，请参见Section 65.4.3。
只有在config函数将longValuesOK设置为 true 且已提供大于页面 Importing 值的情况下，才能将picksplit应用于单个叶 Tuples。在这种情况下，操作的重点是剥离前缀并产生新的较短的叶子基准值。该调用将重复进行，直到生成了足够短以适合页面的叶数据为止。有关更多信息，请参见Section 65.4.1。
-
inner_consistent- 返回树搜索期间要遵循的节点(分支)集。
该函数的 SQL 声明必须如下所示：
CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...
第一个参数是指向spgInnerConsistentIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgInnerConsistentOut C 结构的指针，该函数必须用结果数据填充。
typedef struct spgInnerConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
int nkeys; /* length of array */
Datum reconstructedValue; /* value reconstructed at parent */
void *traversalValue; /* opclass-specific traverse value */
MemoryContext traversalMemoryContext; /* put new traverse values here */
int level; /* current level (counting from zero) */
bool returnData; /* original data must be returned? */
/* Data from current inner tuple */
bool allTheSame; /* tuple is marked all-the-same? */
bool hasPrefix; /* tuple has a prefix? */
Datum prefixDatum; /* if so, the prefix value */
int nNodes; /* number of nodes in the inner tuple */
Datum *nodeLabels; /* node label values (NULL if none) */
} spgInnerConsistentIn;
typedef struct spgInnerConsistentOut
{
int nNodes; /* number of child nodes to be visited */
int *nodeNumbers; /* their indexes in the node array */
int *levelAdds; /* increment level by this much for each */
Datum *reconstructedValues; /* associated reconstructed values */
void **traversalValues; /* opclass-specific traverse values */
} spgInnerConsistentOut;
长度为nkeys的数组scankeys描述了索引搜索条件。这些条件与 AND 结合使用-只有满足所有条件的索引条目才有意义。 (请注意nkeys = 0 表示所有索引条目都满足查询.)通常，一致性函数只关心每个数组条目的sk_strategy和sk_argument字段，它们分别提供可索引的运算符和比较值。特别是，不必检查sk_flags来查看比较值是否为 NULL，因为 SP-GiST 核心代码将过滤掉这种情况。 reconstructedValue是为父 Tuples 重构的值；在根级别为(Datum) 0，或者inner_consistent函数未在父级别提供值。 reconstructedValue始终是spgConfigOut。 leafType类型。 traversalValue是指向从父索引 Tuples 上的inner_consistent的先前调用向下传递的任何遍历数据的指针，或在根级别为 NULL。 traversalMemoryContext是用于存储输出遍历值的内存上下文(请参见下文)。 level是当前内部 Tuples 的级别，从根级别的零开始。如果此查询需要重建的数据，则returnData为true；仅当config函数 assertcanReturnData时才如此。如果当前内部 Tuples 标记为“全部相同”，则allTheSame为 true；在这种情况下，所有节点都具有相同的标签(如果有的话)，因此全部或都不匹配查询(请参见Section 65.4.3)。如果当前内部 Tuples 包含前缀，则hasPrefix为 true；否则为hasPrefix。如果是这样，则prefixDatum是其值。 nNodes是内部 Tuples 中包含的子节点数，nodeLabels是其标签值的数组，如果节点没有标签，则为 NULL。
必须将nNodes设置为搜索需要访问的子节点的数量，并且将nodeNumbers设置为其索引的数组。如果操作员类别跟踪级别，则将levelAdds设置为下降到要访问的每个节点时所需的级别增量的数组。 (通常，所有节点的这些增量都是相同的，但不一定如此，因此使用数组.)如果需要值重构，请将reconstructedValues设置为spgConfigOut的值数组。为每个要访问的子节点重建leafType类型；否则，将reconstructedValues保留为 NULL。如果希望将附加的带外信息(“遍历值”)传递给树搜索的较低级别，请将traversalValues设置为适当的遍历值的数组，每个要访问的子节点一个；否则，将traversalValues保留为 NULL。请注意，inner_consistent函数负责在当前内存上下文中分配nodeNumbers，levelAdds，reconstructedValues和traversalValues数组。但是，traversalValues数组所指向的任何输出遍历值都应在traversalMemoryContext中分配。每个遍历值必须是单个分配的块。
-
leaf_consistent- 如果叶子 Tuples 满足查询，则返回 true。
该函数的 SQL 声明必须如下所示：
CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...
第一个参数是指向spgLeafConsistentIn C 结构的指针，该结构包含函数的 Importing 数据。第二个参数是指向spgLeafConsistentOut C 结构的指针，该函数必须用结果数据填充。
typedef struct spgLeafConsistentIn
{
ScanKey scankeys; /* array of operators and comparison values */
int nkeys; /* length of array */
Datum reconstructedValue; /* value reconstructed at parent */
void *traversalValue; /* opclass-specific traverse value */
int level; /* current level (counting from zero) */
bool returnData; /* original data must be returned? */
Datum leafDatum; /* datum in leaf tuple */
} spgLeafConsistentIn;
typedef struct spgLeafConsistentOut
{
Datum leafValue; /* reconstructed original data, if any */
bool recheck; /* set true if operator must be rechecked */
} spgLeafConsistentOut;
长度为nkeys的数组scankeys描述了索引搜索条件。这些条件与 AND 结合使用-只有满足所有条件的索引条目才能满足查询。 (请注意nkeys = 0 表示所有索引条目都满足查询.)通常，一致性函数只关心每个数组条目的sk_strategy和sk_argument字段，它们分别提供可索引的运算符和比较值。特别是，不必检查sk_flags来查看比较值是否为 NULL，因为 SP-GiST 核心代码将过滤掉这种情况。 reconstructedValue是为父 Tuples 重构的值；在根级别为(Datum) 0，或者inner_consistent函数未在父级别提供值。 reconstructedValue始终是spgConfigOut。 leafType类型。 traversalValue是指向从父索引 Tuples 上的inner_consistent的先前调用向下传递的任何遍历数据的指针，在根级别为 NULL。 level是当前叶 Tuples 的级别，从根级别的零开始。如果此查询需要重建的数据，则returnData为true；仅当config函数 assertcanReturnData时才如此。 leafDatum是spgConfigOut的键值。 leafType存储在当前叶 Tuples 中。
如果叶子 Tuples 与查询匹配，则该函数必须返回true，否则返回false。在true的情况下，如果returnData是true，则必须将leafValue设置为spgConfigIn的值。最初提供的attType类型为此叶子 Tuples 构建索引。此外，如果匹配不确定，则recheck可以设置为true，因此必须将运算符重新应用于实际的堆 Tuples 以验证匹配。
可选的用户定义方法是：
-
Datum compress(Datum in)- 将数据项转换为适合物理存储在索引页的叶 Tuples 中的格式。它接受
spgConfigIn。attType值并返回spgConfigOut。leafType值。不得烘烤输出值。
- 将数据项转换为适合物理存储在索引页的叶 Tuples 中的格式。它接受
通常在短期内存上下文中调用所有 SP-GiST 支持方法。也就是说，CurrentMemoryContext将在处理每个 Tuples 后重置。因此，担心 pfreeing 分配 palloc 的所有内容并不是很重要。 (config方法是一个 exception：它应尽量避免泄漏内存.但是通常config方法无需执行任何操作，只不过将常量分配给传递的参数 struct.)
如果索引列是可排序数据类型，则将使用标准PG_GET_COLLATION()机制将索引排序规则传递给所有支持方法。
