57.4. 实现 #
本节介绍实现细节以及其他一些对 SP-GiST 操作符类实现者有用的技巧。
57.4.1. SP-GiST 限制 #
单个叶子元组和内部元组都必须能放入单个索引页中(默认 8KB)。因此,在对变长数据类型的值建立索引时,只有像基数树这类方法才能支持长值:树的每一层都包含足够短、能放进一页的前缀,而最终叶子层也包含足够短、能放进一页的后缀。只有当操作符类准备好保证这一点时,才应将
longValuesOK 设为 TRUE。否则,SP-GiST 核心会拒绝为过大、无法放入索引页的值建立索引的请求。
同样,确保内部元组不会增长到大得无法放入索引页,也是操作符类的责任;这限制了单个内部元组中可使用的子结点数量,以及前缀值的最大大小。
另一个限制是,当内部元组的某个结点指向一组叶子元组时,这些元组必须全部位于同一个索引页上。(这是一个设计决策,目的是减少寻道,并节省把这类元组链接成链时所需链接占用的空间。)如果一组叶子元组增长到单页无法容纳,就会执行拆分并插入一个中间内部元组。要解决这个问题,新的内部元组必须把叶子值集合划分成多个结点组。如果操作符类的
picksplit 函数做不到这一点,SP-GiST 核心就会诉诸第 57.4.3 节中描述的非常规措施。
57.4.2. 无结点标签的 SP-GiST #
某些树算法对每个内部元组都使用固定的一组结点;例如在四叉树中,总是恰好有四个结点,对应于内部元组中心点周围的四个象限。在这种情况下,代码通常按编号处理结点,因此不需要显式的结点标签。为了省略结点标签(从而节省一些空间),picksplit 函数可以为
nodeLabels 数组返回 NULL。随后对
choose 和 inner_consistent
的调用中,nodeLabels 也将为 NULL。原则上,同一个索引中可以对某些内部元组使用结点标签,而对另一些省略。
当处理具有无标签结点的内部元组时,choose 返回
spgAddNode 是错误的,因为在这种情况下结点集合应被视为固定不变。另外,spgSplitTuple 动作中没有生成无标签结点的规定,因为预期随后还需要执行
spgAddNode 动作。
57.4.3. “全部相同”的内部元组 #
当 picksplit 无法把提供的叶子值划分为至少两个结点类别时,SP-GiST 核心可以覆盖操作符类
picksplit 函数的结果。在这种情况下,会创建一个新的内部元组,其中有多个结点,而每个结点都具有相同的标签(如果有);这个标签就是 picksplit 给它唯一使用的那个结点分配的标签。叶子值会被随机分配到这些等价结点中。该内部元组会设置
allTheSame 标志,用来提醒
choose 和 inner_consistent
函数:这个元组的结点集合并不是它们通常会预期的那种。
在处理 allTheSame 元组时,choose 返回 spgMatchNode
表示新值可以分配给任意一个等价结点;核心代码会忽略给出的
nodeN 值,并随机下降到其中一个结点(以保持树的平衡)。choose 返回
spgAddNode 则属于错误,因为那会使结点不再全部等价;如果待插入的值与现有结点不匹配,就必须使用
spgSplitTuple 动作。
在处理 allTheSame 元组时,inner_consistent 函数应当要么把全部结点返回为继续索引搜索的目标,要么一个也不返回,因为它们都是等价的。这是否需要编写特殊情况代码,取决于 inner_consistent 函数平常对这些结点含义做了多大程度的假定。