本系列的内容主要翻译自Postgresql官方博客，为了便于理解，对于其中部分涉及到的知识，我在查阅相关资料的基础上做了补充。
原文: Indexes in PostgreSQL — 6 (SP-GiST)
系列文章索引
我们已经讨论了PostgreSQL的索引引擎 、访问方法接口 以及三个索引方法：哈希索引 、B树 和GiST 。这篇文章中，我们将讨论SP-GiST。
SP-GiST 首先，关于这个名字要说一下。名字中的”GiST”暗指其和同名的GiST索引方法有相似的地方。相似的地方是指：两者都是通用搜索树，都提供了一个构建不同索引方法的通用框架。
“SP”主要是指空间分区(space partitioning)。这里的空间我们通常会理解成我们习惯上所认为的空间，比如说一个二维的平面。但是我们将看到这里的空间可以是任何值域。
SP-GiST适用于那些空间可以被递归的分割成非相交区域的结构(这一点和GiST不同)。这类树包含四叉树(comprises quadtrees)、K维树 (k-D trees)以及弧形树( radix trees)。
结构 所以，SP-GiST的思想是将值域划分为彼此不覆盖的子域，而子域有可以被进一步分割。像这样的分割会导致不平衡树（不像B树和GiST树）
不相交的特性简化了插入和搜索过程的策略。另一方面，作为一项规则，诱导的树是低分枝的。例如，一个四叉树通常有四个子节点(不像B树。子节点的数目可以是上百个)和更高的深度。像这样的树很适合在内存中工作，但是索引是存储在磁盘上的。因此为了减少IO操作的数量，必须将节点打包成页，但是高效的做到这一点并不容易。此外，由于分支的深度不同，在索引中找到不同数值的时间也可能不同。
这个访问方法和GiST一样，做一些底层的工作(并发访问、锁、日志以及纯粹的搜索算法)，同时提供了专门的简化接口，来方便增加新的数据和分区算法。
SP-GiST内部的节点存储了对子节点的引用；可以给每一个引用定义一个标签。此外，一个内部节点可以存储一个被叫做prefix 的值。实际上这个值不强制一定是前缀，它可以是任意一个满足所有子节点的谓词。
SP-GiST的叶子节点存储了一个索引类型的值和一个对表行的引用。被索引的数据本身(索引键)可以作为这个索引类型的值，但不是必须的：一个缩短类型的值会被存储。
此外，叶子节点可以被分组为列表。因此，一个内部节点不仅可以引用一个值，也可以引用整个列表
请注意，叶子节点的前缀、标签以及值都有自己的数据类型，是彼此独立的。
和GiST一样，为搜索定义的主要函数是一致性函数。这个函数在一个树节点上被调用，并且返回一组子节点，这些子节点的值和搜索的谓语一致。对于一个子节点，一致性函数决定了这个节点中的索引值是否符合搜索谓词。
搜索从根节点开始，一致性函数决定有必要访问的子节点。该算法会在找到的每个子节点上重复运行。该搜索是深度优先的。
在物理层面，索引节点被打包成页，以便在IO层面能让节点的工作更有效率。请注意，一个页面可以包含内部节点和叶子节点，但是不能同时包含。
例子：四叉树 四叉树可以索引平面上的点。思想是根据中心点将平面划分为四个象限，这颗树的分支深度可以是不同的，其深度取决于当前象限内点的密度。
下面是一个样例数据，其数据来源是用openflights.org 上的数据对 demo database 做了扩充。
首先将平面划分为四个象限
然后再分割每个象限
接着分割，直到得到最后的分区
让我们来提供一个例子来说明更多的细节。这种情况下我们的分区像下图所示。
象限的编号如左图所示。为了明确期间，子节点的象限编号也是按照这个顺序。这种例子下，一个可能的索引结构如下图所示。每个内部节点最多可以引用四个节点，每个引用都可以用象限的编号作为标签。但是实际的实现中没有标签，因为存储四个引用的固定数组会更加方便。
1 2 3 4 5 6 7 postgres=# create table points(p point); postgres=# insert into points(p) values (point '(1,1)'), (point '(3,2)'), (point '(6,3)'), (point '(5,5)'), (point '(7,8)'), (point '(8,6)'); postgres=# create index points_quad_idx on points using spgist(p);
在这个例子中，默认使用的操作符类是”quad_point_ops”，其包含下面这些操作
1 2 3 4 5 6 7 8 postgres=# select amop.amopopr::regoperator, amop.amopstrategy from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop where opc.opcname = 'quad_point_ops' and opf.oid = opc.opcfamily and am.oid = opf.opfmethod and amop.amopfamily = opc.opcfamily and am.amname = 'spgist' and amop.amoplefttype = opc.opcintype;
1 2 3 4 5 6 7 8 9 amopopr | amopstrategy -----------------+-------------- <<(point,point) | 1 strictly left >>(point,point) | 5 strictly right ~=(point,point) | 6 coincides <^(point,point) | 10 strictly below >^(point,point) | 11 strictly above <@(point,box) | 8 contained in rectangle (6 rows)
作为例子，我们来看查询select * from points where p >^ point ‘(2,7)’将被怎么执行
我们从根节点开始应用一致性函数去选择哪些节点可以被下沉。对于操作符>^，函数将点(2,7)与中心点(4,4)比较以后，选择出可能包含寻求的点数的象限，这个例子中，是第一和第四象限。
在第一象限的节点中，我们再次使用一致性函数来选择出可能的子节点。中心点是(6,6)，我们需要再次寻找子节点的第一象限和第四象限。
第一象限的叶子节点是包含了(8,6)和(7,8)的列表，其中只有(7,8)是符合要求的。对第四象限的引用都是空的。
(4,4)节点的第四象限也是空的，因此搜素就完成了。
1 2 3 postgres=# set enable_seqscan = off; postgres=# explain (costs off) select * from points where p >^ point '(2,7)';
1 2 3 4 5 QUERY PLAN ------------------------------------------------ Index Only Scan using points_quad_idx on points Index Cond: (p >^ '(2,7)'::point) (2 rows)
内部 我们可以使用“gevel” 插件来看SP-GiST索引的内部情况。
让我们以示例数据为例
1 demo=# create index airports_coordinates_quad_idx on airports_ml using spgist(coordinates);
首先，我们获取索引的一些统计信息
1 demo=# select * from spgist_stats('airports_coordinates_quad_idx');
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 spgist_stats ---------------------------------- totalPages: 33 + deletedPages: 0 + innerPages: 3 + leafPages: 30 + emptyPages: 2 + usedSpace: 201.53 kbytes+ usedInnerSpace: 2.17 kbytes + usedLeafSpace: 199.36 kbytes+ freeSpace: 61.44 kbytes + fillRatio: 76.64% + leafTuples: 5993 + innerTuples: 37 + innerAllTheSame: 0 + leafPlaceholders: 725 + innerPlaceholders: 0 + leafRedirects: 0 + innerRedirects: 0 (1 row)
然后，我们输出索引数本身
1 2 3 4 5 6 7 8 9 10 11 12 demo=# select tid, n, level, tid_ptr, prefix, leaf_value from spgist_print('airports_coordinates_quad_idx') as t( tid tid, allthesame bool, n int, level int, tid_ptr tid, prefix point, -- prefix type node_label int, -- label type (unused here) leaf_value point -- list value type ) order by tid, n;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 tid | n | level | tid_ptr | prefix | leaf_value ---------+---+-------+---------+------------------+------------------ (1,1) | 0 | 1 | (5,3) | (-10.220,53.588) | (1,1) | 1 | 1 | (5,2) | (-10.220,53.588) | (1,1) | 2 | 1 | (5,1) | (-10.220,53.588) | (1,1) | 3 | 1 | (5,14) | (-10.220,53.588) | (3,68) | | 3 | | | (86.107,55.270) (3,70) | | 3 | | | (129.771,62.093) (3,85) | | 4 | | | (57.684,-20.430) (3,122) | | 4 | | | (107.438,51.808) (3,154) | | 3 | | | (-51.678,64.191) (5,1) | 0 | 2 | (24,27) | (-88.680,48.638) | (5,1) | 1 | 2 | (5,7) | (-88.680,48.638) | ...
但是请记住，”spgist_print”输出的不是叶子节点中的所有值，而是列表中的第一个。因此，这里展示的是索引的结构而不是全部的内容。
K维树 同样是平面上的点，我们也可以使用另外一种分区方法。
让我们先画一条横着的线经过第一个被索引的点，这条直线将平面分割维上下两个部分。下一个索引的点就处在这两个部分的一个。通过第二个点，画一条竖着的线，将这个部分再次划分为左右两个部分。然后我们再画一条水平的线通过下一个点，再画一条垂直的线经过下一个点，如此反复。
这样建立的树所有内部的节点都只有两个子节点的引用，这两个引用都可以通向下一个内部节点或者通向叶子节点的列表。
这种方法可以很容易的推广到K维空间，因此在文献中，这些树也被称为k-dimensional (k-D trees)
以机场的例子解释该方法
首先将平面划分为上下两个部分
然后将每个部分分割为左右两个部分
为了使用这样的分区，我们需要在创建索引的时候明确的指定操作符类“kd_point_ops”
1 postgres=# create index points_kd_idx on points using spgist(p kd_point_ops);
这个操作符类包含和默认的”quad_point_ops”完全相同的操作符。
内部 在查看树结构的时候，我们需要考虑到，在这种情况下，前缀只是一个坐标，而不是一个点。
因为是垂直或者水平分割的，因此前缀只需要一个数字就可以表示。
1 2 3 4 5 6 7 8 9 10 11 12 demo=# select tid, n, level, tid_ptr, prefix, leaf_value from spgist_print('airports_coordinates_kd_idx') as t( tid tid, allthesame bool, n int, level int, tid_ptr tid, prefix float, -- prefix type node_label int, -- label type (unused here) leaf_value point -- list node type ) order by tid, n;
1 2 3 4 5 6 7 8 9 10 11 tid | n | level | tid_ptr | prefix | leaf_value ---------+---+-------+---------+------------+------------------ (1,1) | 0 | 1 | (5,1) | 53.740 | (1,1) | 1 | 1 | (5,4) | 53.740 | (3,113) | | 6 | | | (-7.277,62.064) (3,114) | | 6 | | | (-85.033,73.006) (5,1) | 0 | 2 | (5,12) | -65.449 | (5,1) | 1 | 2 | (5,2) | -65.449 | (5,2) | 0 | 3 | (5,6) | 35.624 | (5,2) | 1 | 3 | (5,3) | 35.624 | ...
例子：弧度树 我们也可以用SP-GiST来为字符串实现一个弧度树。弧度树的思想是要索引的字符串并不完全存储在一个叶子节点中，而是通过串联的存储在这个节点以上直到根部的值来获取到。
假设我们需要索引几个地址:”postgrespro.ru”,”postgrespro.com”,”postgresql.org”和”planet.postgresql.org”
1 2 3 4 5 postgres=# create table sites(url text); postgres=# insert into sites values ('postgrespro.ru'),('postgrespro.com'),('postgresql.org'),('planet.postgresql.org'); postgres=# create index on sites using spgist(url);
树的结构如下所示:
数字的叶子节点存储了所有子节点的前缀。例如，在”stgres”这个节点的子节点中的值都以 “p” + “o” + “stgres”为前缀。
与四叉树不同的是，每一个指向子节点的指针中都使用了额外的一个字符(更精确的来说是两个字节，但是这并不重要)作为标签。
“text_ops “运算符类支持类似B-树的运算符： “equal”, “greater”, and “less”:
1 2 3 4 5 6 7 8 postgres=# select amop.amopopr::regoperator, amop.amopstrategy from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop where opc.opcname = 'text_ops' and opf.oid = opc.opcfamily and am.oid = opf.opfmethod and amop.amopfamily = opc.opcfamily and am.amname = 'spgist' and amop.amoplefttype = opc.opcintype;
1 2 3 4 5 6 7 8 9 10 11 12 13 14 amopopr | amopstrategy -----------------+-------------- ~<~(text,text) | 1 ~<=~(text,text) | 2 =(text,text) | 3 ~>=~(text,text) | 4 ~>~(text,text) | 5 <(text,text) | 11 <=(text,text) | 12 >=(text,text) | 14 >(text,text) | 15 ^@(text,text) | 28 (10 rows)
带标记的运算符的区别在于，他们操作的是字节而不是字符。
有的时候，用弧度树的形式表示可能会比B树更加紧凑的，因为数值不是完全存储的，而是通过树的下降来重建字符串。
考虑到这个查询:select * from sites where url like ‘postgresp%ru’。它可以通过索引来执行
1 2 postgres=# set enable_seqscan = off; postgres=# explain (costs off) select * from sites where url like 'postgresp%ru';
1 2 3 4 5 6 QUERY PLAN ------------------------------------------------------------------------------ Index Only Scan using sites_url_idx on sites Index Cond: ((url ~>=~ 'postgresp'::text) AND (url ~<~ 'postgresq'::text)) Filter: (url ~~ 'postgresp%ru'::text) (3 rows)
实际上索引是用来寻找大于等于postgresp并且小于postgresq的值，然后从结果中选择匹配的值。
首先一致性函数必须决定出要下降到p的哪个子节点。显然，需要下降到”p “+”o “+”stgres”
对于 “stgres “节点，需要再次调用一致性函数来检查。 这次下降到”postgres “+”p “+”ro”。
对于”ro.”节点以及所有的叶子节点，一致性函数将返回TRUE，因此索引方法返回了两个值:”postgrespro.com “和 “postgrespro.ru”。然后在过滤阶段从他们中选择匹配的值。
内部 在查看树状结构的时候，需要将数据类型考虑在内
1 2 3 4 5 6 7 8 9 10 11 postgres=# select * from spgist_print('sites_url_idx') as t( tid tid, allthesame bool, n int, level int, tid_ptr tid, prefix text, -- prefix type node_label smallint, -- label type leaf_value text -- leaf node type ) order by tid, n;
原文中并没有，下面的结果是自己运行后结果。 但是由于原文中插入的数据过少，展示出的结果只有一个层级，因此我在里面又插入了几千条记录得出的内部树结构。node_label的值是字符的ASCII码，例如112是p、 119 是 w。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 tid | allthesame | n | level | tid_ptr | prefix | node_label | leaf_value ----------+------------+----+-------+---------+--------+------------+---------------------- (1,1) | f | 0 | 1 | | | 112 | (1,1) | f | 1 | 1 | | | 119 | (3,4) | | | 2 | | | | lanet.postgresql.org (3,85) | | | 3 | | | | 63.com (3,87) | | | 3 | | | | d.com (3,89) | | | 4 | | | | cuweather.com (3,91) | | | 4 | | | | swers.yahoo.com (3,100) | | | 3 | | | | 60.cn (3,103) | | | 3 | | | | ao123.com (3,104) | | | 3 | | | | sn.com (3,109) | | | 3 | | | | q.com (3,112) | | | 3 | | | | acebook.com (5,1) | f | 0 | 2 | | ww. | 49 | (5,1) | f | 1 | 2 | | ww. | 51 | (5,1) | f | 2 | 2 | | ww. | 97 | (5,1) | f | 3 | 2 | | ww. | 98 | (5,1) | f | 4 | 2 | | ww. | 99 | (5,1) | f | 5 | 2 | | ww. | 100 | (5,1) | f | 6 | 2 | | ww. | 101 | (5,1) | f | 7 | 2 | | ww. | 102 | ...
属性 然后来看一下 SP-GiST 的属性
1 2 3 4 5 select a.amname, p.name, pg_indexam_has_property(a.oid,p.name) from pg_am a, unnest(array['can_order','can_unique','can_multi_col','can_exclude']) p(name) where a.amname = 'spgist' order by a.amname;
1 2 3 4 5 6 7 amname | name | pg_indexam_has_property --------+---------------+------------------------- spgist | can_order | f spgist | can_unique | f spgist | can_multi_col | f spgist | can_exclude | t (4 rows)
spgist不支持用来排序也不能做唯一约束。此外，这样的索引也不能建立在多个字段上，但是允许用来做唯一约束。
下列的索引属性是可以用的
1 2 3 4 select p.name, pg_index_has_property('sites_url_idx'::regclass,p.name) from unnest(array[ 'clusterable','index_scan','bitmap_scan','backward_scan' ]) p(name);
1 2 3 4 5 6 7 8 name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | t bitmap_scan | t backward_scan | f (4 rows)
这里与GiST的区别在于，SP-GiST不支持聚类。
最后，下面是列属性
1 2 3 4 5 6 select p.name, pg_index_column_has_property('sites_url_idx'::regclass,1,p.name) from unnest(array[ 'asc','desc','nulls_first','nulls_last','orderable','distance_orderable', 'returnable','search_array','search_nulls' ]) p(name);
1 2 3 4 5 6 7 8 9 10 11 12 name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | t search_array | f search_nulls | t (9 rows)
不支持排序，这是可以预见的。到目前为止，SP-GiST中还没有用于搜索近邻的距离运算符。最有可能的是，这个功能将在未来得到支持。
SP-GiST可以用于纯索引扫描，至少对于所讨论的运算符类来说是这样。正如我们所看到的，在某些情况下，索引值被明确地存储在叶子节点中，而在其他情况下，这些值是在树的下降过程中逐部分重建的。
NULLs 为了不使情况复杂化，到目前为止我们还没有提到NULL。从索引属性中可以看出，NULL是被支持的
1 2 postgres=# explain (costs off) select * from sites where url is null;
1 2 3 4 5 QUERY PLAN ---------------------------------------------- Index Only Scan using sites_url_idx on sites Index Cond: (url IS NULL) (2 rows)
然而，NULL对于SP-GiST来说是一个陌生的东西。所有来自 “spgist “操作符类的操作符都必须是严格的：只要操作符的任何参数是NULL，就必须返回NULL。方法本身确保了这一点。NULL不会被传递给操作符。
但是，为了使用只扫描索引的访问方法，NULL必须被存储在索引中。它们被存储在在一个单独的有自己根的树中。
其它数据类型 除了点和为了字符串使用的弧度树以外，还有一些其它的基实现了SP-GiST的访问方法。
“box_ops “运算符类为矩形提供了一个四象限树。每个矩形用四维空间中的一个点来表示，因此象限的数量是16。如果存在很多相交的矩形，SP-GiST索引就会比GiST有更高的性能：在GiST中，没有这样的边界能够将彼此相交的分离开来，而点（即使是四维的）则没有这样的问题。
“range_ops “运算符类为区间(intervals)提供了一个四叉树。一个区间由一个二维的点来表示：下边界成为横轴，上边界成为纵轴。
