Ltree

From PostgreSQL 中文维基, PostgreSQL 中文站, PostgreSQL 中国社区, PostgreSQL Chinese community

Jump to: navigation, search

[编辑] ltree

目录

这个模块实现了一个数据类型 ltree，用于表示以树状层次结构的标签数据。这个模块还给树结构提供了扩展的设施和搜索的功能。

[编辑] 定义

标签是一个字母数字和下划线字符组成的序列（比如，在 C locale 设置里头，字符 A-Za-z0-9_ 都是允许的）。标签必须小于 256 字节长。

例子： 

 42，Personal_Services

一个标签路径是一个零或者多个用点分隔的标签，比如 L1.L2.L3，代表从层极关系的根到特定节点的路径。标签路径的长度必须小于 65Kb，最好小于 2Kb。实际上这并不是一个什么限制；比如，在 DMOZ 分类（ http://www.dmoz.org ）里最长的标签路径大概是240字节长。

例子： 

 Top.Countries.Europe.Russia

ltree 模块提供了几个数据结构：

  • ltree 存储标签路径。
  • lquery 表示了一个类似正则的用于匹配 ltree 值的模式。一个字匹配在某个路径里的标签。一个星号（*）匹配零个或多个标签。比如： 
     foo         准确匹配标签路径 foo
     *.foo.*     匹配任何包含标签 foo 的路径
     *.foo       匹配任何最后的标签是 foo 的标签路径
星号也可以使用量词，表示可以匹配的标签个数： 
     *{n}        匹配正好 n 个标签
     *{n,}       匹配至少 n 个标签
     *{n,m}      匹配至少 n 个，但不超过 m 个标签
     *{,m}       匹配最多 m 个标签 -- 和 *{0,m} 一样
在 lquery 里头，还有好几个修饰词可以放在非星号标签的后头，让它可以做某些模糊匹配： 
     @           大小写无关匹配，比如 a@ 匹配 A
     *           匹配任意带有类似前缀的标签，比如 foo* 匹配 foobar
     %           匹配开头是用下划线分隔的字
%的行为稍微有些复杂。它会试图匹配字而不是整个标签。比如 foo_bar% 匹配 foo_bar_baz，但是不匹配 foo_barbaz。如何和 * 结合使用，那么前缀匹配就会应用于各个独立的字，比如 foo_bar%* 匹配 foo_bar2_baz，但是不匹配 foo1_br2_baz。
还有，你可以使用 | （OR）书写好几个（可能带修饰的）标签用于匹配任意这些标签，也可以在开头写 ! （NOT）以匹配任何不匹配所有候选的标签。
下面是一个有注解的 lquery 的例子： 
  Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain
    a.  b.     c.      d.               e.
这个查询会匹配符合下面条件的任何标签：
  1. 以标签 Top 开头
  2. 然后是零到两个标签
  3. 一个以大小写无关的前缀 sport 开头的标签
  4. 然后是一个既不匹配 football 也不匹配 tennis 的标签
  5. 然后是一个以一个开头是 Russ 或者精确匹配 Spain 的标签结束。　
  • ltxtquery 表示一个匹配 ltree 的类似全文搜索的模式。一个 ltxtquery 值包含字，字的后面可能有修饰词 @，*，%；修饰词的含义和 lquery 相同。字可以用 &（AND），|（OR），!（NOT）和括弧组合。它和 lquery 的主要区别是 ltxtquery 匹配的字不会考虑他们在标签路径里面的位置。
这里是 ltxtquery 的例子： 
         Europe & Russia*@ & !Transportation
这样将会匹配包含标签 Europe 和任何以大小写无关的 Russia开头，并且路径中不包含标签 Transportation 的路径。这些字在路径中的位置无所谓。还有，在使用 % 的时候，这些字还可以匹配在一个标签内任意用下划线分隔的字，位置也是无关的。

注意：ltxtquery 允许在符号之间有空白，但是 ltree 和 lquery 不允许。

[编辑] 操作符和函数

ltree 类型有通常的比较操作符 =，<>，<，>，<=，>=。比较排序是以遍历树的顺序进行的，子节点的顺序是由标签文本排序的。另外，还有下列特殊的操作符：

