PostgreSQL索引(5) – GiST
本文翻译自Egor Rogov的英文博客，且已征得Egor Rogov的同意。译者做了少量修改。
审校：纪昀红，中国人民大学信息学院在读博士生。
在前面几篇文章中，我们讨论了通用索引引擎、AM的接口和两种AM（Hash索引、B-tree索引）。本文将介绍GiST索引。
GiST是generalized search tree的简称，即通用搜索树。像B-tree一样，它也是一颗平衡树。
它们有什么区别呢？B-tree和比较的语义强关联在一起，即它只有使用>、>=、=、<=、<这五个操作符进行比较的能力，当然这个能力已经非常强大。但是，现代数据库系统中经常存储一些在这5个操作符上没有实际意义的数据类型，比如地理数据、图像数据、文本数据。
GiST索引可以帮助我们处理这些数据类型。它允许用户自己定义一个规则，这个规则可以把任意数据类型的数据分布在一颗平衡树上。并且它提供一种方法，一些操作符可以利用这种方法检索这棵树。例如，借助于相对位置（在左边、在右边、包含等）操作符，R-tree就可以被存储在GiST索引中，用来处理空间数据；借助于集合的交、包含操作符，RD-tree也可以被存储在GiST索引中。
PG具有很好的扩展性，通过前几篇文章可知，我们完全可以从头实现一种新的索引类型。为了达到这个目的，我们必须实现一个通用索引引擎的接口。但是，这仍然需要很强的专业知识，需要花费大量的人力，因为我们不但需要了解新索引本身的逻辑，还要把索引的数据映射到PG的页面中，需要高效地使用锁，需要考虑redo日志。GiST简化了我们的任务，它为我们处理了一些底层的问题，并且为我们提供了它自己的接口：与应用相关，但是与PG内部技术无关的接口。从这个意义上说，我们可以把GiST看作一个实现新索引类型的框架。
1. 结构
GiST是一颗平衡树，即从根节点到叶子节点所经过的节点数都相同。节点中包含了索引的数据行。
通常来讲，叶子节点中的每一行都包含一个谓词（bool类型的表达式）和一个指向基表的TID。索引数据（key）必须满足这个谓词。
非叶子节点的每一行也包含一个谓词和一个指向孩子节点的指针，这个孩子节点所表示的子树中的所有数据都必须满足这个谓词。GiST这个重要的特性替换了B-tree中简单的有序性质。
查询GiST树需要使用一个特殊的一致性(consistent) 函数，这是GiST的一个接口函数，可以被各种操作符族自由的实现。
GiST在处理每行数据时，都会调用这个一致性函数，用来确定这行数据是否满足谓词条件（由indexed-field operator expression指定）。对非叶子节点来说，这个函数决定是否有必要向下搜索相应的子树；对叶子节点来说，这个函数决定某行索引数据是否满足谓词条件。
与一般树的搜索算法相同，查询从根节点开始。通过调用一致性函数，可以知道继续搜索哪些子树（可能有多个子树满足条件），可以排除哪些子树。对所有符合条件的子节点，重复这个搜索过程。对叶子节点，将满足一致性函数的行作为结果返回。
搜索过程使用深度优先搜索。尽可能快的到达叶子节点，使得查询尽快返回结果。这在用户仅仅需要部分结果时非常有用。
再次强调一下，这个一致性函数与>、>=、=、<=、<完全没有关系。各种不同索引之间的一致性函数的含义可能完全不同，因此，索引也不保证按某种顺序返回结果。
本文不会介绍GiST索引的插入和删除算法：处理这些操作的是其它几个接口。然而，需要注意的是，当向索引中插入一个新值时，插入的位置会基于这样的原则进行选择：插入这个点后，可以让父节点的谓词扩展的尽可能小。但是当删除一个值时，父节点的谓词条件的范围不会收缩。收缩仅仅发生在这些场景：一个页面被分裂成两个（当一个页面没有空间存放新值时）、索引被重建（reindex、vacuum full）时。因此，在频繁更新的场景下，GiST的效率会随着时间逐渐下降。
下文通过具体的示例介绍几种不同数据类型的索引，和它们一些有用的性质：
- 点（和其它地理实体）和最近邻搜索
- 区间和排它约束
- 全文检索
2. 用R-tree索引点
2.1 两个示例
我们将使用平面上的点展示这个示例（当然，也可以为其它地理数据类型创建类似的索引）。常规的B-tree并不适合这种数据类型，因为比较两个点的大小没有实际意义。
R-tree的思想是将平面划分成多个矩形，这些矩形可以覆盖所有被索引的点。一个索引行存放一个矩形，谓词可以被定义成：被搜索的点是否被给定的矩形包含。
R-tree的根节点存储几个最大的矩形，它们可能相互重叠。孩子节点存储小一些的矩形；孩子节点存储的矩形被父节点包含；孩子节点存储的矩形又包含孙子节点中所有的矩形（或点）。
理论上来说，叶子节点应该存储点，但是叶子节点和非叶子节点中的数据类型必须相同，因此，叶子节点也存放矩形，但是这些矩形退化成点。
我们使用可视化的方式展示一个三层的R-tree。这些点是飞机场的坐标（和demo数据库中的airports表类似，但是展示了更多openflights.org上的数据）。
第一层：两个相交的矩形
第二层：大矩形被划分成更小的矩形
第三层：每个矩形存放尽可能多的点，并且可以被容纳到一个索引页面中
现在考虑一个更简单的示例，它只有一层。
create table points(p point);
insert into points(p) values
(point '(1,1)'), (point '(3,2)'), (point '(6,3)'),
(point '(5,5)'), (point '(7,8)'), (point '(8,6)');
create index on points using gist(p);
如果按照上图分裂，索引节点的关系如下：
set enable_seqscan = off;
explain(costs off) select * from points where p <@ box '(2,1),(7,4)';
QUERY PLAN
----------------------------------------------
Index Only Scan using points_p_idx on points
Index Cond: (p <@ '(7,4),(2,1)'::box)
(2 rows)
操作符（indexed-field <@ expression，indexed-field是一个点，expression是一个矩形）的一致性函数定义如下：对一个非叶子节点的索引行，如果它表示的矩形与表达式中的矩形相交，则返回yes；对一个叶子节点的索引行，如果它表示的点（退化的矩形）被表达式中的矩形包含，则返回yes。
查询从根节点开始。矩形{(2,1)-(7,4)}与{(1,1)-(6,3)}相交，但是与{(5,5)-(8,8)}不相交，因此不需要搜索第二颗子树。
到达第一个叶子节点时，我们遍历它包含的3个点，返回其中两个作为结果：(3,2)和(6,3)。
select * from points where p <@ box '(2,1),(7,4)';
p
-------
(3,2)
(6,3)
(2 rows)
2.2 内部结构
本小节使用上文飞机场的示例介绍索引的内部结构。
Pageinspect插件不能查看GiST索引的内部结构。我们可以使用另外一个插件：gevel。它没有被包含在标准的发行版中，点击这里查看安装指南。
如果一切顺利，它将提供3个函数。首先，看一下索引的统计数据：
select * from gist_stat('airports_coordinates_idx');
gist_stat
------------------------------------------
Number of levels: 4 +
Number of pages: 690 +
Number of leaf pages: 625 +
Number of tuples: 7873 +
Number of invalid tuples: 0 +
Number of leaf tuples: 7184 +
Total size of tuples: 354692 bytes +
Total size of leaf tuples: 323596 bytes +
Total size of index: 5652480 bytes+
(1 row)
可以看出，索引包含4层，共有690个页面：根节点和中间两层已在上文的图中被展示，第4层是叶子节点。实际上，包含8000个点的索引的体积不应该这么大：为了清晰展示，我们只使用了10%的填充率，导致索引的体积大一些。
然后，我们可以输出这棵树：
select * from gist_tree('airports_coordinates_idx');
gist_tree
-----------------------------------------------------------------------------------------
0(l:0) blk: 0 numTuple: 5 free: 7928b(2.84%) rightlink:4294967295 (InvalidBlockNumber) +
1(l:1) blk: 335 numTuple: 15 free: 7488b(8.24%) rightlink:220 (OK) +
1(l:2) blk: 128 numTuple: 9 free: 7752b(5.00%) rightlink:49 (OK) +
1(l:3) blk: 57 numTuple: 12 free: 7620b(6.62%) rightlink:35 (OK) +
2(l:3) blk: 62 numTuple: 9 free: 7752b(5.00%) rightlink:57 (OK) +
3(l:3) blk: 72 numTuple: 7 free: 7840b(3.92%) rightlink:23 (OK) +
4(l:3) blk: 115 numTuple: 17 free: 7400b(9.31%) rightlink:33 (OK) +
...
最后，我们可以输出索引行的数据。注意：结果必须被强制转换成所需的数据类型。在我们的场景中，这个类型是box（矩形的边框）。顶层节点中的5行如下：
select level, a from gist_print('airports_coordinates_idx')
as t(level int, valid bool, a box) where level = 1;
level | a
-------+-----------------------------------------------------------------------
1 | (47.663586,80.803207),(-39.2938003540039,-90)
1 | (179.951004028,15.6700000762939),(15.2428998947144,-77.9634017944336)
1 | (177.740997314453,73.5178070068359),(15.0664,10.57970047)
1 | (-77.3191986083984,79.9946975708),(-179.876998901,-43.810001373291)
1 | (-39.864200592041,82.5177993774),(-81.254096984863,-64.2382965088)
(5 rows)
实际上，上面的图片，就是用这些数据生成的。
2.3 搜索操作符和排序操作符
到目前为止，所讨论的操作符都被称作搜索操作符（例如p <@ box ‘(2,1),(7,4)’中的 <@），因为他们在查询中表示搜索条件。
除了搜索操作符，还有另外一种操作符：排序操作符。它们可以出现在order by子句中用来指定排序条件，代替通常的列作为排序条件。请看一个示例：
select * from points order by p <-> point '(4,7)' limit 2;
p
-------
(5,5)
(7,8)
(2 rows)
p point ‘(4,7)’条件用了一个排序操作符：。它表示：把结果按照与点(4,7)的距离进行排序。limit 2表示返回两个。这种查询也被称作k-NN查询（K近邻查询）。
一个AM为了支持这种查询，必须定义一个额外的距离函数，而且排序操作符必须被适当的操作符类包含，例如点的points_ops类。下面展示了操作符和它们的类型（s表示搜索操作符，o表示排序操作符）：
select amop.amopopr::regoperator, amop.amoppurpose, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'point_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'gist'
and amop.amoplefttype = opc.opcintype;
amopopr | amoppurpose | amopstrategy
-------------------+-------------+--------------
<<(point,point) | s | 1 strictly left
>>(point,point) | s | 5 strictly right
~=(point,point) | s | 6 coincides
<^(point,point) | s | 10 strictly below
>^(point,point) | s | 11 strictly above
<->(point,point) | o | 15 distance
<@(point,box) | s | 28 contained in rectangle
<@(point,polygon) | s | 48 contained in polygon
<@(point,circle) | s | 68 contained in circle
(9 rows)
策略（B-tree一文中提到过策略，B-tree支持5种比较策略）的序号也被展示出来，并且附上了它们的含义。明显看出，它支持的策略比B-tree多，有一些策略只支持点。还可以为其它数据类型定义不同的策略。
每处理一个索引行，都会调用距离函数，它必须可以计算出表达式（indexed-field ordering-operator expression）中的值（expression）与索引行的距离。对叶子节点中的索引行来说，这个值就是准确的距离。对非叶子节点来说，这个函数必须返回此节点所包含的所有叶子节点中的数据行与expression的最短距离。因为遍历所有的叶子节点代价很大，这个函数可以低估距离，以损失效率为代价。但是不可以高估这个距离，因为这会破坏整个搜索过程。
距离函数可以返回任意可以排序的类型。就像之前介绍的一样，为了对值排序，PG会从b-tree的操作符族中选择适当的操作符。
对平面上的点来说，这个距离可以被简单的解释为两个点的欧式距离。点与矩形之间的距离是从点到这个矩形的最小距离，如果矩形包含这个点，则距离为0。无需遍历孩子节点就可以简单计算出这个距离，这个值肯定不会大于点到矩形中任意点的距离。
我们分析上面查询的搜索算法。
查询从根节点开始。根节点包含两个矩形，(4,7)到矩形{(1,1)-(6,3)}的距离为4.0，到矩形{(5,5)-(8,8)}的距离为1.0。
孩子节点按照距离递增的顺序被搜索。在这种方式下，我们首先下降到最近的孩子节点中，并且计算孩子节点中的点到(4,7)的距离：
这些信息已经足够返回距离(4,7)最近的两个点作为结果：(5,5) and (7,8)。因为我们知道到矩形{(1,1)-(6,3)}中的点到(4,7)的距离最少是4.0，所以我们不需要搜索第一个孩子节点。
但是，如果需要返回3个点呢？
select * from points order by p <-> point '(4,7)' limit 3;
p
-------
(5,5)
(7,8)
(8,6)
(3 rows)
虽然第二个孩子节点包含3个点，但是我们不能直接返回(8,6)。因为第一个孩子节点中的点可能距离(4,7)更近（4.0 < 4.1）。
这个示例说明了非叶子节点对距离函数的要求。通过为第二个孩子节点选取一个更小的距离（选取4.0，而不是选取真实值4.5），降低了效率（搜索算法需要额外搜索一个节点），但是没有破坏算法的正确性。
直到最近，GiST是唯一支持排序操作符的AM。但是这种情况发生变化了：RUM 索引（以后讨论）加入了这个行列，B-tree也不是不可能加入这个行列：Nikita Glukhov的一个patch，正在社区中被讨论。
截止2019年3月，SP-GiST即将在PG 12中支持K-NN，也是由Nikita Glukhov开发。B-tree的patch还在开发中。(译者注：最新版PG的sp-GiST已经支持K-NN查询)
3. 用R-tree索引区间
3.1 示例
这一小节通过示例展示GiST索引在区间数据上的应用，并且介绍排它约束。
对区间数据，比如时间区间（tsrange类型），建立的GiST索引，与上一小节示例的唯一不同就是，节点中的数据表示一个区间，而不是一个矩形。
下面举一个简单的示例：我们想要出租一套房子，并且用一张表表示每次预定的时间区间。
create table reservations(during tsrange);
insert into reservations(during) values
('[2016-12-30, 2017-01-09)'),
('[2017-02-23, 2017-02-27)'),
('[2017-04-29, 2017-05-02)');
create index on reservations using gist(during);
这个索引可以加速下面的查询：
select * from reservations where during && '[2017-01-01, 2017-04-01)';
during
-----------------------------------------------
["2016-12-30 00:00:00","2017-01-08 00:00:00")
["2017-02-23 00:00:00","2017-02-26 00:00:00")
(2 rows)
explain (costs off) select * from reservations where during && '[2017-01-01, 2017-04-01)';
QUERY PLAN
------------------------------------------------------------------------------------
Index Only Scan using reservations_during_idx on reservations
Index Cond: (during && '["2017-01-01 00:00:00","2017-04-01 00:00:00")'::tsrange)
(2 rows)
&&操作符表示区间相交；查询必须返回所有与给定区间相交的区间。对这种操作符，一致性函数的定义决定给定的区间是否与内部节点或叶子节点中的行相交。
注意，这并不表示以某种顺序查询到区间，尽管区间类型有比较操作符。我们可以对区间建立btree索引，但是B-tree缺少下面这些操作符，会使得我们很难处理区间数据:
select amop.amopopr::regoperator, amop.amoppurpose, amop.amopstrategy
from pg_opclass opc, pg_opfamily opf, pg_am am, pg_amop amop
where opc.opcname = 'range_ops'
and opf.oid = opc.opcfamily
and am.oid = opf.opfmethod
and amop.amopfamily = opc.opcfamily
and am.amname = 'gist'
and amop.amoplefttype = opc.opcintype;
amopopr | amoppurpose | amopstrategy
-------------------------+-------------+--------------
@>(anyrange,anyelement) | s | 16 contains element
<<(anyrange,anyrange) | s | 1 strictly left
&<(anyrange,anyrange) | s | 2 not beyond right boundary
&&(anyrange,anyrange) | s | 3 intersects
&>(anyrange,anyrange) | s | 4 not beyond left boundary
>>(anyrange,anyrange) | s | 5 strictly right
-|-(anyrange,anyrange) | s | 6 adjacent
@>(anyrange,anyrange) | s | 7 contains interval
<@(anyrange,anyrange) | s | 8 contained in interval
=(anyrange,anyrange) | s | 18 equals
(10 rows)
(除了等于操作符被B-tree包含之外，其它操作符在B-tree中都不存在)
3.2 内部结构
我们仍然可以使用gevel插件查看它的内部结构，只需要在调用gist_print时对数据类型进行转换：
select level, a from gist_print('reservations_during_idx')
as t(level int, valid bool, a tsrange);
level | a
-------+-----------------------------------------------
1 | ["2016-12-30 00:00:00","2017-01-09 00:00:00")
1 | ["2017-02-23 00:00:00","2017-02-27 00:00:00")
1 | ["2017-04-29 00:00:00","2017-05-02 00:00:00")
(3 rows)
3.3 排它约束
使用GiST索引可以实现排它约束（EXCLUDE）。
排它约束保证表中的任意两行数据在某些列上都不能有某种相关性（由用户指定相关性的操作符）。如果操作符是相等操作符，那么我们就得到了唯一约束：任意两行数据在某些列上互不相等。
排它约束由索引提供支持，就像唯一约束一样。我们可以选择满足下列条件的任意操作符：
- 被AM支持 —— can_exclude属性为真（例如，btree，GiST，SP-GiST，但是不包括GIN）。
- 符合交换律，也就是说： a operator b 与 b operator a的结果相同。
下面列出了一些可被使用的策略和操作符的示例（操作符可能有不同的名称，也可能不适用于所有数据类型）：
- 适合B-tree的比较策略:
- equals =
- 适合GiST和SP-GiST的操作符:
- intersection &&
- coincidence ~=
- adjacency -|-
我们可以在排它约束中使用等于操作符，但是这在实际中并没有意义，因为直接使用唯一约束会更加高效。这就是我们在介绍B-tree时没有介绍排它约束的原因。
3.3.1 示例
下面举一个排它约束的例子，它不允许预定的时间互相重叠。
先创建排它约束，然后插入一行数据：
alter table reservations add exclude using gist(during with &&);
insert into reservations(during) values ('[2017-06-10, 2017-06-13)');
当尝试插入一行与[2017-06-10, 2017-06-13)有重叠的区间时，会直接报错：
insert into reservations(during) values ('[2017-05-15, 2017-06-15)');
ERROR: conflicting key value violates exclusion constraint "reservations_during_excl"
DETAIL: Key (during)=(["2017-05-15 00:00:00","2017-06-15 00:00:00")) conflicts with existing key (during)=(["2017-06-10 00:00:00","2017-06-13 00:00:00")).
3.3.2 btree_gist插件
下面让示例变得更复杂一点：我们将要出租多套房子，每套房子的多个预定时间不重叠即可，不同房子的预定时间可以重叠。
alter table reservations add house_no integer default 1;
我们需要更改排它约束，让它同时考虑房子的编号。但是，GiST并不支持整数类型的相等操作符：
alter table reservations drop constraint reservations_during_excl;
alter table reservations add exclude using gist(during with &&, house_no with =);
ERROR: data type integer has no default operator class for access method "gist"
HINT: You must specify an operator class for the index or define a default operator class for the data type.
在这种场景下，btree_gist插件就派上用场了，它对B-tree固有的操作符增加了GiST功能。GiST本身就支持任意操作符，为什么不让它支持>、>=、=、<=、<呢？
create extension btree_gist;
alter table reservations add exclude using gist(during with &&, house_no with =);
现在，我们不能在同一个时间段内预定第一套房：
insert into reservations(during, house_no) values ('[2017-05-15, 2017-06-15)', 1);
ERROR: conflicting key value violates exclusion constraint "reservations_during_house_no_excl"
但是可以在相交的时间段内预定第二间房
insert into reservations(during, house_no) values ('[2017-05-15, 2017-06-15)', 2);
注意，虽然GiST在某种程度上可以支持>、>=、=、<=、<，但是B-tree的效率更高。所以，仅仅在必须的时候才应该这样做，就像本例一样。
4. 使用RD-tree进行全文检索
4.1 全文检索简介
首先简要介绍一下PG中的全文检索。
全文检索的任务就是从一堆文档中找出符合查询的文档。如果有很多文档符合条件，需要找出最佳匹配的文档，本文不讨论这个话题。
为了支持查询，首先把一个文档转换成tsvector类型，它包含一系列词素和它们在文档中出现的位置。词素就是一系列单词，这些单词已经被处理过，具有适合查询的形式。例如，统一转换成小写，去掉可变后缀等。
select to_tsvector('There was a crooked man, and he walked a crooked mile');
to_tsvector
-----------------------------------------
'crook':4,10 'man':5 'mile':11 'walk':8
(1 row)
可以看到有些词被直接丢弃了（there, was, a, and, he），因为它们在文档中出现的频率很高，搜索这些词通常没有意义。所有这些转换规则都可以被定制，这是另外一话题，本文不再讨论。
查询使用另外一个类型表示：tsquery。简要来说，查询包含一个或由几个条件连接起来的词素：与 &, 或 |, 非 !。我们可以使用小括号表示优先级。
select to_tsquery('man & (walking | running)');
to_tsquery
----------------------------
'man' & ( 'walk' | 'run' )
(1 row)
全文检索中，只用了一个操作符（@@，匹配操作符）。
select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (walking | running)');
?column?
----------
t
(1 row)
select to_tsvector('There was a crooked man, and he walked a crooked mile') @@ to_tsquery('man & (going | running)');
?column?
----------
f
(1 row)
现在有这些知识已经够用了。我们将在下一篇讨论GIN索引时，再深入讨论全文检索。
4.2 RD-trees
为了更快地进行全文检索，首先，表中应该直接存储tsvector类型的列（为了避免每次搜索时，都做一些复杂的转换）。其次，必须在这一列上创建一个索引，其中一个选择就是GiST。
create table ts(doc text, doc_tsv tsvector);
create index on ts using gist(doc_tsv);
insert into ts(doc) values
('Can a sheet slitter slit sheets?'),
('How many sheets could a sheet slitter slit?'),
('I slit a sheet, a sheet I slit.'),
('Upon a slitted sheet I sit.'),
('Whoever slit the sheets is a good sheet slitter.'),
('I am a sheet slitter.'),
('I slit sheets.'),
('I am the sleekest sheet slitter that ever slit sheets.'),
('She slits the sheet she sits on.');
update ts set doc_tsv = to_tsvector(doc);
当然，使用trigger将文档转换成tsvector更好一些。
select * from ts;
-[ RECORD 1 ]----------------------------------------------------
doc | Can a sheet slitter slit sheets?
doc_tsv | 'sheet':3,6 'slit':5 'slitter':4
-[ RECORD 2 ]----------------------------------------------------
doc | How many sheets could a sheet slitter slit?
doc_tsv | 'could':4 'mani':2 'sheet':3,6 'slit':8 'slitter':7
-[ RECORD 3 ]----------------------------------------------------
doc | I slit a sheet, a sheet I slit.
doc_tsv | 'sheet':4,6 'slit':2,8
-[ RECORD 4 ]----------------------------------------------------
doc | Upon a slitted sheet I sit.
doc_tsv | 'sheet':4 'sit':6 'slit':3 'upon':1
-[ RECORD 5 ]----------------------------------------------------
doc | Whoever slit the sheets is a good sheet slitter.
doc_tsv | 'good':7 'sheet':4,8 'slit':2 'slitter':9 'whoever':1
-[ RECORD 6 ]----------------------------------------------------
doc | I am a sheet slitter.
doc_tsv | 'sheet':4 'slitter':5
-[ RECORD 7 ]----------------------------------------------------
doc | I slit sheets.
doc_tsv | 'sheet':3 'slit':2
-[ RECORD 8 ]----------------------------------------------------
doc | I am the sleekest sheet slitter that ever slit sheets.
doc_tsv | 'ever':8 'sheet':5,10 'sleekest':4 'slit':9 'slitter':6
-[ RECORD 9 ]----------------------------------------------------
doc | She slits the sheet she sits on.
doc_tsv | 'sheet':4 'sit':6 'slit':2
索引的结构应该是什么样呢？直接使用R-tree肯定不行，因为没办法为文档定义一个矩形框。但是，我们可以为把这种方法在集合类型上稍作改动，称作RD-tree（RD是Russian Doll的意思）。这种场景下，集合的元素是词素。
RD-tree的一个思想就是把矩形框用集合替代，也就是说，一个集合可以包含其它子集。
一个重要的问题是怎样把集合表示成索引的行。最直接的方式是直接枚举集合中的所有元素，类似下面这样：
假如使用doc_tsv @@ to_tsquery(‘sit’)搜索，我们可以只搜索包含sit词素的节点：
这种表示有很大的问题。文档中词素的数量可能会很大，所以索引行就会很大，导致索引行被存储在toast表中，使得索引非常低效。即使文档中包含很少的词素，集合的并集也会很大：越靠近root的节点，索引行越大。
这种表示形式有时也会被使用，但是被用在其它类型上。对全文检索来说，使用一种更紧凑的结构 —— 被称作签名树。它的思想与Bloom filer非常相似。
每个词素可以被表示成一个签名：一个比特串中只有一个1，其它位全是0。1的位置由词素的hash值决定。
对所有词素的签名做OR操作的结果，就是文档的签名。
假设有下列词素及其签名：
could 1000000
ever 0001000
good 0000010
mani 0000100
sheet 0000100
sleekest 0100000
sit 0010000
slit 0001000
slitter 0000001
upon 0000010
whoever 0010000
每个文档的签名如下：
Can a sheet slitter slit sheets? 0001101
How many sheets could a sheet slitter slit? 1001101
I slit a sheet, a sheet I slit. 0001100
Upon a slitted sheet I sit. 0011110
Whoever slit the sheets is a good sheet slitter. 0011111
I am a sheet slitter. 0000101
I slit sheets. 0001100
I am the sleekest sheet slitter that ever slit sheets. 0101101
She slits the sheet she sits on. 0011100
索引树可以表示成这样：
这种方法的优势非常明显：每个索引行的大小都相同，索引非常紧凑。缺点也很明显：压缩使得精度降低。
考虑相同的搜索条件doc_tsv @@ to_tsquery(‘sit’)。首先计算出查询文档的签名：0010000。一致性函数必须返回所有符合条件的孩子节点，只要它至少包含查询签名的至少一位。
可以看出，和上面的搜索过程相比，这次需要搜索更多节点，这是由假阳性引起的。例如，whoever的签名与sit相同。需要强调的是，这个搜索过程没有假阴性出现，也就是说，我们不会遗漏任何符合条件的文档。
另外，不同的文档也可能会有相同的签名：在我们的例子中，“I slit a sheet, a sheet I slit”和“I slit sheets”的签名相同，都是0001100。如果索引的叶子节点没有保存tsvector的值，索引本身就会给出假阳性的结果。当然，这种情况下，AM可以要求通用索引引擎使用基表上的值进行recheck。所以用户不会看到假阳性的结果。但是这会降低查询的性能。
实际上，PG中的签名使用124字节的串表示，而不是示例中的7位，所以假阳性发生的频率比示例中要低的多。但是，现实中，索引的文档数量也要多很多。为了减少索引假阳性的数量，PG的实现有些诡异：仅当tsvector的大小不太大时（比1/16个页面稍微小一点，在默认8K页面的配置中，大约500字节），它才会被存储在叶子节点中。
4.3 示例
本小节使用pgsql-hackers的邮件列表数据展示GiST索引在全文检索中真正的工作过程。示例中使用的邮件列表共有356125条消息，每条消息包含发送日期、主题、作者、文本。
select * from mail_messages order by sent limit 1;
-[ RECORD 1 ]------------------------------------------------------------------------
id | 1572389
parent_id | 1562808
sent | 1997-06-24 11:31:09
subject | Re: [HACKERS] Array bug is still there....
author | "Thomas G. Lockhart" <Thomas.Lockhart@jpl.nasa.gov>
body_plain | Andrew Martin wrote: +
| > Just run the regression tests on 6.1 and as I suspected the array bug +
| > is still there. The regression test passes because the expected output+
| > has been fixed to the *wrong* output. +
| +
| OK, I think I understand the current array behavior, which is apparently+
| different than the behavior for v1.0x. +
...
给这张表添加tsvector列，并且建立索引。这里我们把所有列连接起来，用来说明文档不是仅能使用一个列，而是可以由任意不同的部分组成。
alter table mail_messages add column tsv tsvector;
update mail_messages
set tsv = to_tsvector(subject||' '||author||' '||body_plain);
NOTICE: word is too long to be indexed
DETAIL: Words longer than 2047 characters are ignored.
...
UPDATE 356125
create index on mail_messages using gist(tsv);
一些单词由于太长而被丢弃了，不过索引最终还是建立成功了，并且可以支持查询：
explain (analyze, costs off)
select * from mail_messages where tsv @@ to_tsquery('magic & value');
QUERY PLAN
----------------------------------------------------------
Index Scan using mail_messages_tsv_idx on mail_messages
(actual time=0.998..416.335 rows=898 loops=1)
Index Cond: (tsv @@ to_tsquery('magic & value'::text))
Rows Removed by Index Recheck: 7859
Planning time: 0.203 ms
Execution time: 416.492 ms
(5 rows)
可以看出共有989行满足条件，AM因为假阳性额外返回了7859行，都被索引引擎过滤掉了。
4.4 内部结构
为了分析索引的内部结构，我们仍然使用gevel插件：
select level, a
from gist_print('mail_messages_tsv_idx')
as t(level int, valid bool, a gtsvector)
where a is not null;
level | a
-------+-------------------------------
1 | 992 true bits, 0 false bits
2 | 988 true bits, 4 false bits
3 | 573 true bits, 419 false bits
4 | 65 unique words
4 | 107 unique words
4 | 64 unique words
4 | 42 unique words
...
gtsvector类型的值中存放了签名，也可能存储了tsvector。如果存储了tsvector，则输出了词素（unique words）的数量。否则，输出了签名中0和1的数量。
可以看出，根节点的签名都为1，也就是说这一层根本就没用。第二层用处也不大（只有4位为0）。
5. 属性
下面展示GiST AM的属性（查询语句在前几篇文章中已有介绍）：
amname | name | pg_indexam_has_property
--------+---------------+-------------------------
gist | can_order | f
gist | can_unique | f
gist | can_multi_col | t
gist | can_exclude | t
可以看出，GiST所以不能对数据排序，不支持创建唯一索引，不支持多列索引，支持排它约束。
AM能否支持K-NN中的排序，用amcanorderbyop（不是can_order）表示，GiST索引的这个属性为true。
索引层面的属性：
name | pg_index_has_property
---------------+-----------------------
clusterable | t
index_scan | t
bitmap_scan | t
backward_scan | f
下面展示具体索引列上的属性，有一些属性依赖操作符：
name | pg_index_column_has_property
--------------------+------------------------------
asc | f
desc | f
nulls_first | f
nulls_last | f
orderable | f
search_array | f
search_nulls | t
可以看出：它不支持排序，不能查询数组，不索引NULL值。
但是剩下的两个属性，distance_orderable和returnable，取决于所使用的操作符类。例如，对点来说：
name | pg_index_column_has_property
--------------------+------------------------------
distance_orderable | t
returnable | t
distance_orderable属性为t，表示支持K-NN查询。returnable属性为t表示支持Index Only Scan。虽然索引的叶子节点存储的是矩形，而不是点，但是AM仍然可以返回所需的点。
对区间类型来说，不支持K-NN查询：
name | pg_index_column_has_property
--------------------+------------------------------
distance_orderable | f
returnable | t
对全文检索来说，二者都不支持：
name | pg_index_column_has_property
--------------------+------------------------------
distance_orderable | f
returnable | f
因为叶子节点存放的仅仅是签名，并没有原始的数据，就像Hash索引一样。
6. 其它数据类型
最后，介绍GiST索引支持的一些其它数据类型：
PG内置支持inet类型，用来存储IP地址信息。所有其它的类型都需要借助插件：
cube插件提供了cube数据类型，用来支持多维立方体。这种数据类型，就像平面上的地理数据类型一样，支持R-tree，支持K-NN查询。
seg插件提供了seg数据类型，它可以表示带边界的区间，并且可以指定精度。这种数据类型支持R-tree。
intarray插件扩展了整形数组的功能，为它们增加了GiST支持。它实现了两个操作符类：gist__int_ops和gist__bigint_ops。
ltree插件增加了ltree数据类型，支持RD-tree。
pg_trgm增加了一个特殊的操作符类gist_trgm_ops，用来支持全文检索。