Redrock Postgres 搜索 英文
版本: 9.3 / 9.4 / 9.5 / 9.6 / 10 / 11 / 12 / 13 / 14 / 15 / 16

69.4. 实现 #

69.4.1. SP-GiST 限制
69.4.2. 没有节点标签的 SP-GiST
69.4.3. 完全相同 内部元组

本节涵盖实现细节和其他技巧,这些技巧对 SP-GiST 运算符类的实现者很有用。

69.4.1. SP-GiST 限制 #

各个叶元组和内部元组必须适合单个索引页(默认 8kB)。因此,在索引可变长度数据类型的值时,只能通过诸如基数树之类的办法来支持长值,其中树的每一层都包含一个足够短的前缀以适合页面,并且最终的叶层包含一个后缀也足够短以适合页面。运算符类应将 longValuesOK 设置为 true,仅当它准备安排这样做时。否则,SP-GiST 内核将拒绝任何索引过大而无法放入索引页的值的请求。

同样,内部元组不会增长到太大而无法放入索引页,这是操作符类的责任;这限制了可以在一个内部元组中使用的子节点的数量,以及前缀值的最大大小。

另一个限制是,当内部元组的节点指向一组叶元组时,这些元组必须全部位于同一索引页中。(这是一个设计决策,目的是减少寻址并节省将此类元组链接在一起的链接中的空间。)如果叶元组集增长到太大而无法放入一个页面,则会执行拆分并插入一个中间内部元组。要解决此问题,新的内部元组必须将叶值集分成多个节点组。如果操作符类的picksplit函数无法做到这一点,则SP-GiST核心将诉诸第 69.4.3 节中描述的非常规措施。

longValuesOK为 true 时,预计SP-GiST树的连续层级会将越来越多的信息吸收进内部元组的前缀和节点标签中,从而使所需的叶数据越来越小,最终可以放入一个页面中。为了防止操作符类中的错误导致无限插入循环,如果叶数据在十个choose方法调用周期内没有变小,SP-GiST核心将引发错误。

69.4.2. 没有节点标签的 SP-GiST #

一些树算法为每个内部元组使用一组固定的节点;例如,在四叉树中,总有恰好四个节点对应于内部元组质心点周围的四个象限。在这种情况下,代码通常按数字处理节点,并且不需要显式节点标签。为了抑制节点标签(从而节省一些空间),picksplit函数可以为nodeLabels数组返回 NULL,同样,choose函数可以在spgSplitTuple操作期间为prefixNodeLabels数组返回 NULL。这又会导致在后续对chooseinner_consistent的调用期间nodeLabels为 NULL。原则上,节点标签可以用于一些内部元组,而对于同一索引中的其他内部元组则可以省略。

当使用具有未标记节点的内部元组时,choose 返回 spgAddNode 是一个错误,因为在这种情况下,节点集应该固定。

69.4.3. All-the-Same 内部元组 #

picksplit 无法将提供的叶值分成至少两类节点时,SP-GiST 核心可以覆盖操作符类的 picksplit 函数的结果。发生这种情况时,将创建新的内部元组,其中包含多个节点,每个节点具有 picksplit 提供给它使用的单个节点的相同标签(如果有),并且叶值在这些等效节点之间随机分配。在内部元组上设置 allTheSame 标志,以警告 chooseinner_consistent 函数,该元组没有它们可能预期的节点集。

在处理 allTheSame 元组时,choosespgMatchNode 结果被解释为新值可以分配给任何等效节点;核心代码将忽略提供的 nodeN 值,并随机进入其中一个节点(以保持树的平衡)。choose 返回 spgAddNode 是一个错误,因为这会使节点不再全部等效;如果要插入的值与现有节点不匹配,则必须使用 spgSplitTuple 操作。

在处理 allTheSame 元组时,inner_consistent 函数应将所有或没有节点作为继续索引搜索的目标返回,因为它们都是等效的。这可能需要或不需要任何特殊情况代码,具体取决于 inner_consistent 函数通常对节点的含义假设多少。