表 F-11 ltree 操作符
操作符 返回值 描述
ltree @> ltree boolean 左手边参数是右手边的祖先（或者平辈）吗？
ltree <@ ltree boolean 左手边参数是右手边的后代（或者平辈）吗？
ltree ~ lquery boolean ltree 匹配 lquery 吗？
lquery ~ ltree boolean ltree 匹配 lquery 吗？
ltree ? lquery[] boolean ltree 匹配数组中的任何 lquery 吗？
lquery[] ? ltree boolean ltree 匹配数组中的任何 lquery 吗？
ltree @ ltxtquery boolean ltree 匹配 ltxtquery 吗？
ltxtquery @ ltree boolean ltree 匹配 ltxtquery 吗？
ltree || ltree ltree 连接 ltree 路径
ltree || text ltree 把文本转换为 ltree 然后连接
text || ltree ltree 把文本转换为 ltree 然后连接
ltree[] @> ltree boolean 数组是否包含 ltree 的一个祖先？
ltree <@ ltree[] boolean 数组是否包含 ltree 的一个后代？
ltree[] <@ ltree boolean 数组是否包含 ltree 的一个后代？
ltree @> ltree[] boolean 数组是否包含 ltree 的一个祖先？
ltree[] ~ lquery boolean 数组是否包含匹配 lquery 的路径？
lquery ~ ltree[] boolean 数组是否包含匹配 lquery 的路径？
ltree[] ? lquery[] boolean ltree 数组是否包含任意匹配任意 lquery 数组中的 lquery 的项？
lquery[] ? ltree[] boolean ltree 数组是否包含任意匹配任意 lquery 数组中的 lquery 的项？
ltree[] @ ltxtquery boolean 数组里是否有任意路径匹配 ltxtquery？
ltxtquery @ ltree[] boolean 数组里是否有任意路径匹配 ltxtquery？
ltree[] ?@> ltree ltree 数组中第一个是 ltree 的祖先的项；如果没有则为 NULL
ltree[] ?<@ ltree ltree 数组中第一个是 ltree 的后代的项；如果没有则为 NULL
ltree[] ?~ lquery ltree 数组中第一个匹配 lquery 的项，如果没有则为 NULL
ltree[] ?@ ltxtquery ltree 数组中第一个匹配 ltxtquery 的项，如果没有则为 NULL

操作符 <@，@>，@ 和 ~ 有类似的 ^<@，^@>，^@，^~，他们的功能一样区别只是不使用索引。这些只是在测试的时候有用。

有下列函数可用：

表 F-12. ltree 函数
函数 返回类型 描述 例子 结果
subltree(ltree, int start, int end) ltree 从位置 start 到位置 end-1 的 ltree 的子树（从零开始计算） subltree('Top.Child1.Child2',1,2) Child1
subpath(ltree, int offset, int len) ltree 从位置 offset 开始，长度为 len 的 ltree 子树。如果 offset 为负数，那么 subpath 则从结尾向前移动对应的长度。如果 len 为负数，则从路径末尾留下对应长度的标签。 subpath('Top.Child1.Child2',0,2) Top.Child1
subpath(ltree, int offset) ltree ltree 的子路径，从位置 offset 开始，延伸到路径结尾。如果 offset 是负数，子路径从路径末尾向前偏移。 subpath('Top.Child1.Child2',1) Child1.Child2
nlevel(ltree) integer 路径中的标签个数 nlevel('Top.Child1.Child2') 3
index(ltree a, ltree b) integer 在 a 里面出现的第一个 b 的位置；如果没找到则为 -1 index('0.1.2.3.5.4.5.6.8.5.6.8','5.6') 6
index(ltree a, ltree b, int offset) integer 在 a 里面出现的第一个 b 的位置；搜索起点是 offset，负数的 offset 意思是从路径末尾的 - offset 个标签开始计算 index('0.1.2.3.5.4.5.6.8.5.6.8','5.6',-4) 9
text2ltree(text) ltree 把 text 转换为 ltree
ltree2text(ltree) text 把 text 转换为 ltree
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

[编辑] 索引

ltree 支持好几种类型的索引，可以加速指定操作符的查找：

  • ltree 上的 B-tree：<，<=，=，>=，>
  • ltree 上的 GiST 索引：<，<=，=，>=，>，@>，<@，@，~，?
创建这样的索引的例子： 
  CREATE INDEX path_gist_idx ON test USING GIST (path);
  • ltree[]上的 GiST 索引：ltree[] <@ ltree，ltree @> ltree[]，@，~，?
创建这样的索引的例子： 
  CREATE INDEX path_gist_idx ON test USING GIST (array_path);
注意：这个索引类型是松散的。

[编辑] 例子

这个例子适用下列数据（也可以在源代码的文件 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)

[编辑] 作者

所有工作都是 Teodor Sigaev（<teodor@stack.net>）和 Oleg Bartunov（<oleg@sai.msu.su>）做的，参阅 http://www.sai.msu.su/~megera/postgres/gist 获取额外的信息。作者们感谢 Eugeny Rodichev 参与的非常有助的讨论。欢迎评论和虫子报告。

取自"http://www.pgsqldb.org/mwiki/index.php/Ltree"
Personal tools