9.1第52章

52.1. 介绍

GiST 的意思是通用的搜索树（Generalized Search Tree）。 它是一种平衡的，树状结构的访问方法，在系统中起一个基础的模版，然后可以 使用它实现任意索引模式。B+-trees，R-trees 和许多其它的索引模式都可以用 GiST 实现。

GiST 的一个优点是它允许一种客户化的数据类型和合适的 访问方法一起开发，并且是由该数据类型范畴里的专家，而不是数据库专家开发。

有些信息是从加州大学伯克力分校的 GiST 项目网站 和 Marcel Kornacker 的论文，Access Methods for Next-Generation Database Systems 中派生的。PostgreSQL 里的 GiST 实现目前主要是 Teodor Sigae 和 Oleg Bartunov 维护的， 在他们的网站上有更多信息。

52.2. 扩展性

通常，实现一种新的索引访问方法意味着大量的艰苦工作。我们必须理解数据库 的内部工作机制，比如锁的机制和预写日志。GiST 接口有 一个高层的抽象，只要求访问方法的实现者实现被访问的数据类型的语意。 GiST 层本身会处理并发，日志和搜索树结构的任务。

我们不要把这个扩展性和其它标准搜索树的扩展性混淆在一起，比如它们所能处理的 数据等方面。比如，PostgreSQL 支持可以扩展的 B+-trees 和 R-trees。这就意味着呢可以用 PostgreSQL 在任意你需要的数据类型上建立 B+-tree 或者 R-tree。但是 B+-trees 只支持范围谓词 （(<，=，>）， 而 R-trees 只支持 n-D （n－维）范围查询（包含，被包含，相等）。

所以，如果你用 PostgreSQL B+-tree 索引了一个图象 集，那么你就只能发出类似"图象 x 和 图象 y 相等吗"， "图象 x 是不是比图象 y 小" 和 "图象 x 是否大于图象 y"？这样的查询。 根据你在这个环境下定义的"等于"，"小于"，"大于" 的含义，上面这些查询可能有意义。但是，使用一个基于 GiST 的索引， 你可以创建一些方法来发出和域相关的问题，比如"找出所有马的图象" 或者"找出所有曝光过头的图象"。

要让一种 GiST 访问模式跑起来的方法只是实现七个用户定义 的方法，这七个方法定义了树里面的键字的行为。当然，为了支持那些怪异的查询，这些方法 也会相当怪异，但是对于所有标准的查询（B+-trees，R-trees 等），他们是相当直接的。 简单说，GiST 组合了扩展性和通用性，以及代码复用和一个干净的界面。

52.3. 实现

一个用于 GiST 的索引操作符表必须提供的 七个方法：

• consistent
  给出一个在树的数据页上的谓词 p，和一个用户查询 q， 如果对于一个给定的数据项，p 和 q 都很明确地不能为真，那么这个方法将返回假。
• union
  这个方法合并树中的信息。给出一个条目的集合，这个函数生成一个新的谓词， 这个谓词对所有这些条目都为真。
• compress
  将数据项转换成一个适合于在一个索引页里面物理存储的格式。
• decompress
  compress 方法的反方法。把一个数据项的索引表现形式 转换成可以由数据库操作的格式。
• penalty
  返回一个表示将新条目插入树中特定分支需要的"开销"的数值。 项将会按照树中最小 penalty 的路径插下去。
• picksplit
  如果需要分裂一个页面的时候，这个函数决定页面中哪些条目保存呆旧页面里， 而哪些移动到新页面里。
• same
  如果两个条目相同，返回真，否则返回假。

49.4. 例子

PostgreSQL 源代码版本包括好几个使用　GiST 实现的索引方法。核心系统目前为某些内置的几何数据类型提供 R-Tree 的等效功能 （参阅 src/backend/access/gist/gistproc.c）。 下面的 contrib 模块也包含 GiST 操作符表：

• btree_gist
  好几种类型的 B-Tree 等效
• cube
  用于多维立方体的索引
• intarray
  用于一维 int4 数组值的 RD-Tree
• ltree
  用于树状结构的索引
• pg_trgm
  使用 trigram 匹配的文本相似查找
• seg
  用于"漂浮范围（float range）"的索引
• tsearch2
  全文索引

49.5. 崩溃恢复

通常，重放 WAL 日志就足以再数据库崩溃之后恢复 GiST 索引的完整性。 不过，还存在一些边角的情况，这些时候索引状态无法完整地重建。 这时候索引从作用上仍然是正确的，但是可能会导致一些性能的降低。 在发生这种情况的时候，索引可以通过 VACUUM 其所有表来修复， 或者通过使用 REINDEX 重建索引来修复。在某些情况下，单纯的 VACUUM 是不够的，需要 VACUUM FULL 或者 REINDEX。 是否需要这些步骤，可以从崩溃恢复的日志信息中得到提示：

LOG:  index NNN/NNN/NNN needs VACUUM or REINDEX to finish crash recovery

或者在索引插入的时候出现下面的日志信息：

LOG:  index "FOO" needs VACUUM or REINDEX to finish crash recovery

如果一个单纯的 VACUUM 觉得自己无法完整地恢复，它会返回一个提示：

NOTICE:  index "FOO" needs VACUUM FULL or REINDEX to finish crash recovery