本节简单介绍了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)