26 GiST

PostgreSQL 18 · 基于俄文 PG18 原版的简体中文译本

简体中文 · PG14 English · PG14简体中文 · PG18Русский · PG18

26.1. 总览

GiST（广义搜索树）方法¹ 是平衡搜索树思想的泛化，适用于允许值之间相互定位的数据类型。B-树与有序数据类型紧密绑定，这些类型的值可以进行比较（尽管对这类类型的支撑已实现得极为高效）。而 GiST 允许在操作符类中定义任意的数据分布原则。GiST 索引可以容纳 R-树（用于空间数据）或 RD-树（用于集合），而签名树可用于任何数据类型（例如文本或图像）。

得益于 PostgreSQL 的可扩展性，开发者可以从零开始创建新的访问方法，只需实现索引机制的接口即可。但这不仅需要仔细设计索引逻辑，还需构建页面结构、高效的锁定策略以及日志预写支持。所有这些都要求开发者具备极高的专业水平并付出大量工作量。GiST 通过承担底层问题的解决并实现通用的搜索理念，大大简化了这一任务。要为新数据类型使用 GiST 方法，只需提供一个包含十余个核心函数的操作符类。该类包含了索引逻辑的大部分内容，与 B-树的极简操作符类形成鲜明对比。从这个意义上说，GiST 可以被视为构建新型访问方法的框架。

从最一般的角度来说，叶节点中的每条记录（叶记录）包含一个谓词（逻辑条件）和行版本的标识符。索引键必须满足该谓词；至于该键是否实际包含在该记录中，无关紧要。

每个内部节点中的记录（内部记录）也包含一个谓词和对子节点的引用，且子树中所有索引数据都必须满足该谓词。换句话说，内部记录的谓词包含了所有子记录的谓词。这是一个重要特性，它替代了 B-树的简单有序性，成为 GiST 索引的核心机制。

GiST 树中的搜索使用一致性函数——由操作符类定义的核心函数之一。

一致性函数被调用以检查索引记录的谓词是否与搜索条件（形式为“索引列操作符表达式”）一致。对于内部记录，它决定是否需要进入对应的子树；对于叶记录，它判断索引键是否满足搜索条件。

搜索² 通常从根节点开始。通过一致性函数判断哪些子节点值得进入，哪些不值得。随后，算法对每个选定的子节点重复此过程；与 B-树不同，GiST 索引中可能有多个子节点。由一致性函数在叶节点中筛选出的记录作为结果返回。

搜索始终采用深度优先：算法优先尝试到达某个叶节点。这使得可以更快地开始返回结果，这对于用户仅关心前几行数据时尤为重要。

向 GiST 树中插入新值时，一致性函数不适用，因为需要选择一个特定的叶节点³。该节点的选择应使插入成本最小化，该成本由操作符类的惩罚函数决定。

与 B-树类似，所选节点中可能没有空闲空间，从而导致页面分裂⁴。这需要额外的两个函数：一个决定哪些记录保留在旧节点中，哪些转移到新节点；另一个用于合并两个谓词，以更新父节点的谓词。

新值的添加逐渐扩展现有谓词，而谓词的收缩仅在页面分裂或索引完全重建时发生。这可能导致在频繁更新场景下 GiST 索引性能下降。

由于上述通用性论述可能显得抽象，且大量逻辑依赖于具体操作符类，接下来我将通过几个具体示例进行说明。

26.2. 点的 R 树

第一个示例涉及平面上点（或其他几何对象）的索引。普通 B-树不适用于此类数据，因为点之间未定义比较操作符。当然，可以自行定义这些操作符，但处理几何数据时，我们更关注其他类型的索引支持，我将详细讨论其中两个：在指定区域内查找点，以及查找最近邻。

R-树的核心思想是将平面划分为若干矩形，这些矩形共同覆盖所有待索引的点。索引记录存储一个包围矩形，其谓词可表述为：点位于该包围矩形内部。

R-树的根节点包含多个较大的矩形（可能部分重叠）。子节点包含更小的矩形，嵌套于父节点中；它们共同覆盖所有下层点。

叶节点必须包含实际的索引点，但 GiST 要求所有索引记录的数据类型一致，因此存储的仍是矩形，但“压缩”为点的形式。

通过绘制由机场坐标构建的 R-树三个层级的示意图，可以更直观地理解该结构。为此，我将 demo 数据库中的 airports 表扩展至五千行⁵。为便于观察，索引使用了较低的 fillfactor 参数值，使树结构更深；默认值（90）下仅需一层即可。 90

=> CREATE TABLE airports_big AS
  SELECT * FROM airports_data;
