本节简单介绍了PostgreSQL中的SP-GiST索引,包括SP-GiST索引的基础知识和结构等. **简介** 上一节介绍了GiST索引,SP-GiST基于GiST,其中SP的意思是*space partitioning*,这里的space是指日常生活我们称之为空间的space,比如二维平面(two-dimensional plane)等. SP-GiST适用于空间可递归分割为N个互不相交区域的结构,包括quadtrees/k-dimensional trees(k-D trees)/radix trees. **结构** SP-GiST的访问方法是分割值域为互不相交的子域,这些子域可递归分割.这样的划分方法生成的树是非平衡树(Btree和GiST是平衡树). 互不相交的特性简化了插入和检索的复杂度.换句话说,树的分支率比较低.比如,一棵quadtree的某个节点通常有4个字节点(Btree可能有上百个)以及更深的高度.这种类型的树比较适合在内存中操作,但索引是存储在磁盘上面的,因此为了减少I/O,节点必须打包到pages中,要有效地做到这一点并不容易.除此之外,由于分支深度的不同,在索引中查找不同值所需的时间也有所不同. AM(access method)访问方法,与GiST类似,处理低层次的任务(并发访问和锁定/日志记录/纯搜索算法)并提供指定的简化接口以便为新数据类型和新分区算法提供支持. SP-GiST树的内部节点存储子节点的引用,*label*为每个参考定义.除此之外,内部节点可存储称为"prefix"的值,实际上这个值不是前缀;它可以看作是满足所有子节点的任意谓词. 叶子节点包含索引类型值和TID的引用.索引数据本身(搜索键)可以用作值,但这不是必需的:可以存储缩短的值. 另外,叶子节点可被分组为链表,因此内部节点可以参考一个值而不是整个链表. 注意叶子节点中的*prefixs,labels*有自己的数据类型,与其他节点相对独立. 与GiST一样,定义检索的主函数是*consistency function*,处理逻辑与GiST类似. 在物理存储上面,索引节点被打包为pages,这样可以在处理节点进行I/O时可以更高效,一个page可以包含内部或叶子节点,但不能既包含内部也包含叶子节点. **示例:quadtree** quadtree用于索引平面上的点,一种常用的做法是递归的将区域相对于中心点划分为四个部分(象限),在这样一棵树上,分支的深度可以变化,这取决于相应象限中点的密度. 举个例子: First, we split the plane into four quadrants  Then we split each of the quadrants  And so on until we get the final partitioning  下面是一个更简单的例子,如下图所示:  在该例中,4个象限编号为1-4,为了清晰起见,按照完全相同的顺序从左到右放置子节点,其中一种索引结构如下图所示:  每一个内部节点引用(指向)四个子节点中最大的那个.每一个引用使用象限编号打标记(如上图所示).但实现上没有标记存在,因为存储固定的数组更方便,其中一些引用还可能是空的. 沿用上一节使用的points数据表,创建SP-GiST索引: ``` testdb=# create index idx_points_quad_idx on points using spgist(p); CREATE INDEX ``` 默认使用quad_point_ops op class,包含以下operators: ``` testdb=# select amop.amopopr::regoperator, amop.amopstrategy testdb-# from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop testdb-# where opc.opcname = 'quad_point_ops' testdb-# and opf.oid = opc.opcfamily testdb-# and am.oid = opf.opfmethod testdb-# and amop.amopfamily = opc.opcfamily testdb-# and am.amname = 'spgist' testdb-# and amop.amoplefttype = opc.opcintype; amopopr | amopstrategy ------------------+-------------- <<(point,point) | 1 >>(point,point) | 5 ~=(point,point) | 6 <^(point,point) | 10 >^(point,point) | 11 <->(point,point) | 15 <@(point,box) | 8 (7 rows) ``` 下面希望找到(2,7)上的点,即:  搜索过程是从root节点开始,使用*consistency function*选择沿哪个子节点向下搜索,对于操作符">^",函数比较(2,7)和中心点(4,4)选择可能包含目标点的象限(在本例中是第一和第四象限),在第一象限,使用*consistency function*确定沿哪个子节点向下搜索,第一象限的中心点是(6,6),因此继续搜索第一和第四象限(该象限为空),叶子节点(8,6)和(7,8)在第一象限中,只有(7,8)满足查询条件,返回结果同时回到上一层检索中心点(4,4)的第四象限,该象限为空,深度遍历结束. ``` testdb=# set enable_seqscan = off; SET testdb=# explain (costs off) select * from points where p >^ point '(2,7)'; QUERY PLAN ----------------------------------------------------- Index Only Scan using idx_points_quad_idx on points Index Cond: (p >^ '(2,7)'::point) (2 rows) testdb=# select * from points where p >^ point '(2,7)'; p ------- (7,8) (1 row) ``` **参考资料** [Indexes in PostgreSQL — 6 (SP-GiST)](https://habr.com/en/company/postgrespro/blog/446624/)