9.3 9.4 9.5 9.6 10 11 12 13 14
阿里云PostgreSQL 问题报告 纠错本页面

65.1. 简介

SP-GiST是空间划分GiST(Space-partitioned GiST)的简称。SP-GiST支持划分搜索树,它们可用于开发许多各种不同的非平衡数据结构,例如四叉树、k-d树和单词查找树。这些结构的共同特征是它们反复地将搜索空间划分成大小不需要相等的分区。匹配这些划分规则的搜索将会很快。

这些常用的数据结构最初是为在内存中使用而设计的。在主存中,它们通常被设计为一组由指针链接的动态分配的结点。这对直接在磁盘上存储并不合适,因为这些指针链可能很长并且需要太多次的磁盘访问。相反,基于磁盘的数据结构应该具有高扇出来最小化 I/O。SP-GiST所提出的挑战是将搜索树结点映射到磁盘页面,这样即使是一次搜索会穿过很多结点,它也只需要访问很少的几个磁盘页面。

GiST一样,SP-GiST也打算允许带有合适访问方法的自定义数据类型的开发,这种开发只需由该数据类型的领域专家参与,而不需要数据库专家的参与。

这里的一些信息是来自于普渡大学的 SP-GiST 索引项目网站PostgreSQL中的SP-GiST实现主要由 Teodor Sigaev 和 Oleg Bartunov 维护,在他们的 网站上有更多信息。