60.3. 可扩展性

返回关于索引实现的静态信息，包括前缀的数据类型的OID以及结点标签数据类型。

这个函数的SQL声明必须看起来像这样：

CREATE FUNCTION my_config(internal, internal) RETURNS void ...

第一个参数是一个指向spgConfigIn C 结构的指针，包含该函数的输入数据。第二个参数是一个指向spgConfigOut C 结构的指针，函数必须将结果数据填充在其中。

typedef struct spgConfigIn
{
    Oid         attType;        /* 要被索引的数据类型 */
} spgConfigIn;

typedef struct spgConfigOut
{
    Oid         prefixType;     /* 内部元组前缀的数据类型 */
    Oid         labelType;      /* 内部元组结点标签的数据类型 */
    bool        canReturnData;  /* 操作符类能重构原始数据 */
    bool        longValuesOK;   /* 操作符类能处理值 > 1 页 */
} spgConfigOut;

为了支持多态的索引操作符类，attType要被传入；对于普通固定数据类型的操作符类，它将总是取相同的值，因此可以被忽略。

对于不使用前缀的操作符类，prefixType可以被设置为VOIDOID。同样，对于不使用结点标签的操作符类，labelType可以被设置为VOIDOID。如果操作符类能够重构出原来提供的被索引值，则canReturnData应该被设置为真。只有当attType是变长的并且操作符类能够将长值通过反复的添加后缀分段时，longValuesOK才应当被设置为真（参见Section 60.4.1）。

为将一个新值插入到一个内部元组选择一种方法。

该函数的SQL声明必须看起来像这样：

CREATE FUNCTION my_choose(internal, internal) RETURNS void ...

第一个参数是一个指向spgChooseIn C 结构的指针，包含该函数的输入数据。第二个参数是一个指向spgChooseOut C 结构的指针，函数必须将结果数据填充在其中。

typedef struct spgChooseIn
{
    Datum       datum;          /* 要被索引的原始数据 */
    Datum       leafDatum;      /* 要被存储在叶子中的当前数据 */
    int         level;          /* 当前层（从零计数） */

    /* 来自当前内部元组的数据 */
    bool        allTheSame;     /* tuple is marked all-the-same? */
    bool        hasPrefix;      /* 元组有一个前缀？ */
    Datum       prefixDatum;    /* 如果有，前缀值 */
    int         nNodes;         /* 内部元组中的结点数目 */
    Datum      *nodeLabels;     /* 结点标签值（如果没有为 NULL） */
} spgChooseIn;

typedef enum spgChooseResultType
{
    spgMatchNode = 1,           /* 下降到现有结点 */
    spgAddNode,                 /* 向内部元组增加一个结点 */
    spgSplitTuple               /* 划分内部元组（修改它的前缀） */
} spgChooseResultType;

typedef struct spgChooseOut
{
    spgChooseResultType resultType;     /* 动作代码，见上文 */
    union
    {
        struct                  /* 用于spgMatchNode的结果 */
        {
            int         nodeN;      /* 下降到这个结点（索引从 0 开始） */
            int         levelAdd;   /* 这次匹配增加的层 */
            Datum       restDatum;  /* 新叶数据 */
        }           matchNode;
        struct                  /* 用于spgAddNode的结果 */
        {
            Datum       nodeLabel;  /* 新结点的标签 */
            int         nodeN;      /* 在哪里插入它（索引从 0 开始） */
        }           addNode;
        struct                  /* 用于spgSplitTuple的结果 */
        {
            /* 来自有一个结点的新内部元组的信息 */
            bool        prefixHasPrefix;    /* 元组能有前缀吗？ */
            Datum       prefixPrefixDatum;  /* 如果有，前缀值 */
            Datum       nodeLabel;          /* 结点的标签 */

            /* 来自放有所有旧结点的新下层内部元组的信息 */
            bool        postfixHasPrefix;   /* 元组能有前缀吗？ */
            Datum       postfixPrefixDatum; /* 如果有，前缀值 */
        }           splitTuple;
    }           result;
} spgChooseOut;

