本节简单介绍了PostgreSQL中的GiST索引,包括GiST索引的基础知识和结构等. **简介** GiST是*generalized search tree通用搜索树*的简称,与Btree类似,是平衡搜索树.与Btree不同的地方在于,Btree严格与比较语义相关,支持大于/小于/等于等操作符,但对于地理信息数据,文本文件,图像等数据Btree则是无能无力.GiST索引方法可以处理这些数据,它允许定义一个规则在一个平衡的树中分布任意类型的数据，并允许定义一个方法来使用这个表示来让某些操作符访问。 **结构** GiST是由节点pages组成的高度平衡(height-balanced)树。节点由索引行组成。 叶子节点的每一个(leaf row)通常来说包含某些谓词(布尔表达式)以及实际数据行(TID)的引用.索引数据必须满足该谓词. 内部节点的每一个行(internal row)同样包含谓词以及子字节的引用,所有child subtree中已索引的数据必须满足该谓词.换句话来说,内部行的谓词组合了所有child rows的谓词.GiST索引的这一重要特性取代了Btree的简单排序。 在GiST中检索使用特定的*consistency function(即consistent)*,consistent是PG定义的接口函数之一,对于支持的op family有自己的实现方法.对于每一个索引行都会调用consistent函数来判定该行的谓词是否与搜索谓词consistent(被称为索引域操作符表达式).对于内部行,该函数实际上会判定是否需要下降到相应的子树中进行检索. 搜索从root节点开始,*consistency function*函数找出哪些子节点(可能有多个)可以进入,而哪些不需要,对于每一个进入的子节点进行递归处理.如果是子节点,那么选中的行将被返回. 搜索使用深度优先:算法首先尝试到达叶子节点,这样可以尽可能快的返回第一个结果行(类似于Oracle的HINT : first_rows). 下面以Point为例说明.该例中,Index有3个层次: *Level one: two large intersecting rectangles are visible*  *Level two: large rectangles are split into smaller areas*  *Level three: each rectangle contains as many points as to fit one index page*  下面是只有一个Leve的例子:  相应的数据表&数据如下: ``` testdb=# drop table if exists points; DROP TABLE testdb=# create table points(p point); CREATE TABLE testdb=# insert into points(p) values testdb-# (point '(1,1)'), (point '(3,2)'), (point '(6,3)'), testdb-# (point '(5,5)'), (point '(7,8)'), (point '(8,6)'); INSERT 0 6 testdb=# testdb=# create index on points using gist(p); CREATE INDEX ``` 索引结构如下:  执行查询: ``` testdb=# set enable_seqscan = off; SET testdb=# 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) ``` 期望得到的结果是:  索引扫描过程:  **参考资料** [Indexes in PostgreSQL — 5 (GiST)](https://habr.com/en/company/postgrespro/blog/444742/)