=> COPY airports_big FROM
  '/home/student/internals/airports/extra_airports.copy';
=> CREATE INDEX airports_gist_idx ON airports_big
  USING gist(coordinates) WITH (fillfactor=10);

在顶层，所有点被划分到多个（部分重叠的）包围矩形中：

图 26.1 点的 R-树

在下一层，大矩形进一步分解为更小的矩形：

图 26.2 点的 R-树

在树的最后一个内部层级，每个包围矩形包含的点数恰好等于一页所能容纳的数量：

图 26.3 点的 R-树

说明

图表展示的是 PostgreSQL 13 版本创建的索引结构。版本 14 会预先按 z-顺序对点进行排序 ⁶——这显著提升了索引构建速度，但增加了矩形重叠（降低了搜索效率）。版本 15 中排序算法得到显著改进⁷，但旧图示仍更具直观性。

该索引使用了唯一的点操作符类 point_ops。

同样，可以对矩形或其他任何几何图形进行索引，只需在索引中存储其包围矩形即可。

页面布局

可通过 pageinspect 扩展查看 GiST 索引页面的内容。（v. 14）

与 B-树不同，GiST 索引没有元页面，树的根节点始终位于第零页。若根页面发生分裂，旧根节点被移至独立页面，新根节点占据其位置。

以下是根页面的内容：

