F.22. ltree

该模块实现了一种数据类型ltree，用于表示存储在分层树状结构中的数据的标签。提供了用于搜索标签树的广泛工具。

F.22.1. Definitions

label *是字母数字字符和下划线的序列(例如，在 C 语言环境中，允许字符A-Za-z0-9_)。标签长度必须少于 256 个字符。

范例：42，Personal_Services

label path *是零个或多个由点分隔的标签的序列，例如L1.L2.L3，代表从层次树的根到特定节点的路径。标签路径的长度不能超过 65535 个标签。

示例：Top.Countries.Europe.Russia

ltree模块提供了几种数据类型：

ltree存储标签路径。
lquery表示用于匹配ltree值的类似正则表达式的模式。一个简单的单词与路径中的标签匹配。星号(*)匹配零个或多个标签。例如：

foo         Match the exact label path foo
*.foo.*     Match any label path containing the label foo
*.foo       Match any label path whose last label is foo

还可以量化星号以限制它们可以匹配多少个标签：

*{n}        Match exactly n labels
*{n,}       Match at least n labels
*{n,m}      Match at least n but not more than m labels
*{,m}       Match at most m labels — same as  *{0,m}

可以将多个修饰符放在lquery的非星号标签的末尾，以使其比完全匹配更匹配：

@           Match case-insensitively, for example a@ matches A
*           Match any label with this prefix, for example foo* matches foobar
%           Match initial underscore-separated words

%的行为有点复杂。它尝试匹配单词而不是整个标签。例如foo_bar%匹配foo_bar_baz而不匹配foo_barbaz。如果与*结合使用，则前缀匹配分别应用于每个单词，例如foo_bar%*匹配foo1_bar2_baz但不匹配foo1_br2_baz。

另外，您可以编写几个可能经过修改的标签，并以|(OR)分隔以匹配这些标签中的任何一个，也可以在开头放置!(NOT)以匹配与其他替代品不匹配的任何标签。

这是lquery的带 Comments 的示例：

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.22.2. 运算符和功能

类型ltree具有通常的比较运算符=，<>，<，>，<=，>=。比较按树遍历的 Sequences 排序，节点的子级按标签文本排序。另外，Table F.14中显示的专业操作员也可用。

表 F.14.ltree个运算符

Operator	Returns	Description
`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[]` `?` `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

运算符<@，@>，@和~具有类似物^<@，^@>，^@，^~，除了不使用索引外，它们的相似之处相同。这些仅用于测试目的。

可用的功能显示在Table F.15中。

表 F.15.ltree功能

Function	Return Type	Description	Example	Result
`subltree(ltree, int start, int end)`	`ltree`	从位置* `start` 到位置 `end` * -1 的`ltree`子路径(从 0 开始计数)	`subltree('Top.Child1.Child2',1,2)`	`Child1`
`subpath(ltree, int offset, int len)`	`ltree`	`ltree`的子路径从* `offset` 位置开始，长度 `len` 。如果 `offset` 为负，则子路径从该路径的末尾开始。如果 `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`	* `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`	* `b` 在 `a` 中首次出现的位置，从 `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`	将`ltree`投射到`text`
`lca(ltree, ltree, ...)`	`ltree`	路径的最长共同祖先(最多支持 8 个参数)	`lca('1.2.3','1.2.3.4.5.6')`	`1.2`
`lca(ltree[])`	`ltree`	数组中路径的最长共同祖先	`lca(array['1.2.3'::ltree,'1.2.3.4'])`	`1.2`

F.22.3. Indexes

ltree支持多种类型的索引，可以加快指示的运算符的速度：

超过ltree的 B 树索引：<，<=，=，>=，>
GiST 超过ltree的索引：<，<=，=，>=，>，@>，<@，@，~，?

创建这样的索引的示例：

CREATE INDEX path_gist_idx ON test USING GIST (path);

GiST 超过ltree[]的索引：ltree[] <@ ltree，ltree @> ltree[]，@，~，?

创建这样的索引的示例：

CREATE INDEX path_gist_idx ON test USING GIST (array_path);

注意：此索引类型是有损的。

F.22.4. Example

本示例使用以下数据(在源分发中的文件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.22.5. Transforms

可以使用其他扩展来实现 PL/Python 的ltree类型的转换。extensions 为ltree_plpythonu，ltree_plpython2u和ltree_plpython3u(有关 PL/Python 命名约定，请参见Section 45.1)。如果安装这些转换并在创建函数时指定它们，则ltree值将 Map 到 Python 列表。 (但是，当前不支持相反的功能.)

F.22.6. Authors

所有工作都是由 Teodor Sigaev(<teodor@stack.net>)和 Oleg Bartunov(<oleg@sai.msu.su>)完成的。有关其他信息，请参见http://www.sai.msu.su/~megera/postgres/gist/。作者要感谢 Eugeny Rodichev 的有益讨论。欢迎发表 Comment 和错误报告。