欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PostgreSQL索引详解5——Gist索引

程序员文章站 2024-01-03 11:11:04
...

1、概述

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

2、结构

Gist索引的结构可以简单概括为:

  • 树结构,深度一致。Tree-structure
  • 索引PAGE内的数据不按KEY的顺序排序。No order within pages
  • 不同的索引PAGE的内容可能存在交叉,例如RANGE类型,值交叉。Key ranges of pages can overlap
  • 由于第三条,所以搜索一条TUPLE时,可能会找到多个满足条件的PAGE。No single “correct” location for
    a particular tuple

2.1、单个gist索引page的结构:
PostgreSQL索引详解5——Gist索引
索引page中存放的是key+tid,例如上图中[100,150]表示100到150这个范围,(1,10)表示行的ctid(第几个HEAP PAGE,里面的第几条记录)。同时,这些存放的值在索引中是无序的。

2.2、Gist两级索引结构:
GiST两级索引长这样,上一级代表下一级中单个INDEX PAGE的大范围。
PostgreSQL索引详解5——Gist索引
例如我们现在查询[55,60]这个范围,在索引中是如何工作的呢?
PostgreSQL索引详解5——Gist索引

3、使用实例

在使用之前,我们先来看看Gist索引的使用场景有哪些。
因为gist是一个通用的索引接口,所以可以使用GiST实现b-tree, r-tree等索引结构。
不同的类型,支持的索引检索也各不一样。例如:
1、几何类型,支持位置搜索(包含、相交、在上下左右等),按距离排序。
2、范围类型,支持位置搜索(包含、相交、在左右等)。
3、IP类型,支持位置搜索(包含、相交、在左右等)。
4、空间类型(PostGIS),支持位置搜索(包含、相交、在上下左右等),按距离排序。
5、标量类型,支持按距离排序。

3.1、几何类型检索
创建一个存放几何数据的表:

bill@bill=>create table t_gist (id int, pos point);    
CREATE TABLE
bill@bill=>insert into t_gist select generate_series(1,100000), point(round((random()*1000)::numeric, 2), round((random()*1000)::numeric, 2));    
INSERT 0 100000
bill@bill=>select * from t_gist limit 5;
 id |       pos       
----+-----------------
  1 | (614.87,412.97)
  2 | (248.71,779.61)
  3 | (976.17,826.79)
  4 | (999.39,126.9)
  5 | (651.61,364.49)
(5 rows)

在pos列上创建gist索引:

bill@bill=>create index idx_t_gist_1 on t_gist using gist (pos);  
CREATE INDEX

查询:
可以发现gist索引支持bitmap scan和index scan。

bill@bill=>explain (analyze,verbose,timing,costs,buffers) select * from t_gist where circle '((100,100) 10)'  @> pos;    
                                                       QUERY PLAN                                                       
------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on bill.t_gist  (cost=2.35..113.84 rows=100 width=20) (actual time=0.107..0.157 rows=35 loops=1)
   Output: id, pos
   Recheck Cond: ('<(100,100),10>'::circle @> t_gist.pos)
   Heap Blocks: exact=32
   Buffers: shared hit=38
   ->  Bitmap Index Scan on idx_t_gist_1  (cost=0.00..2.33 rows=100 width=0) (actual time=0.093..0.093 rows=35 loops=1)
         Index Cond: (t_gist.pos <@ '<(100,100),10>'::circle)
         Buffers: shared hit=6
 Planning Time: 0.188 ms
 Execution Time: 0.268 ms
(10 rows)

bill@bill=>explain (analyze,verbose,timing,costs,buffers) select * from t_gist where circle '((100,100) 1)' @> pos order by pos <-> '(100,100)' limit 10; 
                                                             QUERY PLAN                                                              
-------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.28..12.72 rows=10 width=28) (actual time=0.084..0.085 rows=1 loops=1)
   Output: id, pos, ((pos <-> '(100,100)'::point))
   Buffers: shared hit=4
   ->  Index Scan using idx_t_gist_1 on bill.t_gist  (cost=0.28..124.73 rows=100 width=28) (actual time=0.082..0.083 rows=1 loops=1)
         Output: id, pos, (pos <-> '(100,100)'::point)
         Index Cond: (t_gist.pos <@ '<(100,100),1>'::circle)
         Order By: (t_gist.pos <-> '(100,100)'::point)
         Buffers: shared hit=4
 Planning Time: 0.175 ms
 Execution Time: 0.129 ms
(10 rows)

3.2、标量类型
因为gist可以实现btree的索引结构,所以我们也可以在例如数字这种标量类型上使用gist索引(虽然一般都不如btree索引效果好),不过我们还需要使用btree_gist索引插件。

bill@bill=>create extension btree_gist ;
CREATE EXTENSION
bill@bill=>create table t_btree(id int,info text);
CREATE TABLE
bill@bill=>insert into t_btree select generate_series(1,100000),md5(random()::text);
INSERT 0 100000

创建gist索引:

bill@bill=>create index idx_t_btree on t_btree using gist(id);
CREATE INDEX

查询:

bill@bill=>explain (analyze,verbose,timing,costs,buffers) select * from t_btree order by id <-> 100 limit 1;
                                                               QUERY PLAN                                                                
-----------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.28..0.32 rows=1 width=41) (actual time=0.072..0.073 rows=1 loops=1)
   Output: id, info, ((id <-> 100))
   Buffers: shared hit=4
   ->  Index Scan using idx_t_btree on bill.t_btree  (cost=0.28..3798.18 rows=100000 width=41) (actual time=0.071..0.071 rows=1 loops=1)
         Output: id, info, (id <-> 100)
         Order By: (t_btree.id <-> 100)
         Buffers: shared hit=4
 Planning Time: 0.334 ms
 Execution Time: 0.118 ms
(9 rows)

4、总结

Gist索引实现首先要将数据聚集,聚集后,在单个组内包含的KEY+HEAP行号会放到单个INDEX PAGE中。
聚集的范围作为一级结构,存储在GiST的entry 中,便于检索。
既然灵魂是聚集,那么GiST的性能就和他的聚集算法息息相关,PostgreSQL把这个接口留给了用户,用户在自定义数据类型时,如果要自己实现对应的GIST索引,那么就好好考虑这个类型聚集怎么做吧。
PostgreSQL内置的range, geometry等类型的GIST已经帮你做好了,你只需要做新增的类型,比如你新增了一个存储人体结构的类型,存储图片的类型,或者存储X光片的类型,怎么快速检索它们,那就是你要实现的GIST索引聚集部分了。

参考链接:

https://habr.com/ru/company/postgrespro/blog/444742/

https://www.cnblogs.com/cmi-sh-love/p/kong-jian-shud-ju-suo-yinRTree-wan-quan-jie-xi-jiJa.html

https://github.com/digoal/blog/blob/master/201906/20190604_03.md

上一篇:

下一篇: