关于PostgreSQL的GiST索引之五

4.其它数据类型的GiST索引

GiST索引可适用于多维数据类型和集合数据类型，对多维数据类型使用Rtree的索引算法，对集合数据类型RD-tree或者签名文件（是不是也可以叫利用签名向量压缩的RD-tree）的索引算法。签名文件的索引算法由于采用有损压缩的方式保存key集合，所以搞不好会遇到性能陷阱。前面已经详细介绍了tsvector和hstore的GiST索引，它们都采用了签名文件的索引算法，只不过签名向量的大小，叶节点的索引项是否用签名向量压缩等细节不一样。下面再简单介绍其他几种GiST索引采用签名文件索引算法的数据类型。

4.1 intarray

PostgreSQL为数组提供了默认的GIN索引操作符。如果想对int数组尝试GiST索引，可以使用intarray扩展模块带来的两个GiST索引操作符类。

gist__int_ops操作符类
采用RD-tree的索引算法，索引项中放int型key的集合。
1)对叶节点的索引项，如果key的数目超过199，报错。
2)对非叶节点的索引项，如果key的数目超过199，进行无损压缩。
  压缩方法为依次存放key和该key出现的次数。因此这种方法对重复key比较少的场合，不但不能起到压缩的作用，反而更膨胀了。

相关代码
contrib/intarray/_int_gist.c

gist__intbig_ops操作符类
使用签名向量的形式有损压缩索引项，和hstore的GiST索引类似。
1)所有索引项包含的key的集合都采用签名向量压缩
2)签名向量的大小为2016bit

相关代码
contrib/intarray/_intbig_gist.c

4.2 pg_trgm

pg_trgm模块提供的gist_trgm_ops操作符类可以把text数据切成若干三元词，并使用签名向量的形式压缩存储这些三元词，索引算法和tsvetor的GiST索引类似。
gist_trgm_ops操作符类
1)叶节点的索引项存储pg_trgm三元词的数组
  pg_trgm生成三元词时，内部用了3个字节存储三元词，如果三元词中包含多字节字符，通过先计算CRC再取前3个字节的方法压缩。
2)非叶节点的索引项存储其包含的所有三元词集合的签名向量
3)签名向量的大小为96bit

由于pg_trgm的GiST索引的签名向量比较小，每次查询需要扫描的索引节点数必然很多，会很影响速度。
具体的测试实例可参考下面这篇文章。
http://blog.chinaunix.net/uid-20726500-id-4824895.html

相关代码
contrib/pg_trgm/trgm_gist.c


ltree
ltree模块引入一种可以表达路径的数据类型ltree，比如：Top.Science.Astronomy.Astrophysics 。ltree模块包含了两个GiST索引操作符类。
gist_ltree_ops操作符类
gist_ltree_ops用于索引ltree，它的算法是签名向量和Rtree的混合体。所以它既支持比较操作符(<, <=, =, >=, >)，又支持匹配操作符（@>, <@, @, ~, ?）。
1）叶节点的索引项全部存储原始ltree数据
2）非叶节点的索引项存储标签集合的签名向量和Rtree需要的边界值
3）签名向量的大小为64bit

gist_ltree_ops的签名向量同样很小，损耗很大。gist_ltree_ops对单个标签的匹配查询效率很低，但是作为匹配条件的路径中一般包含多个标签，所以查询效率可以得到成倍提高。

相关代码
contrib/ltree/ltree_gist.c

gist__ltree_ops操作符类
gist__ltree_ops用于索引ltree的数组，采用类似hstore的GiST索引的签名向量的算法。
1)所有索引项都采用签名向量压缩
2)对ltree数组中的所有ltree的所有标签值都进行哈希设置bit位得到一个签名向量
3)签名向量的大小为224bit

相关代码
contrib/ltree/_ltree_gist.c

5. 总结：GiST还是GIN？

PostgreSQL中对很多集合数据类型同时提供GiST和GIN两种索引操作符类，该选哪个好，有时让人头疼。对查询操作，无疑GIN索引要优于GiST。但是对更新操作，GIN索引要为集合中的每个元素生成一个项目，而GiST是为整个集合生成一个项目，所以GiST在更新操作上有优势。GIN索引的问题很好量化，由GIN索引带来的更新操作的额外负担和平均每条记录中包含的集合数据的大小成正比。而GiST索引在查询上的性能表现就严重依赖于操作符类如何在索引项目中存储集合数据了。有没有压缩？有损压缩还是无损压缩？压缩损耗有多大？所以要结合使用场景和GiST的压缩算法具体问题具体分析。