F.21. ltree

这个模块实现了一种数据类型ltree用于表示存储在一个层次树状结构中的数据的标签。还提供了在标签树中搜索的扩展功能。

F.21.1. 定义

一个标签是一个字母数字字符和下划线的序列(例如,在 C 区域中允许字符A-Za-z0-9_)。标签长度必须少于 256 字节。

例子: 42, Personal_Services

一个标签路径是由点号分隔的零个或者更多个标签的序列,例如L1.L2.L3,它表示一个从层次树的根到一个特定节点的路径。一个标签路径的长度必须小于 65Kb,但是最好将它保持在 2Kb 以下。实际上这不是一个主要限制,例如在 DMOZ 目录(http://www.dmoz.org)中最长的标签路径大约是 240 字节。

例子:Top.Countries.Europe.Russia

ltree模块提供多种数据类型:

注意:ltxtquery允许符号之间的空白,但是ltreelquery不允许。

F.21.2. 操作符和函数

类型ltree有普通比较操作符 =<><><=>=。 比较会按照树遍历的顺序排序,一个节点的子女按照标签文本排序。另外,还有Table F-12中显示的特殊操作符。

Table F-12. ltree 操作符

操作符返回值描述
ltree @> ltreeboolean左参数是不是右参数的一个祖先(或者相等)?
ltree <@ ltreeboolean左参数是不是右参数的一个后代(或者相等)?
ltree ~ lquerybooleanltree匹配lquery吗?
lquery ~ ltreebooleanltree匹配lquery吗?
ltree ? lquery[]booleanltree匹配数组中的任意lquery吗?
lquery[] ? ltreebooleanltree匹配数组中的任意lquery吗?
ltree @ ltxtquerybooleanltree匹配ltxtquery吗?
ltxtquery @ ltreebooleanltree匹配ltxtquery吗?
ltree || ltreeltree串接ltree路径
ltree || textltree把文本转换成ltree并且串接
text || ltreeltree把文本转换成ltree并且串接
ltree[] @> ltreeboolean数组是否包含ltree的一个祖先?
ltree <@ ltree[]boolean数组是否包含ltree的一个祖先?
ltree[] <@ ltreeboolean数组是否包含ltree的一个后代?
ltree @> ltree[]boolean数组是否包含ltree的一个后代?
ltree[] ~ lqueryboolean数组是否包含匹配lquery的路径?
lquery ~ ltree[]boolean数组是否包含匹配lquery的路径?
ltree[] ? lquery[]booleanltree数组是否包含匹配任意lquery的路径?
lquery[] ? ltree[]booleanltree数组是否包含匹配任意lquery的路径?
ltree[] @ ltxtqueryboolean数组是否包含匹配ltxtquery的路径?
ltxtquery @ ltree[]boolean数组是否包含匹配ltxtquery的路径?
ltree[] ?@> ltreeltreeltree祖先的第一个数组项;如果没有则是 NULL
ltree[] ?<@ ltreeltreeltree祖先的第一个数组项;如果没有则是 NULL
ltree[] ?~ lqueryltree匹配lquery的第一个数组项;如果没有则是 NULL
ltree[] ?@ ltxtqueryltree匹配lquery的第一个数组项;如果没有则是 NULL

操作符<@@>@以及~有类似的、 ^<@^@>^@^~,只是它们不适用索引。它们只对测试目的有用。

可用的函数在Table F-13中。

Table F-13. ltree 函数

函数返回类型描述例子结果
subltree(ltree, int start, int end)ltreeltree的从位置start到位置end-1(从 0 开始计)的子路径subltree('Top.Child1.Child2',1,2)Child1
subpath(ltree, int offset, int len)ltreeltree从位置offset开始长度为len的子路径。如果offset为负,则子路径开始于距离路径尾部那么远的位置。如果len为负,则从路径的尾部开始丢掉那么多个标签。subpath('Top.Child1.Child2',0,2)Top.Child1
subpath(ltree, int offset)ltreeltree从位置offset开始一直延伸到路径末尾的子路径。如果offset为负,则子路径开始于距离路径尾部那么远的位置。subpath('Top.Child1.Child2',1)Child1.Child2
nlevel(ltree)integer路径中标签的数量nlevel('Top.Child1.Child2')3
index(ltree a, ltree b)integera中第一次出现b的位置,如果没有找到则为 -1index('0.1.2.3.5.4.5.6.8.5.6.8','5.6')6
index(ltree a, ltree b, int offset)integera中第一次出现b的位置,搜索从offset开始。负的offset表示从距路径尾部-offset个标签的位置开始index('0.1.2.3.5.4.5.6.8.5.6.8','5.6',-4)9
text2ltree(text)ltreetext转换成ltree
ltree2text(ltree)textltree转换成text
lca(ltree, ltree, ...)ltree最低公共祖先,即最长的公共路径前缀(最多支持 8 个参数)lca('1.2.2.3','1.2.3.4.5.6')1.2
lca(ltree[])ltree最低公共祖先,即最长的公共路径前缀lca(array['1.2.2.3'::ltree,'1.2.3'])1.2

F.21.3. 索引

ltree支持一些能加速上述操作符的索引类型:

F.21.4. 例子

这个例子使用下列数据(在源代码发布的contrib/ltree/ltreetest.sql文件中也有):

CREATE TABLE test (path ltree);
INSERT INTO test VALUES ('Top');
INSERT INTO test VALUES ('Top.Science');
INSERT INTO test VALUES ('Top.Science.Astronomy');
INSERT INTO test VALUES ('Top.Science.Astronomy.Astrophysics');
INSERT INTO test VALUES ('Top.Science.Astronomy.Cosmology');
INSERT INTO test VALUES ('Top.Hobbies');
INSERT INTO test VALUES ('Top.Hobbies.Amateurs_Astronomy');
INSERT INTO test VALUES ('Top.Collections');
INSERT INTO test VALUES ('Top.Collections.Pictures');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Stars');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Galaxies');
INSERT INTO test VALUES ('Top.Collections.Pictures.Astronomy.Astronauts');
CREATE INDEX path_gist_idx ON test USING gist(path);
CREATE INDEX path_idx ON test USING btree(path);

