F.15. ltree #
该模块实现了数据类型 ltree，用于表示存储在层次化树状结构中的数据标签。它还提供了丰富的标签树搜索能力。
F.15.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模块提供了几种数据类型：
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%*可匹配foo1_bar2_baz，但不能匹配foo1_br2_baz。此外，还可以写出多个可能带修饰符的非星号项，并用
|（OR）分隔，以匹配其中任意一项；也可以在非星号组前加上!（NOT），以匹配不符合这些备选项中任意一项的标签。下面是一个带注释的示例，使用
lquery：Top.*{0,2}.sport*@.!football|tennis.Russ*|Spain a. b. c. d. e.此查询将匹配满足以下条件的任意标签路径：
以标签
Top开头接下来，在下一个条件之前有零到两个标签
然后是一个以前缀
sport开头的标签，且匹配时不区分大小写接着有一个不匹配
football或tennis的标签最后以一个以
Russ开头的标签，或精确匹配Spain的标签结束。
ltxtquery表示一种用于匹配ltree值的、类似全文检索的模式。一个ltxtquery值包含单词，末尾还可以带有修饰符@、*、%；这些修饰符与它们在lquery中的含义相同。单词可以通过&（AND）、|（OR）、!（NOT）以及圆括号组合。它与lquery的关键区别在于，ltxtquery匹配单词时不考虑它们在标签路径中的位置。下面是一个
ltxtquery示例：Europe & Russia*@ & !Transportation
它将匹配包含标签
Europe以及任意以Russia开头（不区分大小写）的标签的路径，但不匹配包含标签Transportation的路径。这些单词在路径中的位置并不重要。另外，当使用%时，该单词可以匹配标签中任意由下划线分隔的单词，而不考虑其位置。
注意：ltxtquery允许在符号之间出现空白，而ltree和lquery不允许。
F.15.2. 操作符和函数
类型 ltree 具有常见的比较操作符
=、<>、<、>、<=、>=。比较时采用树遍历顺序，其中节点的子节点按标签文本排序。此外，还提供了以下专用操作符：
表 F.11. ltree 操作符
| Operator | Returns | 描述 |
|---|---|---|
ltree @> ltree | boolean | 左参数是否为右参数的祖先（或与之相等）？ |
ltree <@ ltree | boolean | 左参数是否为右参数的后代（或与之相等）？ |
ltree ~ lquery | boolean | does ltree match lquery? |
lquery ~ ltree | boolean | does ltree match lquery? |
ltree ? lquery[] | boolean | does ltree match any lquery in array? |
lquery[] ? ltree | boolean | does ltree match any lquery in array? |
ltree @ ltxtquery | boolean | does ltree match ltxtquery? |
ltxtquery @ ltree | boolean | does ltree match ltxtquery? |
ltree || ltree | ltree | concatenate ltree paths |
ltree || text | ltree | convert text to ltree and concatenate |
text || ltree | ltree | convert text to ltree and concatenate |
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[] ? ltree[] | boolean | ltree 数组是否包含匹配任意 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 | subpath of ltree from position start to
position end-1 (counting from 0) | subltree('Top.Child1.Child2',1,2) | Child1 |
subpath(ltree, int offset, int len) | ltree | 从位置 offset 开始、长度为
len 个标签的 ltree 子路径。如果
offset 为负，则子路径从距路径末尾
-offset 个标签处开始。如果 len 为负，则从路径末尾省去那么多个标签。 | subpath('Top.Child1.Child2',0,2) | Top.Child1 |
subpath(ltree, int offset) | ltree | 从位置 offset 开始、一直延伸到路径末尾的 ltree 子路径。如果 offset
为负，则子路径从距路径末尾 -offset 个标签处开始。 | subpath('Top.Child1.Child2',1) | Child1.Child2 |
nlevel(ltree) | integer | 路径中的标签数 | nlevel('Top.Child1.Child2') | 3 |
index(ltree a, ltree b) | integer | b 在 a 中首次出现的位置；如果未找到则为 -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 | 从 offset 开始搜索时，b 在 a 中首次出现的位置；负的 offset 表示从路径末尾向前 -offset 个标签处开始 | index('0.1.2.3.5.4.5.6.8.5.6.8','5.6',-4) | 9 |
text2ltree(text) | ltree | cast text to ltree | | |
ltree2text(ltree) | text | 将 ltree 转换为 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.15.3. 索引
ltree支持几种能够加速所示操作符的索引类型：
ltree上的 B-树索引：<、<=、=、>=、>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);
注意：这种索引类型是有损的。
F.15.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.15.5. 作者
全部工作均由 Teodor Sigaev（<teodor@stack.net>）和
Oleg Bartunov（<oleg@sai.msu.su>）完成。更多信息见http://www.sai.msu.su/~megera/postgres/gist/。作者谨感谢 Eugeny Rodichev 的有益讨论。欢迎提出意见和缺陷报告。