69.1. 简介#

SP-GiST是空间分区GiST的缩写。SP-GiST支持分区搜索树，有助于开发各种不同的非平衡数据结构，例如四叉树、k-d 树和基数树（trie）。这些结构的共同特点是，它们会反复将搜索空间划分为分区，这些分区不必大小相等。与分区规则匹配良好的搜索速度可能非常快。

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

与GiST类似，SP-GiST旨在允许数据类型专家（而非数据库专家）开发具有适当访问方法的自定义数据类型。

此处的一些信息来自普渡大学的 SP-GiST 索引项目网站。PostgreSQL中的SP-GiST实现主要由 Teodor Sigaev 和 Oleg Bartunov 维护，有关更多信息，请访问他们的网站。