<acronym>SP-GiST</acronym> is an abbreviation for space-partitioned <acronym>GiST</acronym>. <acronym>SP-GiST</acronym> supports partitioned search trees, which facilitate development of a wide range of different non-balanced data structures, such as quad-trees, k-d trees, and radix trees (tries). The common feature of these structures is that they repeatedly divide the search space into partitions that need not be of equal size. Searches that are well matched to the partitioning rule can be very fast. SP-GiSTは、空間分割された(Space-Partitioned)GiSTを短縮した語です。 SP-GiSTは分割された探索木をサポートし、四分木、kd木、基数木(トライ木)など広範にわたる様々な非平衡データ構造の開発を可能にします。 これらの構造に共通の特徴は、それらが探索空間を繰り返し小さな領域に分割し、その領域の大きさが必ずしも等しくない、ということです。 分割規則によく適合した検索は非常に高速になります。

These popular data structures were originally developed for in-memory usage. In main memory, they are usually designed as a set of dynamically allocated nodes linked by pointers. This is not suitable for direct storing on disk, since these chains of pointers can be rather long which would require too many disk accesses. In contrast, disk-based data structures should have a high fanout to minimize I/O. The challenge addressed by <acronym>SP-GiST</acronym> is to map search tree nodes to disk pages in such a way that a search need access only a few disk pages, even if it traverses many nodes. これらのよく使われるデータ構造は、元々はメモリ内での利用のために開発されたものでした。 主記憶上では、それらは通常、ポインタにより接続され、動的に割り当てられるノードの集合として設計されます。 このようなポインタのチェーンは長くなりがちで、非常に多くのディスクアクセスが必要となるため、ディスク上に直接格納するには適しません。 これとは反対に、ディスクベースのデータ構造は、I/Oを最小化する、大きな論理出力数を持つべきです。 SP-GiSTによって解決される困難とは、探索木のノードをディスクのページにマップするときに、多数のノードを通り抜ける場合であっても、探索ではごく少数のディスクページにしかアクセスしないですむようにすることです。

Like <acronym>GiST</acronym>, <acronym>SP-GiST</acronym> is meant to allow the development of custom data types with the appropriate access methods, by an expert in the domain of the data type, rather than a database expert. GiSTと同じく、SP-GiSTは適切なアクセス方法のある独自のデータ型の開発を可能にするためのもので、データベースのエキスパートよりもむしろ、そのデータ型の領域のエキスパートによる開発を可能にします。

Some of the information here is derived from Purdue University's SP-GiST Indexing Project <ulink url="https://www.cs.purdue.edu/spgist/">web site</ulink>. The <acronym>SP-GiST</acronym> implementation in <productname>PostgreSQL</productname> is primarily maintained by Teodor Sigaev and Oleg Bartunov, and there is more information on their <!&#45;- URL will be changed &#45;-> <ulink url="http://www.sai.msu.su/~megera/wiki/spgist_dev">web site</ulink>. ここで記述する情報の一部はPurdue大学のSP-GiSTインデックスプロジェクトWEBサイトによるものです。 PostgreSQLでのSP-GiSTの実装は、おもにTeodor SigaevとOleg Bartunovによって保守されており、詳しい情報は彼らのWEBサイトにあります。