9.SP-GIST索引详解-01.docx

9页

0次

2024-07-13

25墨值下载

SP-GIST 索引介绍

SP-GiST 指空间分区(Space-Partitioned)的 GiST，有助于开发四叉树，KD 树，基数树

(radix tree)等非平衡数据结构，它主要是通过一些新的索引算法来提高 GiST 索引在某种情况

下的性能。它划分的搜索空间不存在重叠，因此，SP-GiST 访问方法的思想是将值域拆分为

不重叠的子域，每个子域又可以拆分。

SP-GiST 和 GiST 都是通用的搜索树

SP-GiST 的叶子节点包含索引类型的值和行（TID）的引用。此外，叶子节点可以分组为列

表。因此，中间节点不仅可以引用一个值，还可以引用整个列表。

PostgreSQL 内建的 SP-GiST 索引操作符类

操作符类名被索引的数据类型索引支持的操作符索引算法

kd_point_ops point << <@ <^ >> >^ ~=

KD 树

quad_point_ops point << <@ <^ >> >^ ~=

四叉树

range_ops any range type && &< &> -|- << <@ = >> @>

四叉树

text_ops text

< <= = > >= ~<=~ ~<~ ~>=~

~>~

基数树(radix tree)

注: quad_point_ops 是 point 类型缺省的 SP-GiST 索引操作符类

SP-GIST 应用案例 1-四叉树

四叉树用于索引平面中的点，它将区域相对于中心点递归地分为四个部分（象限）。

首先，将平面划分为四个象限...

然后，划分每个象限...，

依此类推，直到获得最终分区。

of 9

25墨值下载

关注