他のバージョンの文書 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

63.1. はじめに

SP-GiSTは、空間分割された(Space-Partitioned)GiSTを短縮した語です。 SP-GiSTは分割された探索木をサポートし、四分木、kd木、基数木(トライ木)など広範にわたる様々な非平衡データ構造の開発を可能にします。 これらの構造に共通の特徴は、それらが探索空間を繰り返し小さな領域に分割し、その領域の大きさが必ずしも等しくない、ということです。 分割規則によく適合した検索は非常に高速になります。

これらのよく使われるデータ構造は、元々はメモリ内での利用のために開発されたものでした。 主記憶上では、それらは通常、ポインタにより接続され、動的に割り当てられるノードの集合として設計されます。 このようなポインタのチェーンは長くなりがちで、非常に多くのディスクアクセスが必要となるため、ディスク上に直接格納するには適しません。 これとは反対に、ディスクベースのデータ構造は、I/Oを最小化する、大きな論理出力数を持つべきです。 SP-GiSTによって解決される困難とは、探索木のノードをディスクのページにマップするときに、多数のノードを通り抜ける場合であっても、探索ではごく少数のディスクページにしかアクセスしないですむようにすることです。

GiSTと同じく、SP-GiSTは適切なアクセス方法のある独自のデータ型の開発を可能にするためのもので、データベースのエキスパートよりもむしろ、そのデータ型の領域のエキスパートによる開発を可能にします。

ここで記述する情報の一部はPurdue大学のSP-GiSTインデックスプロジェクトWEBサイトによるものです。 PostgreSQLでのSP-GiSTの実装は、おもにTeodor SigaevとOleg Bartunovによって保守されており、詳しい情報は彼らのWEBサイトにあります。