他のバージョンの文書 16 | 15 | 14 | 13 | 12 | 11 | 10 | 9.6 | 9.5 | 9.4 | 9.3 | 9.2 | 9.1 | 9.0 | 8.4 | 8.3 | 8.2 | 8.1 | 8.0 | 7.4 | 7.3 | 7.2

69.4. 実装 #

この節では、SP-GiSTの演算子クラスを実装する人にとって知っていると役に立つ、実装についての詳細とその他の秘訣について説明します。

69.4.1. SP-GiSTの制限 #

それぞれのリーフタプルおよび内部タプルは1つのインデックスページ内(デフォルトで8kB)に収まらなければなりません。 従って、可変長のデータ型の値をインデックス付けするときは、長い値は基数木のようなメソッドによってのみサポートされます。つまり、ツリーのそれぞれのレベルではページに収まる短さの接頭辞を含み、最後のリーフレベルでは、やはりページに収まる短さの接尾辞を含む、というようなものです。 このようなことが発生する場合の対応の準備ができている場合のみ、演算子クラスはlongValuesOKを真にセットするべきです。 そうでなければ、SP-GiSTのコアは、インデックスページに収めるには大きすぎる値についてのインデックス付け要求を拒絶します。

同様に、内部タプルが大きくなりすぎてインデックスページに収まらない、ということにならないようにするのは、演算子クラスの責任です。 これにより、1つの内部タプルで使うことができる子ノードの数、および接頭辞の値の最大サイズが制限されます。

内部タプルのノードがリーフタプルの集合を指しているとき、それらのタプルはすべて同じインデックスページ内になければならない、という制限もあります。 (これは、シークの回数を減らし、そのようなタプルを一つにつなげるリンクに必要なスペースを減らす、という設計上の決定によるものです。) リーフタプルの集合が大きくなって1ページに収まらなくなると、分割が実行され、中間の内部タプルが挿入されます。 これで問題を解決するためには、新しい内部タプルは、リーフの値の集合を2つ以上のノードのグループに分割しなければなりません。 演算子クラスのpicksplit関数がそれをするのに失敗したときは、SP-GiSTのコアは、69.4.3に記述されている特別な手段に頼ることになります。

longValuesOKが真であれば、SP-GiSTツリーの後続のレベルは、より多くの情報を接頭辞と内部タプルのノードラベルへと吸収し、要求されるリーフデータより小さくして、最終的には1ページに収まるようになることが期待されます。 演算子クラスのバグが無限の挿入ループを引き起こすのを防ぐために、chooseメソッドの呼び出しの10サイクル以内でリーフデータが少しも小さくならなければ、SP-GiSTコアはエラーを発生します。

69.4.2. ノードラベルのないSP-GiST #

木構造のアルゴリズムには、それぞれの内部タプルに対して固定された集合のノードを使うものがあります。 例えば四分木では、内部タプルの中心点の周りの4つの象限に対応するちょうど4つのノードが必ずあります。 このような場合、コードは典型的には数字を使ったノードで動作し、明示的なノードラベルは必要ありません。 ノードラベルを使わない(そしてそれによりいくらかのスペースを節約する)ために、picksplit関数はnodeLabels配列としてNULLを返すことができ、同様にchoose関数はspgSplitTupleアクションの間prefixNodeLabels配列としてNULLを返すことができます。 この結果、その後のchoose関数およびinner_consistent関数の呼び出しにおいてもnodeLabelsはNULLになります。 原則として、ノードラベルは同じインデックス中の一部の内部タプルに使い、他の内部タプルには省略する、ということができます。

ラベルのないノードを持つ内部タプルを処理するときに、choosespgAddNodeを返すのはエラーです。というのは、この場合、ノードの集合は固定されていると想定されるからです。

69.4.3. All-the-Same内部タプル #

picksplitが入力のリーフ値を少なくとも2つのノード分類に分割できなかった場合、SP-GiSTのコアは演算子クラスのpicksplit関数の結果を無効にすることがあります。 これが起きると、複数のノードを持つ新しい内部タプルが作成されます。それぞれのノードは、picksplitが一つのノードに付与したもの(あれば)と同じラベルを持ち、リーフ値はこれらの等価なノード間でランダムに分割されます。 内部タプルにはallTheSameのフラグがセットされ、choose関数およびinner_consistent関数に対し、そのタプルが通常期待されるようなノードの集合を持っていないことを警告します。

allTheSameの処理において、choosespgMatchNodeという結果は、新しい値は等価なノードのどれに割り当てられても良い、という意味に解釈されます。 コアのコードは入力されたnodeNの値を無視し、(ツリーの平衡を保つために)ノードの1つにランダムに降りていきます。 choosespgAddNodeを返すのはエラーです。というのは、そうするとすべてのノードが等価ではなくなるからです。 挿入する値が既存のノードとマッチしない時は、spgSplitTupleのアクションを使わなければなりません。

allTheSameのタプルの処理において、すべてのノードは等価なので、inner_consistent関数は、インデックス検索を続けるためのターゲットとして、すべてのノードを返すか、ノードを1つも返さないかのいずれかであるべきです。 このために、特殊ケースを扱うコードが必要になるかもしれませんし、必要ないかもしれません。それは、inner_consistent関数が、通常、ノードの意味についてどの程度のことを仮定しているかに依存します。