# 56.2\. 扩展性 SP-GiST提供了一个高度抽象的接口,只需要访问方法开发人员实现特定于给定数据类型的方法。SP-GiST核心负责高效的磁盘映射和搜索树结构。它还负责考虑并发性和日志记录。 SP-GiST树的叶元组包含和被索引列相同数据类型的值。 在根层级的叶元组总是包含原来的索引数据值,但是低层级的叶元组可能只包含一个压缩表示,如一个后缀。 在这种情况下,操作符类支持函数必须能够，通过利用从到达叶元组所经过的内部元组中收集到的信息，重建原始值。 内部元组更为复杂,因为它们是搜索树中的分支点。 每个内部元组包含由一个或多个_节点_组成的集合,表示一组类似的叶元组值。 一个节点包含一个链接指向另一个低级内部元组,或指向一个短的叶元组的列表，这些叶元组存储在相同的索引页面中。 每个节点都有一个用来描述它的_标签_。例如,在一个基数树中节点标签可以是字符串值的下一个字符。 可选地,一个内部元组可以有一个_前缀_值,描述了它的所有成员。 在基数树中这可能是其所代表的字符串的共同前缀。 前缀值不一定真的是一个前缀,可以是操作符类所要求的任何数据。 例如,在四叉树中它可以存储可度量四个象限的中心点，四叉树的内部元组也就会相应的存储四个节点，每个代表了这个中心点周围的一个象限。 一些树算法需要知道当前元组的层级(或深度),所以SP-GiST核心为操作符类提供了在向下访问树时管理层级计数的能力。 并且也支持在需要时递增地重建所代表的值。 > **Note:** SP-GiST核心代码考虑了null条目。 尽管SP-GiST索引为被索引列中的null值存储了的条目,但这对索引操作符类代码是隐藏的:null索引条目或搜索条件不会被传递给操作符类的方法。 (假定SP-GiST操作符是严格的,因此不能在null值上匹配成功。)因此后面也就不会再讨论null值的问题了。 一个用于SP-GiST的索引操作符类必须提供五个用户定义的方法。 所有五个方法按照约定接受两个`internal`参数，第一个参数是一个指向包含了支持方法的输入值的C结构体的指针，而第二个参数是一个指向放置输出值的C结构体的指针。其中四个方法只是返回void,因为它们所有的结果都出现在输出结构体里;但`leaf_consistent`返回一个布尔结果。这些方法不能修改输入结构体中的任何域。在所有情况下，在调用用户定义的方法之前，输出结构体的内容被用初始化为0。 五个用户定义的方法如下： `config` 返回关于索引实现的静态信息,包括前缀的数据类型OID和节点标签的数据类型。 函数的SQL声明必须看起来像这样: ``` CREATE FUNCTION my_config(internal, internal) RETURNS void ... ``` 第一个参数是一个指向C结构体`spgConfigIn`的指针,包含函数的输入数据。 第二个参数是一个指向C结构体`spgConfigOut`的指针,该函数必须填充结果数据到里面。 ``` 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 */ 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 56.3.1](#calibre_link-552))。 `choose` 选择一种方法将一个新值插入到一个内部元组。 函数的SQL声明必须看起来像这样: ``` CREATE FUNCTION my_choose(internal, internal) RETURNS void ... ``` 第一个参数是一个指向C结构体`spgChooseIn`的指针,包含函数的输入数据。 第二个参数是一个指向C结构体`spgChooseOut`的指针,该函数必须填充结果数据到里面。 ``` 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 inner tuple with one node */ bool prefixHasPrefix; /* tuple should have a prefix? */ Datum prefixPrefixDatum; /* if so, its value */ Datum nodeLabel; /* node's label */ /* 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`是被插入到索引的原始数据。 `leafDatum`最初和`datum`是一样的，如果函数`choose`或者`picksplit`把它修改了，在树的低层级可能会不同。 当插入搜索到达叶页面，当前的`leafDatum`值就是存储到新生成的叶元组中的值。 `level`是当前内部元组的层级，从0，也就是根的层级，开始计数。 如果当前内部元组包含多个等价节点，`allTheSame`为true(参见[Section 56.3.3](#calibre_link-553))。 如果当前内部元组包含前缀，`hasPrefix`为true。 此时，`prefixDatum`是前缀值。 `nNodes`是内部元组中包含子节点的数量，`nodeLabels`是它们的标签值的数组,或者是NULL如果没有标签的话。 `choose`函数可以确定新值匹配一个现有的子节点,或者必须添加一个新的子节点,或者新值与元组前缀不一致,所以内部元组必须分裂开以创建一个限制较少的前缀。 如果新值匹配的一个现有的子节点,把`resultType`设置为`spgMatchNode`。 把`nodeN`设置为那个索引节点在节点数组中的索引(从0开始)。 把`levelAdd`设置为，由下降到那个节点导致的`level`增量； 或者为0如果操作符类不使用层级。 把`restDatum`设置为和`datum`相等的值，如果操作符类从一个层级到下一个层级不会修改数据值；否则将其设置为修改后的值，它在下一个层级被用作`leafDatum`。 如果必须添加一个新的子节点,把`resultType`设置为`spgAddNode`。 设置`nodeLabel`为新节点的标签,并设置`nodeN`为插入位置在节点数组中的索引(从0开始)。 添加了节点后,`choose`函数将再次与被修改的内部元组一起被调用，那次调用应该导致一个`spgMatchNode`结果。 如果新值与元组前缀是不一致的,把`resultType`设置为`spgSplitTuple`。 这一动作把所有现有的节点移动到一个新的低层级的内部元组,并把现有内部元组替换为一个只有一个链接到新的低层级内部元组的单个节点的元组。 设定`prefixHasPrefix`表明是否新的较高的元组应该有一个前缀,如果是的话，设置`prefixPrefixDatum`为前缀值。 这个新的前缀值必须比原来的限制足够小以接受新的被索引值,而且应当不超过原前缀的长度。 设置`nodeLabel`为指向新的低层级内部元组的节点的标签值。 设定`postfixHasPrefix`表明是否新的较低的元组应该有一个前缀,如果是的话，设置`postfixPrefixDatum`为前缀值。 这两个前缀和额外的标签的组合必须与原始前缀具有相同的含义,因为没有机会改变被移动到新的低层级元组中的节点标签，也不能改变任何子索引条目。 节点被分裂后,`choose`会被再次调用，针对替换的内部元组。那个调用通常会导致`spgAddNode`结果,因为分裂步骤添加的节点标签可能不会匹配新值；所以在那之后,还会有第三次调用,最后的调用返回`spgMatchNode`,允许插入操作下去到叶层级。 `picksplit` 决定如何在一组叶元组之上创建一个新的内部元组。 函数的SQL声明必须看起来像这样: ``` CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ... ``` 第一个参数是一个指向C结构体`spgPickSplitIn`的指针,包含函数的输入数据。 第二个参数是一个指向C结构体`spgPickSplitOut`的指针,该函数必须填充结果数据到里面。 ``` 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`是提供的叶元组的数量。 `datums`是数据值的数组。 `level`是所有的叶元组共享的当前层级,这将成为新的内部元组的层级。 `hasPrefix`表明是否新的内部元组应该有一个前缀,如果是的话设置prefixDatum前缀值。 `nNodes`表明新内部元组将包含的节点数量,并设置`nodeLabels`为它们的标签值的数组。 (如果节点不需要标签,设置`nodeLabels`为NULL;有关详细信息,请参见[Section 56.3.2](#calibre_link-554)。) 设置`mapTuplesToNodes`为各个叶元组应该被分配的节点的索引(从0开始)的数组。 设置`leafTupleDatums`为存储在新的叶元组的值的数组(如果操作符类从一个层级到下一个层级不修改数据,它们将和输入数据相同)。 注意,`picksplit`函数负责分配(palloc) `nodeLabels`, `mapTuplesToNodes`和`leafTupleDatums`数组。 如果提供了不止一个叶元组,预计`picksplit`函数会把它们分类到多个节点,否则不可能把叶元组分裂到多个页面,这是这个操作的最终目的。 因此,如果`picksplit`函数最终把所有叶元组放在同一节点,核心SP-GiST代码将覆盖这一决定并生成一个内部元组，这些叶元组会被随机分配到这个内部元组的几个有等价标签(identically-labeled)的节点上。 这样的元组被设置了`allTheSame`标志，以表示发生这样的事情了。 `choose`和`inner_consistent`函数必须小心对待这样的内部元组。 有关更多信息,请参见[Section 56.3.3](#calibre_link-553)。 只有当`config`函数设置`longValuesOK`为true,并且提供了大于一页面的输入值时， `picksplit`才可以被应用到单个叶元组。 在这种情况下操作的要点是剥离前缀并产生一个新的、更短的叶数据值。 这个调用将被反复执行，直到叶数据已经短到可以放到一个被生成的页面上。 有关更多信息,请参见[Section 56.3.1](#calibre_link-552)。 `inner_consistent` 返回树搜索需要继续访问的节点集合(分支)。 函数的SQL声明必须看起来像这样: ``` CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ... ``` 第一个参数是一个指向C结构体`spgInnerConsistentIn`的指针,包含函数的输入数据。 第二个参数是一个指向C结构体`spgInnerConsistentOut`的指针,该函数必须填充结果数据到里面。 ``` typedef struct spgInnerConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ int nkeys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ 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 */ } spgInnerConsistentOut; ``` 长度为`nkeys`的`scankeys`数组描述了索引搜索条件。 这些条件以"AND"联接在一起，即，只有满足所有条件的索引条目才能匹配这个查询。 (注意,如果`nkeys`为0意味着所有索引条目都满足查询。) 通常这个函数只关心每个数组项目的`sk_strategy`和`sk_argument`字段,它们分别给出了可索引的操作符和比较值。 特别是没有必要看`sk_flags`以检查比较值是否为NULL,因为SP-GiST核心代码会过滤掉这样的条件。 `reconstructedValue`是为父元组重建的值；如果在根层级或`inner_consistent`函数在父层级没有提供一个值，它会是0。 `level`是当前内部元组的层级，从0，也就是根的层级，开始计数。 `returnData`为`true`，如果这个查询需要重建数据的话；只有`config`函数声明了`canReturnData`时，才有可能是这样。 `allTheSame`是true，如果当前内部元组标记"all-the-same";在这种情况下的所有节点具有相同的标签(如果有的话),所以要么全部要么没有一个匹配这个查询(参见[Section 56.3.3](#calibre_link-553))。 如果当前内部元组包含前缀，`hasPrefix`为true。 此时，`prefixDatum`是前缀值。 `nNodes`是内部元组中包含子节点的数量，`nodeLabels`是它们的标签值的数组,或者是NULL如果节点没有标签。 `nNodes`必须被设置为搜索需要访问的子节点的数量, 并且`nodeNumbers`必须被设置的它们的索引的数组。 如果操作符类跟踪层级,设置`levelAdds`为向下访问到每个节点时层级增量的数组。 (通常这些增量对所有节点是相同的,但这并不一定是这样,所以使用一个数组)。 如果需要重建数据值,设置`reconstructedValues`为每个要访问的子节点的重建值的数组;否则,保持`reconstructedValues`为NULL。 注意,`inner_consistent`函数负责分配(palloc) `nodeNumbers`, `levelAdds`和`reconstructedValues`数组。 `leaf_consistent` 如果叶元组满足查询返回true。 函数的SQL声明必须看起来像这样: ``` CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ... ``` 第一个参数是一个指向C结构体`spgLeafConsistentIn`的指针,包含函数的输入数据。 第二个参数是一个指向C结构体`spgLeafConsistentOut`的指针,该函数必须填充结果数据到里面。 ``` typedef struct spgLeafConsistentIn { ScanKey scankeys; /* array of operators and comparison values */ int nkeys; /* length of array */ Datum reconstructedValue; /* value reconstructed at parent */ 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`是父元组重建的值；如果在根层级或`inner_consistent`函数在父层级没有提供一个值，它会是0。 `level`是当前叶元组的层级，从0，也就是根的层级，开始计数。 `returnData`为`true`，如果这个查询需要重建数据的话；只有`config`函数声明了`canReturnData`时，才有可能是这样。 `leafDatum`是存储在当前叶元组中的键值。 如果这个叶元组匹配查询，这个函数必须返回`true`,否则返回`false`。 在`true`的情况下,如果`returnData`是`true`， 那么`leafValue`必须被设置为最初提供的这个叶元组索引的值。 如果匹配是不确定的,`recheck`也被设置为`true`，因此操作符必须被重新应用到实际的堆元组上以验证匹配。 所有SP-GiST支持方法通常在一个短期的内存上下文中被调用;也就是说, 在处理每一个元组后`CurrentMemoryContext`将被重置。 因此不太需要担心地去pfree你palloc出来的所有东西。 （`config`方法是一个例外:它应该尽量避免内存泄露。 但通常`config`方法除了把常数赋值到传递过来的结构体中外，其它什么也不需要做。） 如果被索引列是一个collatable数据类型,该索引排序规则将被传递给所有的支持方法,使用标准的`PG_GET_COLLATION()` 机制。