62.4. 实现

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

62.4.1. SP-GiST 限制

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

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

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

62.4.2. 无节点标签的 SP-GiST

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

在处理具有无标签节点的内部元组时,让choose返回spgAddNode是一种错误,因为该节点集合在这种情况下被假定为固定的集合。还有,没有规定要在spgSplitTuple动作中生成一个无标签节点,因为那样也将需要一个spgAddNode动作。

62.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函数对这些节点含义的假定程度,这可能会也可能不会要求任何处理特殊情况的代码。