可扩展性

注意: SP-GiST核心代码会关注空项。尽管SP-GiST索引确实可以存储被索引列中的空值，但这对索引操作符类代码是隐藏的：不会有空索引项或搜索条件会被传递给操作符类方法（我们假定SP-GiST操作符是严格的并且因此无法成功处理空值）。因此这里不会进一步讨论空值。

config

返回关于索引实现的静态信息，包括前缀的数据类型的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才应当被设置为真（参见第 62.4.1 节）。

choose

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

该函数的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 。如果当前内部元组被标记为包含多个等价节点（见第 62.4.3 节），allTheSame为真。如果当前内部元组有一个前缀，hasPrefix为真，如果这样，prefixDatum为前缀值。nNodes是包含在内部元组中子结点的数量，并且nodeLabels是这些子结点的标签值的数组，如果没有标签则为 NULL。

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并且允许插入下降到叶子层。

picksplit

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

该函数的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设置为它们的标签值的数组或者 NULL（如果结点不要求标签）。将mapTuplesToNodes设置为一个数组，该数组告诉每一个叶子元组应该被赋予的结点的索引（从零开始）。将leafTupleDatums设置为由将要被存储在新叶子元组中的值构成的一个数组（如果操作符类不将数据从一层修改到下一层，这些值将和输入的datums相同）。注意picksplit函数负责为nodeLabels、mapTuplesToNodes和leafTupleDatums数组进行 palloc。

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

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

inner_consistent

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

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

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

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

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

    Datum       reconstructedValue;     /* 在父结点中的重构值 */
    void       *traversalValue; /* 操作符类相关的贯穿值 */
    MemoryContext traversalMemoryContext;   /* 把新的贯穿值放在这里 */
    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;    /* 相关的重构值 */
    void      **traversalValues;        /* 操作符类相关的贯穿值 */
} spgInnerConsistentOut;

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

nNodes必须被设置为搜索需要访问的子结点数，并且nodeNumbers必须被设置为子结点索引的数组。如果操作符类跟踪层次，把levelAdds设置成一个数组，其中说明了在下降到要被访问的每一个结点时需要增加的层数（通常这些增量对于所有结点都是相同的，但是并不一定如此，所以需要使用一个数组）。如果需要值重构，将reconstructedValues设置成要被访问的每一个子结点的重构值数组。否则让reconstructedValues为 NULL。如果想要把额外的带外信息（"贯穿值"）向下传递给树搜索的较低层，可以把traversalValues设置成合适的贯穿值的数组，其中每一个元素用于一个要被访问的子节点。如果不需要传递额外的带外信息，则把traversalValues设置为 NULL。注意，inner_consistent函数负责在当前内存上下文中分配nodeNumbers、levelAdds、reconstructedValues和traversalValues数组。不过，任何由traversalValues数组指向的输出贯穿值应该在traversalMemoryContext中分配。每一个贯穿值必须是一个单独分配的块（chunk）。

leaf_consistent

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

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

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

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

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

    void       *traversalValue; /* 操作符类相关的贯穿值 */
    Datum       reconstructedValue;     /* 在父结点中的重构值 */
    int         level;          /* 当前层次（从零开始计） */
    bool        returnData;     /* 是否必须返回原始数据？ */

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

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

长度为nkeys的数组scankeys描述了索引搜索条件。这些条件用 AND 组合在一起 — 只有满足所有条件的索引项才满足该查询（注意nkeys = 0 表示所有的索引项都满足查询）。通常 consistent 函数值关注每一个数组项的sk_strategy和sk_argument域，它们分别给出了可索引操作符和比较值。特别是它无需检查sk_flags来检查比较值是否为 NULL，因为 SP-GiST 核心代码将过滤掉这类条件。reconstructedValue是为父元组重构的值，在根层或者当inner_consistent没有提供父层上的值时，它是(Datum) 0。traversalValue是任意贯穿数据的指针，该数据由父索引元组上的上一次inner_consistent调用传递下来，在根层上这个指针为 NULL。level是当前的叶子元组所在的层次，根层为零。如果这个查询要求重构的数据，则returnData为true。只有在config函数主张了canReturnData时才会如此。leafDatum是存储在当前叶子元组中的键值。

如果叶子元组匹配查询，则该函数必须返回true，否则返回false。在返回true的情况中，如果returnData为true，则leafValue必须被设置为最初为构建这个叶子元组提供的值。还有，如果匹配是不确定的并且操作符必须被重新应用在实际堆元组上验证匹配，则recheck会被设置为true。