66.4. 实现

66.4.1. SP-GiST 限制
66.4.2. 无节点标签的 SP-GiST
66.4.3. All-the-Same内部元组

这一节覆盖了实现细节以及SP-GiST操作符类的实现者需要知道的有用的技巧。

66.4.1. SP-GiST 限制

单独的叶子节点和内部节点必须能适合一个单一的索引页面(默认为 8kB)。因此,当索引值是一种变长数据类型时(长值只能由如 radix 树的方法所支持),树的每一层包含的前缀都足够短以适合一个页面,并且最终的叶子层包括的后缀也足够短以适合一个页面。如果操作符类准备好做这种事情,它应该将longValuesOK设置为true。否则,SP-GiST核心将拒绝任何要索引超过一个所以页面长度的值的请求。

同样,操作符类应该负责不要让内部元组增长到无法放在一个索引页面中。这限制了能在一个内部元组中使用的子节点的数目,以及一个前缀值的最大尺寸。

另一个限制是,当一个内部元组的节点指向一组叶子元组时,这些元组必须都在同一个索引页面中(这种设计是为了减少在这类元组构成链中进行定位的时间并且节省空间)。如果叶子元组集合增长到无法放在一个页面中,将执行一次分裂并且插入一个中间的内部元组。为此,新的内部元组必须把叶子值的集合划分成多于一个节点分组。如果操作符类的picksplit函数无法做到这一点,SP-GiST核心只能求助于第 66.4.3 节中所介绍的额外措施。

longValuesOK为真,可以预期SP-GiST树的连续级别将吸收越来越多的信息到内部元组的前缀和节点标签中,使得所需的叶数据越来越小,这样最终就能放在一页上了。 为了防止从导致无限插入循环的操作符类中的错误,SP-GiST内核将抛出一个错误,如果choose方法调用的10个周期内叶数据没有变得更小。

66.4.2. 无节点标签的 SP-GiST

某些树算法对每个内部元组都使用一种固定的节点集合。例如,在一个四叉树中总是正好有四个节点对应于围绕内部节点中心点的四个象限。在这种情况下,代码总是通过编号来处理节点,而不需要显式的节点标签。要抑制节点标签(因而节省一些空间),picksplit函数可以为nodeLabels数组返回NULL,同样choose函数可以在一个spgSplitTuple动作期间为prefixNodeLabels数组返回NULL。这将会导致后续对chooseinner_consistent调用时nodeLabels也为 NULL。原则上,可以为同一个索引中的某些内部元组使用节点标签而对其他内部节点省略节点标签。

在处理具有无标签节点的内部元组时,让choose返回spgAddNode是一种错误,因为该节点集合在这种情况下被假定为固定的集合。

66.4.3. All-the-Same内部元组

picksplit无法把提供的叶子值划分成至少两个节点分类,SP-GiST核心能推翻操作符类的picksplit函数的结果。在发生这种情况时,会创建一个新的内部元组,其中有多个节点,每一个节点都有相同的标签(如果有标签),标签是由picksplit之前给一个节点用的,并且叶子值会被随机地划分给这些等效的节点中。该内部元组上会设置allTheSame标志以警告chooseinner_consistent函数该元组不具有它们所期望的节点集合。

在处理allTheSame元组时,choose函数的结果spgMatchNode会被解释为新值可以被赋值给任一等价的节点。核心代码将忽略提供的nodeN值并且随机地下降到其中一个节点中(以便保持树平衡)。对choose来说,返回spgAddNode是一种错误,因为那会让节点不全部等效。如果要被插入的值不匹配现有的节点,则必须使用spgSplitTuple动作。

在处理allTheSame元组时,为了继续索引搜索,inner_consistent函数应该返回全部节点或者不返回节点作为目标,因为这些节点都是等效的。根据inner_consistent函数对这些节点含义的假定程度,这可能会也可能不会要求任何处理特殊情况的代码。