9.1第52章

From PostgreSQL wiki

Jump to: navigation, search

Contents

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
Personal tools