datum是将被插入到索引中的原始数据。leafDatum最初和datum一样，但是如果choose或picksplit改变了它，那么位于较低层的leafDatum值就会有所改变。当插入搜索到达一个叶子页，leafDatum的当前值就会被存储在新创建的叶子元组中。level是当前内部元组的层次，根层是 0 。如果当前内部元组被标记为包含多个等价节点（见Section 60.4.3），allTheSame为真。如果当前内部元组有一个前缀，hasPrefix为真，如果这样，prefixDatum为前缀值。nNodes是包含在内部元组中子结点的数量，并且nodeLabels是这些子结点的标签值的数组，如果没有标签则为 NULL。

The choose函数能决定新值是匹配一个现有子结点，或是必须增加一个新的子节点，亦或是新值和元组的前缀不一致并且因此该内部元组必须被分裂来创建限制性更低的前缀。

如果新值匹配一个现有的子结点，将resultType设置为spgMatchNode。将nodeN设置为该结点在结点数组中的索引（从零开始）。将levelAdd设置为传到该结点导致的level增加，或者在操作符类不使用层数时将它置为零。如果操作符类没有把数据从一层修改到下一层，将restDatum设置为等于datum，否则将它设置为在下一层用作leafDatum的被修改后的值。

如果必须增加一个新的子结点，将resultType设置为spgAddNode。将nodeLabel设置为在新结点中使用的标签，并将nodeN设置为插入该结点的位置在结点数组中的索引（从零开始）。在结点被增加之后，choose函数将被再次调用并使用修改后的内部元组，那时将会导致一个spgMatchNode结果。

如果新值和元组的前缀不一致，将resultType设置为spgSplitTuple。这个动作将所有现有的结点移动到一个新的下层内部元组，并且将现有的内部元组用一个新元组替换，该元组只有一个结点链接到那个新的下层内部元组。将prefixHasPrefix设置为指示新的上层元组是否具有一个前缀，并且在如果有前缀时设置prefixPrefixDatum为前缀值。这个新的前缀值必须比原来的值要足够宽松以便能够接受将被索引的新值，并且它不能比原来的前缀长。将nodeLabel设置为要用于指向新下层内部元组的结点的标签。将postfixHasPrefix设置为指示新下层内部元组是否具有一个前缀，并且如果有前缀则设置postfixPrefixDatum为前缀值。这两个前缀和额外的标签的组合必须和原来的前缀具有相同的含义，因为我们没有机会修改被移动到新下层元组的结点标签，也没有机会改变任何子索引项。在结点被分裂后，choose函数将被再次调用并使用替换内部元组。该次调用通常会导致一个spgAddNode结果，因为有可能在分裂步骤中增加的节点标签不能匹配新值；那么这样会有第三次调用最终返回spgMatchNode并且允许插入下降到叶子层。

决定如何在一组叶子元组上创建一个新的内部元组。

该函数的SQL声明必须看起来像这样：

CREATE FUNCTION my_picksplit(internal, internal) RETURNS void ...

第一个参数是一个指向spgPickSplitIn C 结构的指针，包含该函数的输入数据。第二个参数是一个指向spgPickSplitOut C 结构的指针，函数必须将结果数据填充在其中。

typedef struct spgPickSplitIn
{
    int         nTuples;        /* 叶子元组的数量 */
    Datum      *datums;         /* 它们的数据（长度为 nTuples 的数组） */
    int         level;          /* 当前层次（从零开始计） */
} spgPickSplitIn;

