受支持版本: 16 / 15 / 14

64.4. 实现 #

本节介绍实现细节以及其他一些对 SP-GiST 操作符类实 现者有用的技巧。

64.4.1. SP-GiST 限制 #

单个叶子元组和内部元组都必须能放入单个索引页中(默认 8kB)。因此,在对 变长数据类型的值建立索引时,只有像基数树这类方法才能支持长值:树的 每一层都包含足够短、能放进一页的前缀,而最终叶子层也包含足够短、能放进 一页的后缀。只有当操作符类准备好保证这一点时,才应将 longValuesOK 设为 true。否则, SP-GiST 核心会拒绝为过大、无法放入索引页的值建立 索引的请求。

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

另一个限制是,当内部元组的某个结点指向一组叶子元组时,这些元组必须全部 位于同一个索引页上。(这是一个设计决策,目的是减少寻道,并节省把这类元 组链接成链时所需链接占用的空间。)如果一组叶子元组增长到单页无法容纳,就会执行拆分 并插入一个中间内部元组。要解决这个问题,新的内部元组必须 把叶子值集合划分成多个结点组。如果操作符类的 picksplit 函数做不到这一点, SP-GiST 核心就会诉诸 Section 64.4.3 中描述的非常规措施。

longValuesOK 为真时,预期 SP-GiST 树的连续各层会把越来越多的信息吸收到内部 元组的前缀和结点标签中,从而使所需的叶子 datum 越来越小,最终能够放入 一页。为了防止操作符类中的缺陷导致插入陷入无限循环,如果在连续十次调 用 choose 方法之后叶子 datum 仍没有变小, SP-GiST 核心就会报错。

64.4.2. 无结点标签的 SP-GiST #

某些树算法对每个内部元组都使用固定的一组结点;例如在四叉树中,总是恰好 有四个结点,对应于内部元组中心点周围的四个象限。在这种情况下,代码通常 按编号处理结点,因此不需要显式的结点标签。为了省略结点标签(从而节省一 些空间),picksplit 函数可以为 nodeLabels 数组返回 NULL,同样在执行 spgSplitTuple 动作期间, choose 函数也可以为 prefixNodeLabels 数组返回 NULL。随后对 chooseinner_consistent 的调用中,nodeLabels 也将为 NULL。原则上, 同一个索引中可以对某些内部元组使用结点标签,而对另一些省略。

当处理具有无标签结点的内部元组时,choose 返回 spgAddNode 是错误的,因为在这种情况下结点集合应被 视为固定不变。

64.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 函数平常对这些结 点含义做了多大程度的假定。

提交更正

如果您发现文档中有不正确的内容、与您使用特定功能的经验不符或需要进一步说明,请使用此表单来报告文档问题。