GIST索引

1.概述

Gist(Generalized Search Tree)，即通用搜索树

和btree一样，也是平衡的搜索树。

和btree不同的是，btree索引常常用来进行例如大于、小于、等于这些操作中，而在实际生活中很多数据其实不适用这种场景，例如地理数据、图像等等。如果我们想要查询在某个地方是否存在某一点，即判断地理位置的"包含"那么我们就可以使用gist索引了。
因为gist索引允许定义规则来将任意类型的数据分布到一个平衡的树中，并且允许定义一个方法使用此表示形式来让某些运算符访问。例如，对于空间数据，GiST索引可以使用 R树，以支持相对位置运算符（位于左侧，右侧，包含等），而对于树形图，R树可以支持相交或包含运算符。

2. 结构

GiST是由节点页面组成的高度平衡树。节点由索引行组成。

通常，叶节点的每一行(leafrow)都包含一些谓词（布尔表达式）和对表行（TID）的引用。索引数据(key)必须符合此谓词。

内部节点的每一行(internalrow)还包含一个谓词和对子节点的引用，并且子树的所有索引数据都必须满足此谓词。换句话说，内部行的谓词包括所有子行的谓词。GiST索引的这一重要特征取代了 B-tree的简单排序。

在GiST树中搜索使用专门的一致性函数（«consistent»）—由接口定义并以其自己的方式实现的函数之一，适用于每个受支持的操作符族。

为索引行调用一致性函数，并确定该行的谓词是否与搜索谓词一致（指定为“ 索引字段运算符表达式 ”）。对于内部行，此函数确定是否需要下降到相应的子树，而对于叶行，此函数确定索引的数据是否满足谓词。

搜索从根节点开始，就像普通的树搜索一样。一致性函数允许找出有意义的子节点（可能有多个）可以输入，而哪些子节点不需要输入。然后对找到的每个子节点重复该算法。如果节点是叶子节点，则一致性函数选择的行将作为结果之一返回。

搜索是深度优先的：算法首先尝试到达一个叶子节点。这样可以尽可能快地返回第一个结果（如果用户只对几个结果感兴趣，而不对所有结果感兴趣，那么这一点可能很重要）。

让我们再次注意，一致性函数与«greater», «less», 或«equal» 运算符无关。一致性函数的语义可能完全不同，因此，假定索引不以特定顺序返回值。

我们不会讨论GiST中值的插入和删除算法：其他一些接口函数执行这些操作。然而，有一点很重要。将新值插入索引后，将选择该值在树中的位置，以便尽可能少地扩展其父行的谓词（理想情况下完全不扩展）。但是，当删除一个值时，父行的谓词不再减少。仅在以下情况下会发生这种情况：将页面分为两部分（当页面没有足够的空间来插入新的索引行时），或者从头开始重新创建索引（使用REINDEX或VACUUM FULL命令）。因此，GiST索引用于频繁更改数据的效率会随着时间的推移而降低。

此外，我们将考虑一些针对各种数据类型和GiST有用属性的索引示例：

1. 点（和其他几何实体）和邻近搜索。

2. 区间和排除约束。

3. 全文搜索。

3. 原理

• 《PostgreSQL独门绝招之一 GIN , GiST , SP-GiST , RUM 索引原理与技术背景 》：https://www.sohu.com/a/123404525_465959
• 《PostgreSQL 百亿地理位置数据 近邻查询性能》：https://blog.csdn.net/weixin_33709609/article/details/90690198
• 《PostgreSQL中的索引介绍-六（GiST）》：https://www.modb.pro/db/11745
• 《GiST索引》：https://www.cnblogs.com/liuxuelin/p/14843483.html