Postgesql中的索引-SP-GiST索引
本系列的内容主要翻译自Postgresql官方博客,为了便于理解,对于其中部分涉及到的知识,我在查阅相关资料的基础上做了补充。
原文: Indexes in PostgreSQL — 6 (SP-GiST)
系列文章索引
我们已经讨论了PostgreSQL的索引引擎、访问方法接口以及三个索引方法:哈希索引、B树和GiST。这篇文章中,我们将讨论SP-GiST。
SP-GiST
首先,关于这个名字要说一下。名字中的”GiST”暗指其和同名的GiST索引方法有相似的地方。相似的地方是指:两者都是通用搜索树,都提供了一个构建不同索引方法的通用框架。
“SP”主要是指空间分区(space partitioning)。这里的空间我们通常会理解成我们习惯上所认为的空间,比如说一个二维的平面。但是我们将看到这里的空间可以是任何值域。
SP-GiST适用于那些空间可以被递归的分割成非相交区域的结构(这一点和GiST不同)。这类树包含四叉树(comprises quadtrees)、K维树 (k-D trees)以及弧形树( radix trees)。
结构
所以,SP-GiST的思想是将值域划分为彼此不覆盖的子域,而子域有可以被进一步分割。像这样的分割会导致不平衡树(不像B树和GiST树)
不相交的特性简化了插入和搜索过程的策略。另一方面,作为一项规则,诱导的树是低分枝的。例如,一个四叉树通常有四个子节点(不像B树。子节点的数目可以是上百个)和更高的深度。像这样的树很适合在内存中工作,但是索引是存储在磁盘上的。因此为了减少IO操作的数量,必须将节点打包成页,但是高效的做到这一点并不容易。此外,由于分支的深度不同,在索引中找到不同数值的时间也可能不同。
这个访问方法和GiST一样,做一些底层的工作(并发访问、锁、日志以及纯粹的搜索算法),同时提供了专门的简化接口,来方便增加新的数据和分区算法。
SP-GiST内部的节点存储了对子节点的引用;可以给每一个引用定义一个标签。此外,一个内部节点可以存储一个被叫做prefix的值。实际上这个值不强制一定是前缀,它可以是任意一个满足所有子节点的谓词。
SP-GiST的叶子节点存储了一个索引类型的值和一个对表行的引用。被索引的数据本身(索引键)可以作为这个索引类型的值,但不是必须的:一个缩短类型的值会被存储。
此外,叶子节点可以被分组为列表。因此,一个内部节点不仅可以引用一个值,也可以引用整个列表
请注意,叶子节点的前缀、标签以及值都有自己的数据类型,是彼此独立的。
和GiST一样,为搜索定义的主要函数是一致性函数。这个函数在一个树节点上被调用,并且返回一组子节点,这些子节点的值和搜索的谓语一致。对于一个子节点,一致性函数决定了这个节点中的索引值是否符合搜索谓词。
搜索从根节点开始,一致性函数决定有必要访问的子节点。该算法会在找到的每个子节点上重复运行。该搜索是深度优先的。
在物理层面,索引节点被打包成页,以便在IO层面能让节点的工作更有效率。请注意,一个页面可以包含内部节点和叶子节点,但是不能同时包含。
例子:四叉树
四叉树可以索引平面上的点。思想是根据中心点将平面划分为四个象限,这颗树的分支深度可以是不同的,其深度取决于当前象限内点的密度。
下面是一个样例数据,其数据来源是用openflights.org上的数据对 demo database做了扩充。
首先将平面划分为四个象限
然后再分割每个象限
接着分割,直到得到最后的分区
让我们来提供一个例子来说明更多的细节。这种情况下我们的分区像下图所示。
象限的编号如左图所示。为了明确期间,子节点的象限编号也是按照这个顺序。这种例子下,一个可能的索引结构如下图所示。每个内部节点最多可以引用四个节点,每个引用都可以用象限的编号作为标签。但是实际的实现中没有标签,因为存储四个引用的固定数组会更加方便。
1 | postgres=# create table points(p point); |
在这个例子中,默认使用的操作符类是”quad_point_ops”,其包含下面这些操作
1 | postgres=# select amop.amopopr::regoperator, amop.amopstrategy |
1 | amopopr | amopstrategy |
作为例子,我们来看查询select * from points where p >^ point ‘(2,7)’将被怎么执行
我们从根节点开始应用一致性函数去选择哪些节点可以被下沉。对于操作符>^,函数将点(2,7)与中心点(4,4)比较以后,选择出可能包含寻求的点数的象限,这个例子中,是第一和第四象限。
在第一象限的节点中,我们再次使用一致性函数来选择出可能的子节点。中心点是(6,6),我们需要再次寻找子节点的第一象限和第四象限。
第一象限的叶子节点是包含了(8,6)和(7,8)的列表,其中只有(7,8)是符合要求的。对第四象限的引用都是空的。
(4,4)节点的第四象限也是空的,因此搜素就完成了。
1 | postgres=# set enable_seqscan = off; |
1 | QUERY PLAN |
内部
我们可以使用“gevel”插件来看SP-GiST索引的内部情况。
让我们以示例数据为例
1 | demo=# create index airports_coordinates_quad_idx on airports_ml using spgist(coordinates); |
首先,我们获取索引的一些统计信息
1 | demo=# select * from spgist_stats('airports_coordinates_quad_idx'); |
1 | spgist_stats |
然后,我们输出索引数本身
1 | demo=# select tid, n, level, tid_ptr, prefix, leaf_value |
1 | tid | n | level | tid_ptr | prefix | leaf_value |
但是请记住,”spgist_print”输出的不是叶子节点中的所有值,而是列表中的第一个。因此,这里展示的是索引的结构而不是全部的内容。
K维树
同样是平面上的点,我们也可以使用另外一种分区方法。
让我们先画一条横着的线经过第一个被索引的点,这条直线将平面分割维上下两个部分。下一个索引的点就处在这两个部分的一个。通过第二个点,画一条竖着的线,将这个部分再次划分为左右两个部分。然后我们再画一条水平的线通过下一个点,再画一条垂直的线经过下一个点,如此反复。
这样建立的树所有内部的节点都只有两个子节点的引用,这两个引用都可以通向下一个内部节点或者通向叶子节点的列表。
这种方法可以很容易的推广到K维空间,因此在文献中,这些树也被称为k-dimensional (k-D trees)
以机场的例子解释该方法
首先将平面划分为上下两个部分
然后将每个部分分割为左右两个部分
为了使用这样的分区,我们需要在创建索引的时候明确的指定操作符类“kd_point_ops”
1 | postgres=# create index points_kd_idx on points using spgist(p kd_point_ops); |
这个操作符类包含和默认的”quad_point_ops”完全相同的操作符。
内部
在查看树结构的时候,我们需要考虑到,在这种情况下,前缀只是一个坐标,而不是一个点。
因为是垂直或者水平分割的,因此前缀只需要一个数字就可以表示。
1 | demo=# select tid, n, level, tid_ptr, prefix, leaf_value |
1 | tid | n | level | tid_ptr | prefix | leaf_value |
例子:弧度树
我们也可以用SP-GiST来为字符串实现一个弧度树。弧度树的思想是要索引的字符串并不完全存储在一个叶子节点中,而是通过串联的存储在这个节点以上直到根部的值来获取到。
假设我们需要索引几个地址:”postgrespro.ru”,”postgrespro.com”,”postgresql.org”和”planet.postgresql.org”
1 | postgres=# create table sites(url text); |
树的结构如下所示:
数字的叶子节点存储了所有子节点的前缀。例如,在”stgres”这个节点的子节点中的值都以 “p” + “o” + “stgres”为前缀。
与四叉树不同的是,每一个指向子节点的指针中都使用了额外的一个字符(更精确的来说是两个字节,但是这并不重要)作为标签。
“text_ops “运算符类支持类似B-树的运算符: “equal”, “greater”, and “less”:
1 | postgres=# select amop.amopopr::regoperator, amop.amopstrategy |
1 | amopopr | amopstrategy |
带标记的运算符的区别在于,他们操作的是字节而不是字符。
有的时候,用弧度树的形式表示可能会比B树更加紧凑的,因为数值不是完全存储的,而是通过树的下降来重建字符串。
考虑到这个查询:select * from sites where url like ‘postgresp%ru’。它可以通过索引来执行
1 | postgres=# set enable_seqscan = off; |
1 | QUERY PLAN |
实际上索引是用来寻找大于等于postgresp并且小于postgresq的值,然后从结果中选择匹配的值。
首先一致性函数必须决定出要下降到p的哪个子节点。显然,需要下降到”p “+”o “+”stgres”
对于 “stgres “节点,需要再次调用一致性函数来检查。 这次下降到”postgres “+”p “+”ro”。
对于”ro.”节点以及所有的叶子节点,一致性函数将返回TRUE,因此索引方法返回了两个值:”postgrespro.com “和 “postgrespro.ru”。然后在过滤阶段从他们中选择匹配的值。
内部
在查看树状结构的时候,需要将数据类型考虑在内
1 | postgres=# select * from spgist_print('sites_url_idx') as t( |
原文中并没有,下面的结果是自己运行后结果。 但是由于原文中插入的数据过少,展示出的结果只有一个层级,因此我在里面又插入了几千条记录得出的内部树结构。node_label的值是字符的ASCII码,例如112是p、 119 是 w。
1 | tid | allthesame | n | level | tid_ptr | prefix | node_label | leaf_value |
属性
然后来看一下 SP-GiST 的属性
1 | select a.amname, p.name, pg_indexam_has_property(a.oid,p.name) |
1 | amname | name | pg_indexam_has_property |
spgist不支持用来排序也不能做唯一约束。此外,这样的索引也不能建立在多个字段上,但是允许用来做唯一约束。
下列的索引属性是可以用的
1 | select p.name, pg_index_has_property('sites_url_idx'::regclass,p.name) |
1 | name | pg_index_has_property |
这里与GiST的区别在于,SP-GiST不支持聚类。
最后,下面是列属性
1 | select p.name, |
1 | name | pg_index_column_has_property |
不支持排序,这是可以预见的。到目前为止,SP-GiST中还没有用于搜索近邻的距离运算符。最有可能的是,这个功能将在未来得到支持。
SP-GiST可以用于纯索引扫描,至少对于所讨论的运算符类来说是这样。正如我们所看到的,在某些情况下,索引值被明确地存储在叶子节点中,而在其他情况下,这些值是在树的下降过程中逐部分重建的。
NULLs
为了不使情况复杂化,到目前为止我们还没有提到NULL。从索引属性中可以看出,NULL是被支持的
1 | postgres=# explain (costs off) |
1 | QUERY PLAN |
然而,NULL对于SP-GiST来说是一个陌生的东西。所有来自 “spgist “操作符类的操作符都必须是严格的:只要操作符的任何参数是NULL,就必须返回NULL。方法本身确保了这一点。NULL不会被传递给操作符。
但是,为了使用只扫描索引的访问方法,NULL必须被存储在索引中。它们被存储在在一个单独的有自己根的树中。
其它数据类型
除了点和为了字符串使用的弧度树以外,还有一些其它的基实现了SP-GiST的访问方法。
- “box_ops “运算符类为矩形提供了一个四象限树。每个矩形用四维空间中的一个点来表示,因此象限的数量是16。如果存在很多相交的矩形,SP-GiST索引就会比GiST有更高的性能:在GiST中,没有这样的边界能够将彼此相交的分离开来,而点(即使是四维的)则没有这样的问题。
- “range_ops “运算符类为区间(intervals)提供了一个四叉树。一个区间由一个二维的点来表示:下边界成为横轴,上边界成为纵轴。
原文作者: 李小飞
原文链接: https://www.lixf.cc/2022/01/08/Indexes-in-PostgreSQL-6/
版权声明: 转载请注明出处(必须保留作者署名及链接)