typedef struct spgPickSplitOut
{
    bool        hasPrefix;      /* 新内部元组应该有一个前缀吗？ */
    Datum       prefixDatum;    /* 如果有，前缀值 */

    int         nNodes;         /* 新内部元组的结点数 */
    Datum      *nodeLabels;     /* 它们的标签（没有标签则为NULL） */

    int        *mapTuplesToNodes;   /* 每一个叶子元组的结点索引 */
    Datum      *leafTupleDatums;    /* 存储在每一个新叶子元组中的数据 */
} spgPickSplitOut;

nTuples是所提供的叶子元组的数量。 datums是它们的数据值的数组。 level是所有叶子元组共有的当前层次，它将成为新内部元组的层次。

将hasPrefix设置为指示新内部元组是否应该有前缀，并且如果有前缀则将prefixDatum设置成前缀值。将nNodes设置为新内部元组将包含的结点数目，并且将nodeLabels设置为它们的标签值的数组（如果结点不要求标签，将nodeLabels设置为 NULL，详见Section 60.4.2）。将mapTuplesToNodes设置为一个数组，该数组告诉每一个叶子元组应该被赋予的结点的索引（从零开始）。将leafTupleDatums设置为由将要被存储在新叶子元组中的值构成的一个数组（如果操作符类不将数据从一层修改到下一层，这些值将和输入的datums相同）。注意picksplit函数负责为nodeLabels、mapTuplesToNodes和leafTupleDatums数组进行 palloc。

如果提供了多于一个叶子元组，picksplit被寄望于将它们分类到多余一个结点中；否则不可能将叶子元组划分到多个页面，这也是这个操作的终极目的。因此，如果picksplit函数结束时把所有叶子元组放在同一个结点中，核心SP-GiST代码将覆盖该决定，并且生成一个内部元组，将叶子元组随机分配到多个不同标签的结点。这样一个元组被标记为allTheSame来表示发生了这种情况。choose和inner_consistent函数必须对这样的内部元组采取合适的处理。详见Section 60.4.3。

picksplit只能在一种情况下被应用在单独一个叶子元组上，这种情况是config函数将longValuesOK设置为真并且提供了一个长于一页的输入。在这种情况中，该操作的要点是剥离一个前缀并且产生一个新的、较短的叶子数据值。这种调用将被重复直到产生一个足够短能够放入到一页的叶子数据。详见Section 60.4.1。

在树搜索过程中返回一组要追求的结点（分支）。

该函数的SQL声明必须看起来像这样：

CREATE FUNCTION my_inner_consistent(internal, internal) RETURNS void ...

第一个参数是一个指向spgInnerConsistentIn C 结构的指针，包含该函数的输入数据。第二个参数是一个指向spgInnerConsistentOut C 结构的指针，函数必须将结果数据填充在其中。

typedef struct spgInnerConsistentIn
{
    ScanKey     scankeys;       /* 操作符和比较值的数组 */
    int         nkeys;          /* 数组的长度 */

    Datum       reconstructedValue;     /* 在父结点中的重构值 */
    int         level;          /* 当前层次（从零开始计） */
    bool        returnData;     /* 是否必须返回原始数据？ */

    /* 来自当前内元组的数据 */
    bool        allTheSame;     /* 元组被标记为完全相同？ */
    bool        hasPrefix;      /* 元组有前缀？ */
    Datum       prefixDatum;    /* 如果有，前缀值 */
    int         nNodes;         /* 内元组中的结点数 */
    Datum      *nodeLabels;     /* 结点标签值（没有就是 NULL） */
} spgInnerConsistentIn;

typedef struct spgInnerConsistentOut
{
    int         nNodes;         /* 要被访问的子结点数 */
    int        *nodeNumbers;    /* 它们在结点数组中的索引 */
    int        *levelAdds;      /* 为每个子结点要增加的层数 */
    Datum      *reconstructedValues;    /* 相关的重构值 */
} spgInnerConsistentOut;

