無料スクリプト配布のPHP.TO   PHPの実用的なtips PHPマニュアル MySQLマニュアル Apacheマニュアル PostgreSQLマニュアル マニュアル検索    

56.3. 実装

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

56.3.1. SP-GiSTの制限

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

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

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

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

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

ラベルのないノードを持つ内部タプルを処理するときに、 choose spgAddNode を返すのはエラーです。というのは、この場合、ノードの集合は固定されていると想定されるからです。 また、 spgSplitTuple のアクションでラベルのないノードを生成する用意はありません。というのは、 spgAddNode のアクションも必要になると考えられるからです。

56.3.3. "All-the-same" 内部タプル

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

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

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


powered by SEO.CUG.NET