=> SELECT ctid, left(keys,65) AS keys
FROM gist_page_items(
  get_raw_page('airports_gist_idx', 0), 'airports_gist_idx'
) \gx
-[ RECORD 1 ]-----------------------------------------------------------
ctid | (216,65535)
keys | (coordinates)=("(27.588300704956055,42.55270004272461),(-179.8769
-[ RECORD 2 ]-----------------------------------------------------------
ctid | (367,65535)
keys | (coordinates)=("(27.826700210571,82.51779937740001),(-176.6459960
-[ RECORD 3 ]-----------------------------------------------------------
ctid | (217,65535)
keys | (coordinates)=("(50.84510040283203,70.871399),(13.922200202941895
-[ RECORD 4 ]-----------------------------------------------------------
ctid | (526,65535)
keys | (coordinates)=("(179.951004028,73.51780700683594),(46.95610046386

这四行记录对应于前一页图示中顶层的四个矩形。

操作符类

可通过以下查询获取实现树中搜索与插入逻辑的核心函数列表⁸：（psql: \dAp）

=> SELECT amprocnum, amproc::regproc
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amproc amop ON amprocfamily = opcfamily
WHERE amname = 'gist'
AND opcname = 'point_ops'
ORDER BY amprocnum;
 amprocnum |         amproc
-----------+------------------------
         1 | gist_point_consistent
         2 | gist_box_union
         3 | gist_point_compress
         5 | gist_box_penalty
         6 | gist_box_picksplit
         7 | gist_box_same
         8 | gist_point_distance
         9 | gist_point_fetch
        11 | gist_point_sortsupport
(9 rows)

我已在上文提及主要的必需函数：

用于搜索时遍历树的一致性函数；
合并函数（注意名称：合并的是矩形）；

用于插入时选择路径的惩罚函数；
用于分裂时分配记录的函数；
用于检查两个键是否相等的函数。

可选函数允许控制数据存储和性能方面的细节。

操作符类 point_ops 支持以下操作符：

=> SELECT amopopr::regoperator, amopstrategy AS st, oprcode::regproc,
  left(obj_description(opr.oid, 'pg_operator'), 19) description
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'gist'
AND opcname = 'point_ops'
ORDER BY amopstrategy;
      amopopr      | st |       oprcode       |     description
-------------------+----+---------------------+---------------------
 <<(point,point)   |  1 | point_left          | is left of
 >>(point,point)   |  5 | point_right         | is right of
 ~=(point,point)   |  6 | point_eq            | same as
 <<|(point,point)  | 10 | point_below         | is below
 |>>(point,point)  | 11 | point_above         | is above
 <->(point,point)  | 15 | point_distance      | distance between
 <@(point,box)     | 28 | on_pb               | point inside box
 <^(point,point)   | 29 | point_below         | deprecated, use <<|
 >^(point,point)   | 30 | point_above         | deprecated, use |>>
 <@(point,polygon) | 48 | pt_contained_poly   | is contained by
 <@(point,circle)  | 68 | pt_contained_circle | is contained by
(11 rows)

仅凭操作符名称难以判断其含义，因此在查询中列出了其对应函数名称和描述。所有操作符均与对象之间的相对位置（“左”、“右”、“上”、“下”、“包含”、“被包含”）或距离有关。（psql: \dAo）

与 B-树相比，GiST 支持更多策略。部分策略编号适用于多个索引类型⁹，部分则通过公式计算（例如编号 28、48 和 68 实质上代表同一策略：矩形、多边形和圆的“包含”关系）。此外，还支持一些已弃用的操作符名称（如 <<| 和 |>>）。

具体操作符类可能并未实现所有可用策略。例如，点类不支持“包含”策略，但具有面积的图形类（如 box_ops、poly_ops 和 circle_ops）则支持该策略。

搜索包含的元素

典型的、由索引加速的查询是获取所有位于指定区域内的点。

例如，查找位于莫斯科中心一纬度范围内的所有机场：

=> SELECT airport_code, airport_name->>'en'
FROM airports_big
WHERE coordinates <@ '<(37.622513,55.753220),1.0>'::circle;
 airport_code |              ?column?
--------------+------------------------------------
 SVO          | Sheremetyevo International Airport
 VKO          | Vnukovo International Airport
 DME          | Domodedovo International Airport
 BKA          | Bykovo Airport
 ZIA          | Zhukovsky International Airport
 CKL          | Chkalovskiy Air Base
 OSF          | Ostafyevo International Airport
(7 rows)
=> EXPLAIN (costs off) SELECT airport_code
FROM airports_big
WHERE coordinates <@ '<(37.622513,55.753220),1.0>'::circle;
                             QUERY PLAN
---------------------------------------------------------------------
 Bitmap Heap Scan on airports_big
   Recheck Cond: (coordinates <@ '<(37.622513,55.75322),1>'::circle)
   -> Bitmap Index Scan on airports_gist_idx
       Index Cond: (coordinates <@ '<(37.622513,55.75322),1>'::ci...
(4 rows)

操作符“包含于” <@ 用于判断点是否位于指定矩形内部。该操作符对应的一致性函数¹⁰ 返回“是”，当且仅当索引记录的矩形与给定矩形有交集。对于存储“压缩”为点的矩形的叶页面，这意味着函数（如同操作符本身）判断点是否位于指定矩形内部。

让我们更详细地分析一个非常简单的示例，如图所示：

图 26.4 区域包含搜索

在这种划分下，索引的结构如下所示：

图 26.5 区域包含搜索

让我们查找图中右侧所示矩形 (1,2)–(4,7) 的内部点。

搜索从根节点开始。给定矩形与 (0,0)–(3,4) 相交，但不与 (5,3)–(9,9) 相交。因此，我们无需进入第二个子树。

在下一层，给定矩形与 (0,3)–(3,4) 相交，并与 (0,0)–(3,2) 相切，因此我们必须检查两个子树。

当我们到达叶节点时，只需遍历其中包含的所有点，并返回满足一致性函数的那些点。

图 26.6 区域包含搜索

B-树搜索总是明确选择一个子节点；而 GiST 搜索可能需要遍历多个子树，尤其是当它们的包围矩形相交时。

插入

在向 R-树插入新键时，插入节点的选择基于惩罚函数，以使包围矩形的面积变化最小¹³。

例如，点 (4,7) 将被添加到矩形 (5,3)–(9,9) 中，因为其面积仅增加 6 个单位，而将 (0,0)–(3,4) 的面积增加 12 个单位。在下一层（叶层）中，出于相同原因，该点将被添加到矩形 (6,6)–(9,9) 中。

图 26.11 插入

假设每页最多容纳三个元素，将发生页面分裂，元素将在两个页面之间重新分配：

图 26.12 插入

在此示例中结果看似显而易见，但一般情况下，分配选择是一个非常复杂的问题。分裂函数首先尝试最小化包围矩形的重叠，优先选择面积较小的矩形，并倾向于在页面间均匀分布点¹⁴。

排它约束

GiST 索引可用于支持排除约束（exclude）。

排除约束保证表中任意两行的指定字段在某个 操作符 意义下不会“匹配”。必须满足以下条件：

排除约束必须由索引方法支持（属性 CAN EXCLUDE）；
操作符必须属于该索引方法的操作符类；
操作符必须是可交换的，即必须满足条件 a 操作符 b = b 操作符 a。

前面讨论的 hash 和 btree 访问方法仅提供一个满足条件的操作符——相等性。使用此操作符时，排除约束等价于唯一性约束，这并无太大用处。（参见 521）

但 gist 方法还有另外两种适用的策略：

相交 — 操作符 &&；
примыкание — оператор -|- (определен для интервалов).

举个例子，创建一个禁止将机场放置得过于接近的约束。该条件可重新表述为：以机场坐标为中心、半径为某值的圆不应相交：

=> ALTER TABLE airports_data ADD EXCLUDE
USING gist (circle(coordinates,0.2) WITH &&);

=> INSERT INTO airports_data(
  airport_code, airport_name, city, coordinates, timezone
) VALUES (
  'ZIA', '{}', '{"en": "Moscow"}', point(38.1517, 55.5533),
  'Europe/Moscow'
);
ERROR:  conflicting key value violates exclusion constraint
"airports_data_circle_excl"
DETAIL:  Key (circle(coordinates, 0.2::double
precision))=(<(38.1517,55.5533),0.2>) conflicts with existing key
(circle(coordinates, 0.2::double
precision))=(<(37.90629959106445,55.40879821777344),0.2>).

创建排除约束时，会自动为其检查创建索引。在本例中，这是一个基于表达式的 GiST 索引。

将问题复杂化。假设允许机场在彼此靠近的情况下共存，但仅限于属于同一城市的情况。解决方案是创建一个新的完整性约束，其表述如下：不允许存在满足以下条件的行对：以机场坐标为中心的圆相交（&&），且城市名称不相等（!=）。

尝试创建此类约束会导致错误，因为不存在文本数据类型的运算符类：

=> ALTER TABLE airports_data
DROP CONSTRAINT airports_data_circle_excl; -- удаляем старое
=> ALTER TABLE airports_data ADD EXCLUDE USING gist (
  circle(coordinates,0.2) WITH &&,
            (city->>'en') WITH !=
);
ERROR:  data type text 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.

但事实上，GiST 可以处理诸如「位于左侧」、「位于右侧」或「相等」之类的策略，这些策略也可应用于普通有序数据类型，如数字或文本字符串。btree_gist 扩展正是为此添加了对 B-树典型操作的 GiST 支持：

=> CREATE EXTENSION btree_gist;
=> ALTER TABLE airports_data ADD EXCLUDE USING gist (
  circle(coordinates,0.2) WITH &&,
            (city->>'en') WITH !=
);
ALTER TABLE

约束已创建。现在由于莫斯科机场之间的距离过近，无法再添加同名城市中的茹科夫斯基机场：

=> INSERT INTO airports_data(
  airport_code, airport_name, city, coordinates, timezone
) VALUES (
  'ZIA', '{}', '{"en": "Zhukovsky"}', point(38.1517, 55.5533),
  'Europe/Moscow'
);
ERROR:  conflicting key value violates exclusion constraint
"airports_data_circle_expr_excl"
DETAIL:  Key (circle(coordinates, 0.2::double precision), (city ->>
'en'::text))=(<(38.1517,55.5533),0.2>, Zhukovsky) conflicts with
existing key (circle(coordinates, 0.2::double precision), (city ->>
'en'::text))=(<(37.90629959106445,55.40879821777344),0.2>, Moscow).

但可以通过将机场所在城市指定为莫斯科来实现添加：

=> INSERT INTO airports_data(
  airport_code, airport_name, city, coordinates, timezone
) VALUES (
  'ZIA', '{}', '{"en": "Moscow"}', point(38.1517, 55.5533),
  'Europe/Moscow'
);
INSERT 0 1

需要注意的是，尽管 GiST 可以处理「大于」、「小于」或「等于」等操作，但 B-树在处理这些操作时效率更高，尤其是在访问值范围时。因此，仅当确实需要 GiST 索引时，才应使用本例中展示的 btree_gist 扩展方法。

属性

访问方法级别属性

=> 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', 'can_include'
]) p(name)
WHERE a.amname = 'gist';
 amname |     name      | pg_indexam_has_property
--------+---------------+-------------------------
 gist   | can_order     | f
 gist   | can_unique    | f
 gist   | can_multi_col | t
 gist   | can_exclude   | t
 gist   | can_include   | t
(5 rows)

不支持值的排序和唯一性。

GiST 索引可以创建包含额外的 include 列。（v. 12）

正如我们所见，索引可以基于多个列构建，并可用于排除约束。

索引级别属性

=>  SELECT p.name, pg_index_has_property('airports_gist_idx', p.name)
FROM unnest(array[
  'clusterable', 'index_scan', 'bitmap_scan', 'backward_scan'
]) p(name);
     name      | pg_index_has_property
---------------+-----------------------
 clusterable   | t
 index_scan    | t
 bitmap_scan   | t
 backward_scan | f
(4 rows)

GiST 索引可用于表的聚簇。

支持两种数据获取方式：逐行获取和位图获取。但 GiST 不支持反向扫描。

列级别属性

大部分列属性在访问方法级别定义，且不会改变：

=> SELECT p.name,
  pg_index_column_has_property('airports_gist_idx', 1, p.name)
FROM unnest(array[
  'orderable', 'search_array', 'search_nulls'
]) p(name);
     name     | pg_index_column_has_property
--------------+------------------------------
 orderable    | f
 search_array | f
 search_nulls | t
(3 rows)

所有与排序相关的属性均被禁用。

GiST 索引允许 NULL 值，但处理效率不高。认为 NULL 值不会扩展其包围矩形；因此插入时，这些值会随机分配到索引树的不同子树中，必须在整个树中搜索它们。

然而，部分列级别属性会根据运算符类的不同而变化。

=> SELECT p.name,
  pg_index_column_has_property('airports_gist_idx', 1, p.name)
FROM unnest(array[
   'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 returnable         | t
 distance_orderable | t
(2 rows)

索引仅可用于索引扫描，因为索引键完全存储在叶节点中。

在这种情况下，如我们所见，运算符类包含用于查找最近邻的距离操作符。到 NULL 值的距离被视为 NULL；这些值将被排在最后（类似于 B-树中的 NULLS LAST）。

但对于范围类型（表示线段，即同几何图形但位于直线上而非平面上）不实现距离操作符，因此对于此类数据类型的索引，该属性将有所不同：

=> CREATE TABLE reservations(during tsrange);

=> CREATE INDEX ON reservations USING gist(during);

=> SELECT p.name,
  pg_index_column_has_property('reservations_during_idx', 1, p.name)
FROM unnest(array[
   'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 returnable         | t
 distance_orderable | f
(2 rows)

26.3. 用于全文检索的 RD 树

关于全文检索

全文搜索的任务 ¹⁵ —— 从一组文档中选出与 搜索查询 匹配的文档。

为搜索目的，文档被转换为特殊类型 tsvector，该类型包含词元及其在文档中的位置。词元是经过转换后便于搜索的单词。例如，默认情况下，单词会被转换为小写并去除可变词尾：

=> SET default_text_search_config = russian;
=> SELECT to_tsvector(
  'И встал Айболит, побежал Айболит. ' ||
  'По полям, по лесам, по лугам он бежит.'
);
                            to_tsvector
--------------------------------------------------------------------
 'айбол':3,5 'беж':13 'встал':2 'лес':9 'луг':11 'побежа':4 'пол':7
(1 row)

所谓的停用词（如“和”、“在”）会被删除，因为它们出现频率过高，无法有效用于搜索。当然，所有这些转换均可自定义。

搜索查询以另一种类型表示——tsquery。查询由一个或多个词元组成，通过逻辑连接词连接：「与」&、「或」|、「非」!。也可使用括号来明确操作优先级。

=> SELECT to_tsquery('Айболит & (побежал | пошел)');
            to_tsquery
----------------------------------
 'айбол' & ( 'побежа' | 'пошел' )
(1 row)

全文搜索仅使用一个 匹配操作符 @@：

=> SELECT amopopr::regoperator, oprcode::regproc, amopstrategy
FROM pg_am am
  JOIN pg_opclass opc ON opcmethod = am.oid
  JOIN pg_amop amop ON amopfamily = opcfamily
  JOIN pg_operator opr ON opr.oid = amopopr
WHERE amname = 'gist'
AND opcname = 'tsvector_ops'
ORDER BY amopstrategy;
       amopopr        |   oprcode   | amopstrategy
----------------------+-------------+--------------
 @@(tsvector,tsquery) | ts_match_vq |            1
(1 row)

该操作符用于判断文档是否与搜索查询匹配。以下是一个简单示例：

=> SELECT to_tsvector('И встал Айболит, побежал Айболит.') @@
  to_tsquery('Айболит & побежать');
 ?column?
----------
 t
(1 row)

这绝非对全文搜索的完整描述，但这些信息已足够理解索引机制。（参见 613）

索引 tsvector 数据

为使全文搜索快速执行，必须使用索引支持 ¹⁶。由于索引的并非文档本身，而是 tsvector 类型的值，因此有两种选择：构建基于表达式的索引（带类型转换），或创建一个独立的 tsvector 类型列并对其进行索引。第一种方法的优点是无需额外存储 tsvector 值，这些值本身对用户无用。但当索引机制需重新检查表中返回的版本标识符时，其速度不如列方法。此时必须为每行重新计算 tsvector 值，而 GiST 索引如我们所见，会重新检查所有行。（参见 613）

构建一个小示例。创建一个包含两个列的表：第一列存储文档，第二列存储 tsvector 值。第二列可通过触发器更新¹⁷，但更方便的做法是将其声明为生成列 ¹⁸：（v. 12）

=> CREATE TABLE ts(
  doc text,
  doc_tsv tsvector GENERATED ALWAYS AS (
    to_tsvector('pg_catalog.russian', doc)
  ) STORED
);
=> CREATE INDEX ts_gist_idx ON ts USING gist(doc_tsv);

说明

之前示例中我使用了带一个参数的 to_tsvector 函数，事先通过参数 default_text_search_config 设置了全文搜索配置。该函数的可变性类别为 STABLE，因为它隐式依赖于参数值。而此处使用的是显式指定配置的函数版本，其可变性类别为 IMMUTABLE，适合用于生成表达式。

向表中插入几行数据：（默认：english）

=> INSERT INTO ts(doc) VALUES
  ('Во поле береза стояла'),  ('Во поле кудрявая стояла'),
  ('Люли, люли, стояла'),     ('Люли, люли, стояла'),
  ('Некому березу заломати'), ('Некому кудряву заломати'),
  ('Люли, люли, заломати'),   ('Люли, люли, заломати'),
  ('Я пойду погуляю'),        ('Белую березу заломаю'),
  ('Люли, люли, заломаю'),    ('Люли, люли, заломаю')
RETURNING doc_tsv;
            doc_tsv
--------------------------------
 'берез':3 'пол':2 'стоя':4
 'кудряв':3 'пол':2 'стоя':4
 'люл':1,2 'стоя':3
 'люл':1,2 'стоя':3
 'берез':2 'заломат':3 'нек':1
 'заломат':3 'кудряв':2 'нек':1
 'заломат':3 'люл':1,2
 'заломат':3 'люл':1,2
 'погуля':3 'пойд':2
 'бел':1 'берез':2 'залома':3
 'залома':3 'люл':1,2
 'залома':3 'люл':1,2
(12 rows)
INSERT 0 12

R-树本身不适用于文档索引，因为其无法定义包围矩形。采用的是该方法的变体——RD-树（俄罗斯套娃，Matryoshka）。该树使用 包围集合 而非包围矩形，即包含所有子集元素的集合。对于全文搜索，该集合由文档的词元组成，但一般情况下集合可以是任意的。

索引记录中表示集合有多种方式。最简单的方式是直接列出集合中的所有元素。其形式可能如下：

图 26.13 tsvector 索引

因此，例如，要查找满足 doc_tsv @@ to_tsquery('стояла') 条件的文档，需进入那些已知其子记录包含词元「стоя」的节点：

图 26.14 tsvector 索引

这种表示方式的问题显而易见。文档中的词元数量可能非常庞大，而页面空间有限。即使每篇文档中唯一词元不多，树的上层节点合并集合后仍可能变得非常大。

为全文搜索采用另一种更紧凑的解决方案——签名树。其思想对接触过布隆过滤器（Bloom filter）的人来说并不陌生。（参见 665）

每个词素都可以表示为其自身的签名：一个固定长度的位串，其中所有位都为零（清除），除了一个位为一（设置）。设置位的编号由词素的哈希函数值决定。

文档的签名是指文档中所有词素签名的按位“或”运算结果。

假设我们为词素分配了如下签名：

词元	签名
бел	`1000000`
берез	`0001000`
залома	`0000010`
заломат	`0010000`
кудряв	`0000100`
люл	`0100000`
нек	`0000100`
погуля	`0000001`
пойд	`0000010`
пол	`0000010`
стоя	`0010000`

表 26.1 词素的签名

那么文档的签名将如下所示：

文档	签名
Во поле береза стояла	`0011010`
Во поле кудрявая стояла	`0010110`
Люли, люли, стояла	`0110000`
Некому березу заломати	`0011100`
Некому кудряву заломати	`0010100`
Люли, люли, заломати	`0110000`
Я пойду погуляю	`0000011`
Белую березу заломаю	`1001010`
Люли, люли, заломаю	`0100010`

表 26.2 文档的签名

在这种情况下，索引树可以表示为：

图 26.15 tsvector 索引

这种方法的优势显而易见：索引条目具有相同且较小的大小，索引变得紧凑。但也有显著的缺点。首先，仅扫描索引变得不可能，因为索引不再存储索引键值，每个返回的标识符都必须通过表进行重新验证。其次，精度丧失：索引可能返回大量误报结果，这些结果随后在重新验证时被过滤掉。

考虑相同的条件 doc_tsv @@ to_tsquery('стояла')。搜索查询的签名计算方式与文档相同，在本例中等于 0010000。一致性函数 ¹⁹ 必须确定所有子节点，其签名包含查询签名中设置的位：

图 26.16 tsvector 索引

与前一个例子相比，这里由于误报触发而遍历了更多的节点。原因是当词素数量很大时，由于其位宽有限，某些词素不可避免地会获得相同的签名。在本例中，词素“стоя”和“заломат”就是如此。这导致同一个签名对应不同的文档；在本例中，“люли, люли, стояла”和“люли, люли, заломати”都具有签名 0110000。

误报降低了索引的效率，但不会危及正确性，因为这种方案中不可能出现漏报，所需值保证不会被遗漏。

当然，在现实中，签名的大小选择得更大。默认使用 124 字节（992 位），因此碰撞概率远低于示例中的情况。如需，可将签名大小设置为最多约 2000 字节，通过 操作符类参数 实现（v. 13）

CREATE INDEX ... USING gist(столбец tsvector_ops(siglen = размер));

此外，如果值足够小 ²⁰（略小于 $\frac{1}{16}$ 页，即标准页约 500 字节），操作符类 tsvector_ops 在索引的叶页面中存储的不是签名，而是 tsvector 值本身。

为了观察索引在真实数据上的工作方式，我们取 pgsql-hackers 邮件列表归档 ²¹。其中包含 356,125 封邮件，每封邮件包含发送日期、主题、作者姓名和正文。

添加一个 tsvector 类型的列并建立索引。此处我将三个值（主题、作者和邮件正文）合并为一个向量，以说明文档可以动态生成，不必存储在单一列中。

=> ALTER TABLE mail_messages ADD COLUMN tsv tsvector
GENERATED ALWAYS AS ( to_tsvector(
  'pg_catalog.english', subject||' '||author||' '||body_plain
) ) STORED;
NOTICE:  word is too long to be indexed
DETAIL:  Words longer than 2047 characters are ignored.
 ...
NOTICE:  word is too long to be indexed
DETAIL:  Words longer than 2047 characters are ignored.
ALTER TABLE
=> CREATE INDEX mail_gist_idx ON mail_messages USING gist(tsv);
=> SELECT pg_size_pretty(pg_relation_size('mail_gist_idx'));
 pg_size_pretty
----------------
 127 MB
(1 row)

在填充列时，部分单词因过大而被丢弃，但最终索引已构建完成，可支持搜索查询：

=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT *
FROM mail_messages
WHERE tsv @@ to_tsquery('magic & value');
                        QUERY PLAN
----------------------------------------------------------
 Index Scan using mail_gist_idx on mail_messages
   (actual rows=898.00 loops=1)
   Index Cond: (tsv @@ to_tsquery('magic & value'::text))
   Rows Removed by Index Recheck: 7852
   Index Searches: 1
(5 rows)

除了 898 行符合条件的记录外，访问方法还返回了 7852 行，这些行通过表的重新验证被过滤掉。增大签名大小可提高精度（从而提高效率），但会牺牲索引的紧凑性：

=> DROP INDEX mail_messages_tsv_idx;
=> CREATE INDEX ON mail_messages
USING gist(tsv tsvector_ops(siglen=248));
=> SELECT pg_size_pretty(pg_relation_size('mail_messages_tsv_idx'));
 pg_size_pretty
----------------
 139 MB
(1 row)
=> EXPLAIN (analyze, costs off, timing off, summary off, buffers off)
SELECT *
FROM mail_messages
WHERE tsv @@ to_tsquery('magic & value');
                        QUERY PLAN
----------------------------------------------------------
 Index Scan using mail_messages_tsv_idx on mail_messages
   (actual rows=898.00 loops=1)
   Index Cond: (tsv @@ to_tsquery('magic & value'::text))
   Rows Removed by Index Recheck: 2057
   Index Searches: 1
(5 rows)

属性

我已展示过访问方法的特性，且大部分特性对所有操作符类都一致。值得关注的是两个列级属性：（参见 574）

=> SELECT p.name,
  pg_index_column_has_property('mail_messages_tsv_idx', 1, p.name)
FROM unnest(array[
   'returnable', 'distance_orderable'
]) p(name);
        name        | pg_index_column_has_property
--------------------+------------------------------
 returnable         | f
 distance_orderable | f
(2 rows)

索引失去了参与仅索引扫描的能力，因为无法通过签名恢复原始值。在本例中这并无大碍：tsvector 值仅用于搜索，我们真正关心的是文档本身。

对于 tsvector_ops 类，排序操作符未定义。

26.4. 其他数据类型

我仅讨论了两个最具代表性的例子。它们表明，GiST 方法虽然基于平衡树，但通过操作符类的不同实现，可以适用于不同类型的数据。提及 GiST 索引时，必须明确操作符类，因为它显著影响索引的属性和特征。

以下是当前由 GiST 访问方法支持的其他一些数据类型。

几何类型。 除了点之外，GiST 索引还可用于其他几何类型：矩形、圆、多边形。这些类型在索引目的中均以它们的包围矩形表示。

扩展 cube 添加了同名数据类型，用于表示多维立方体，这些立方体通过 R-树进行索引。索引中使用的是相应维度的包围平行六面体，而非包围矩形。

范围类型。 PostgreSQL 的标准类型包括数值范围和时间范围，如 int4range 或 tstzrange²²。可以使用 CREATE TYPE AS RANGE 命令定义自定义范围类型。

无论标准还是用户定义的任何范围类型，均通过相同的操作符类 range_ops²³ 由 GiST 索引支持。索引使用一维 R-树：此时包围矩形被转换为包围区间。

多范围类型也受支持；使用操作符类 multirange_ops。此时包围范围覆盖多范围值中包含的所有范围。（v. 14）

扩展 seg 提供了同名数据类型，用于表示边界具有特定精度的区间。该类型不属于范围类型，但本质上是范围类型，并以相同方式索引。

有序类型。 再次提醒，扩展 btree_gist 提供了 GiST 访问方法的多个操作符类，适用于大量通常使用 B-树索引的有序类型数据。这些操作符类可用于创建复合索引，当某一列类型不被 B-树支持时。

网络地址。 数据类型 inet 内置了 GiST 支持，由操作符类 inet_ops²⁴ 实现。

整数数组。 扩展 intarray 使整数数组更具功能性，并为其添加了 GiST 支持。有两个操作符类。对于小数组，可使用 gist__int_ops，它实现的是在索引条目中完整表示键的 RD-树。对于大数组，更适合使用更紧凑但精度较低的签名 RD-树，由 gist__bigint_ops 实现。

说明

操作符类名称中的“额外”下划线出现，是因为下划线开头的名称用于基本类型的数组。例如，对于整数数组，除了更常见的 int4[] 表示法外，还可使用 _int4 类型。不过，_int 和 _bigint 类型并不存在。

标签树。 扩展 ltree 添加了同名数据类型，用于表示带标签的树形结构。GiST 支持通过签名 RD-树实现，由操作符类 gist_ltree_ops 提供 ltree 类型值的支持，以及由 gist__ltree_ops 提供此类类型数组的支持。

键值存储。 扩展 hstore 提供了 hstore 数据类型，用于存储“键–值”对。操作符类 gist_hstore_ops 通过签名 RD-树实现索引支持。

三元组。 扩展 pg_trgm 添加了 gist_trgm_ops 类，实现基于相似性比较和模式搜索的索引支持。（参见 630）

postgrespro.ru/docs/postgresql/18/gist; backend/access/gist/README. ↩︎
backend/access/gist/gistget.c, 函数 gistgettuple. ↩︎
backend/access/gist/gistutil.c, 函数 gistchoose. ↩︎
backend/access/gist/gistsplit.c, 函数 gistSplitByKey. ↩︎
文件可通过以下地址获取 edu.postgrespro.ru/internals-18/extra_airports.copy (数据来自网站 openflights.org). ↩︎
commitfest.postgresql.org/29/2276. ↩︎
commitfest.postgresql.org/37/3488. ↩︎
postgrespro.ru/docs/postgresql/18/gist-extensibility. ↩︎
include/access/stratnum.h. ↩︎
backend/access/gist/gistproc.c, 函数 gist_point_consistent. ↩︎
backend/utils/adt/geo_ops.c, 函数 point_distance. ↩︎
backend/utils/adt/geo_ops.c, 函数 box_closest_point. ↩︎
backend/access/gist/gistproc.c, 函数 gist_box_penalty. ↩︎
backend/access/gist/gistproc.c, 函数 gist_box_picksplit. ↩︎
postgrespro.ru/docs/postgresql/18/textsearch. ↩︎
postgrespro.ru/docs/postgresql/18/textsearch-indexes. ↩︎
postgrespro.ru/docs/postgresql/18/textsearch-features#TEXTSEARCH-UPDATE-TRIGGERS. ↩︎
postgrespro.ru/docs/postgresql/18/ddl-generated-columns. ↩︎
backend/utils/adt/tsgistidx.c, 函数 gtsvector_consistent. ↩︎
backend/utils/adt/tsgistidx.c, 函数 gtsvector_compress. ↩︎
edu.postgrespro.ru/mail_messages.sql.gz. ↩︎
postgrespro.ru/docs/postgresql/18/rangetypes. ↩︎
backend/utils/adt/rangetypes_gist.c. ↩︎
backend/utils/adt/network_gist.c. ↩︎