长度为nkeys的数组scankeys描述了 索引搜索条件。这些条件用 AND 组合 — 只对满足所有条件的索引 项感兴趣（注意，nkeys = 0 表示所有索引项满足该查 询）。通常一致函数只关心每个数组项的sk_strategy和 sk_argument，它们分别给出了可索引操作符和比较值。 特别要说明的是，没有必要去检查sk_flags来看比较值 是否为 NULL，因为 SP-GiST 的核心代码会过滤这样的条件。 reconstructedValue是用于父元组的重构值，在根层时 或者如果inner_consistent函数没有在父层提供一个值时， 它为(Datum) 0。level是当前内元组层次， 根层是 0。如果这个查询要求重构的数据，returnData是 true。如果config断言 canReturnData，returnData只会是 true。如果当前的内元组被标记为"完全一样"， 那么allTheSame为真。在这种情况下，所有的结点都具有 相同的标签（如果有），而且它们要么全部匹配该查询，要么一个都不匹配查 询（见Section 60.4.3）。如果当前内元组包含一个 前缀，则hasPrefix为真。如果这样， prefixDatum就是该前缀的值。nNodes 是包含在内元组中的子结点的数量，nodeLabels是它们的 标签值的数组。当然如果结点没有标签，这个数组就为 NULL。

nNodes必须被设置为搜索需要访问的子结点数，并且 nodeNumbers必须被设置为子结点索引的数组。如果 操作符类跟踪层次，把levelAdds设置成一个数组，其中 说明了在下降到要被访问的每一个结点时需要增加的层数（通常这些增量对 于所有结点都是相同的，但是并不一定如此，所以需要使用一个数组）。如 果需要值重构，将reconstructedValues设置成要被访问 的每一个子结点的重构值数组。否则让 reconstructedValues为 NULL。注意 inner_consistent函数负责为 nodeNumbers、levelAdds 和 reconstructedValues数组分配空间。

如果一个叶子元组满足一个查询则返回真。

该函数的SQL声明必须看起来像这样：

CREATE FUNCTION my_leaf_consistent(internal, internal) RETURNS bool ...

第一个参数是一个指向spgLeafConsistentIn C 结构的指针，包含该函数的输入数据。第二个参数是一个指向spgLeafConsistentOut C 结构的指针，函数必须将结果数据填充在其中。

typedef struct spgLeafConsistentIn
{
    ScanKey     scankeys;       /* 操作符和比较值的数组 */
    int         nkeys;          /* 数组的长度 */

    Datum       reconstructedValue;     /* 在父结点中的重构值 */
    int         level;          /* 当前层次（从零开始计） */
    bool        returnData;     /* 是否必须返回原始数据？ */

    Datum       leafDatum;      /* 叶子元组中的数据 */
} spgLeafConsistentIn;

typedef struct spgLeafConsistentOut
{
    Datum       leafValue;      /* 重构的原始数据，如果有 */
    bool        recheck;        /* 如果操作符必须被重新检查则设为真 */
} spgLeafConsistentOut;

The array scankeys, of length nkeys, describes the index search condition(s). These conditions are combined with AND — only index entries that satisfy all of them satisfy the query. (Note that nkeys = 0 implies that all index entries satisfy the query.) Usually the consistent function only cares about the sk_strategy and sk_argument fields of each array entry, which respectively give the indexable operator and comparison value. In particular it is not necessary to check sk_flags to see if the comparison value is NULL, because the SP-GiST core code will filter out such conditions. reconstructedValue is the value reconstructed for the parent tuple; it is (Datum) 0 at the root level or if the inner_consistent function did not provide a value at the parent level. level is the current leaf tuple's level, starting at zero for the root level. returnData is true if reconstructed data is required for this query; this will only be so if the config function asserted canReturnData. leafDatum is the key value stored in the current leaf tuple.

The function must return true if the leaf tuple matches the query, or false if not. In the true case, if returnData is true then leafValue must be set to the value originally supplied to be indexed for this leaf tuple. Also, recheck may be set to true if the match is uncertain and so the operator(s) must be re-applied to the actual heap tuple to verify the match.