现在,我们有一个表test,它被填充了描述下列层次的数据:

                        Top
                     /   |  \
             Science Hobbies Collections
                 /       |              \
        Astronomy   Amateurs_Astronomy Pictures
           /  \                            |
Astrophysics  Cosmology                Astronomy
                                        /  |    \
                                 Galaxies Stars Astronauts

我们可以做继承:

ltreetest=> SELECT path FROM test WHERE path <@ 'Top.Science';
                path
------------------------------------
 Top.Science
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(4 rows)

这里是一些路径匹配的例子:

ltreetest=> SELECT path FROM test WHERE path ~ '*.Astronomy.*';
                     path
-----------------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
 Top.Collections.Pictures.Astronomy
 Top.Collections.Pictures.Astronomy.Stars
 Top.Collections.Pictures.Astronomy.Galaxies
 Top.Collections.Pictures.Astronomy.Astronauts
(7 rows)

ltreetest=> SELECT path FROM test WHERE path ~ '*.!pictures@.*.Astronomy.*';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(3 rows)

这里是一些全文搜索的例子:

ltreetest=> SELECT path FROM test WHERE path @ 'Astro*% & !pictures@';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
 Top.Hobbies.Amateurs_Astronomy
(4 rows)

ltreetest=> SELECT path FROM test WHERE path @ 'Astro* & !pictures@';
                path
------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
(3 rows)

使用函数的路径构建:

ltreetest=> SELECT subpath(path,0,2)||'Space'||subpath(path,2) FROM test WHERE path <@ 'Top.Science.Astronomy';
                 ?column?
------------------------------------------
 Top.Science.Space.Astronomy
 Top.Science.Space.Astronomy.Astrophysics
 Top.Science.Space.Astronomy.Cosmology
(3 rows)

我们可以通过常见一个在路径中指定位置插入标签的 SQL 函数来简化:

CREATE FUNCTION ins_label(ltree, int, text) RETURNS ltree
    AS 'select subpath($1,0,$2) || $3 || subpath($1,$2);'
    LANGUAGE SQL IMMUTABLE;

ltreetest=> SELECT ins_label(path,2,'Space') FROM test WHERE path <@ 'Top.Science.Astronomy';
                ins_label
------------------------------------------
 Top.Science.Space.Astronomy
 Top.Science.Space.Astronomy.Astrophysics
 Top.Science.Space.Astronomy.Cosmology
(3 rows)

F.21.5. 作者

所有工作都是 Teodor Sigaev()和 Oleg Bartunov()完成的。额外信息可见 http://www.sai.msu.su/~megera/postgres/gist/。作者还要感谢 Eugeny Rodichev 参与讨论。欢迎评论和缺陷报告。