Postgresql 中文操作指南
69.1. Introduction #
SP-GiST 是空间分区 GiST 的缩写。SP-GiST 支持分区的搜索树，这有助于开发各种不同的非平衡数据结构，例如四树、k-d 树和基数树（字典树）。这些结构的共同特点是它们重复地将搜索空间划分为不必等大小的分区。与分区规则非常匹配的搜索可以非常快。
SP-GiST is an abbreviation for space-partitioned GiST. SP-GiST 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.
这些流行的数据结构最初是为内存中使用而开发的。在主内存中，它们通常设计为一组通过指针链接的动态分配节点。这不适合直接存储在磁盘上，因为这些指针链可能相当长，需要太多磁盘访问。相反，基于磁盘的数据结构应该有较高的扇出，以最大限度减少 I/O。SP-GiST 解决的挑战是将搜索树节点映射到磁盘页面中，这样即使搜索遍历了许多节点，它也只需要访问几个磁盘页面。
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 SP-GiST 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.
与 GiST 一样，SP-GiST 旨在允许数据类型领域的专家（而不是数据库专家）通过适当的访问方法开发自定义数据类型。
Like GiST, SP-GiST 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.