65.1. Introduction

SP-GiST 是空间分区的 GiST 的缩写。 SP-GiST 支持分区搜索树,这有助于开发各种不同的非平衡数据结构,例如四叉树,k-d 树和基数树(重试)。这些结构的共同 Feature 是它们将搜索空间重复划分为多个分区,这些分区的大小不必相等。与分区规则完全匹配的搜索可以非常快。

这些流行的数据结构最初是为在内存中使用而开发的。在主存储器中,它们通常被设计为一组由指针链接的动态分配的节点。这不适用于直接存储在磁盘上,因为这些指针链可能会很长,这将需要太多的磁盘访问。相反,基于磁盘的数据结构应具有较高的扇出以最大程度地减少 I/O。 SP-GiST 解决的挑战是将搜索树节点 Map 到磁盘页面,以使搜索只需要访问几个磁盘页面,即使它遍历许多节点也是如此。

与 GiST 一样,SP-GiST 旨在允许由数据类型领域的 maven 而不是数据库 maven 使用适当的访问方法来开发自定义数据类型。

这里的某些信息来自普渡大学的 SP-GiST 索引项目web site。 PostgreSQL 中的 SP-GiST 实现主要由 Teodor Sigaev 和 Oleg Bartunov 维护,有关web site的更多信息。