F.23. ltree — 层次树状数据类型#

F.23.1. 定义
F.23.2. 运算符和函数
F.23.3. 索引
F.23.4. 示例
F.23.5. 转换
F.23.6. 作者

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

此模块被认为是“受信任的”，也就是说，它可以由对当前数据库具有CREATE权限的非超级用户安装。

F.23.1. 定义#

标签是字母数字字符、下划线和连字符的序列。有效的字母数字字符范围取决于数据库语言环境。例如，在 C 语言环境中，允许使用字符A-Za-z0-9_-。标签长度不得超过 1000 个字符。

示例：42、Personal_Services

标签路径是由点分隔的零个或多个标签的序列，例如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}
foo{n,m}    Match at least n but not more than m occurrences of foo
foo{,}      Match any number of occurrences of foo, including zero
```
在没有明确量词的情况下，星号的默认值为匹配任意数量的标签（即 {,}），而非星号项的默认值为精确匹配一次（即 {1}）。
有几个修饰符可以放在非星号 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 的带注释示例
```
Top.*{0,2}.sport*@.!football|tennis{1,}.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不允许。

F.23.2. 运算符和函数#

类型ltree具有常见的比较运算符=、<>、<、>、<=、>=。比较按树遍历的顺序进行排序，节点的子节点按标签文本排序。此外，表 F.13中所示的专门运算符可用。

表 F.13.ltree运算符

运算符描述
`ltree` `@>` `ltree` → `boolean` 左参数是右参数的祖先（或相等）吗？
`ltree` `<@` `ltree` → `boolean` 左参数是右参数的后代（或相等）吗？
`ltree` `~` `lquery` → `boolean` `lquery` `~` `ltree` → `boolean` `ltree` 与 `lquery` 匹配吗？
`ltree` `?` `lquery[]` → `boolean` `lquery[]` `?` `ltree` → `boolean` `ltree` 与数组中的任何 `lquery` 匹配吗？
`ltree` `@` `ltxtquery` → `boolean` `ltxtquery` `@` `ltree` → `boolean` `ltree` 与 `ltxtquery` 匹配吗？
`ltree` `\|\|` `ltree` → `ltree` 连接 `ltree` 路径。
`ltree` `\|\|` `text` → `ltree` `text` `\|\|` `ltree` → `ltree` 将文本转换为 `ltree` 并连接。
`ltree[]` `@>` `ltree` → `boolean` `ltree` `<@` `ltree[]` → `boolean` 数组是否包含 `ltree` 的祖先？
`ltree[]` `<@` `ltree` → `boolean` `ltree` `@>` `ltree[]` → `boolean` 数组是否包含 `ltree` 的后代？
`ltree[]` `~` `lquery` → `boolean` `lquery` `~` `ltree[]` → `boolean` 数组是否包含与 `lquery` 匹配的任何路径？
`ltree[]` `?` `lquery[]` → `boolean` `lquery[]` `?` `ltree[]` → `boolean` `ltree` 数组是否包含与任何 `lquery` 匹配的任何路径？
`ltree[]` `@` `ltxtquery` → `boolean` `ltxtquery` `@` `ltree[]` → `boolean` 数组是否包含与 `ltxtquery` 匹配的任何路径？
`ltree[]` `?@>` `ltree` → `ltree` 返回第一个作为 `ltree` 祖先的数组条目，或在没有的情况下返回 `NULL`。
`ltree[]` `?<@` `ltree` → `ltree` 返回第一个作为 `ltree` 后代的数组条目，或在没有的情况下返回 `NULL`。
`ltree[]` `?~` `lquery` → `ltree` 返回第一个与 `lquery` 匹配的数组条目，或在没有的情况下返回 `NULL`。
`ltree[]` `?@` `ltxtquery` → `ltree` 返回第一个与 `ltxtquery` 匹配的数组条目，或在没有的情况下返回 `NULL`。

运算符

描述

ltree @> ltree → boolean

左参数是右参数的祖先（或相等）吗？

ltree <@ ltree → boolean

左参数是右参数的后代（或相等）吗？

ltree ~ lquery → boolean

lquery ~ ltree → boolean

ltree 与 lquery 匹配吗？

ltree ? lquery[] → boolean

lquery[] ? ltree → boolean

ltree 与数组中的任何 lquery 匹配吗？

ltree @ ltxtquery → boolean

ltxtquery @ ltree → boolean

ltree 与 ltxtquery 匹配吗？

ltree || ltree → ltree

连接 ltree 路径。

ltree || text → ltree

text || ltree → ltree

将文本转换为 ltree 并连接。

ltree[] @> ltree → boolean

ltree <@ ltree[] → boolean

数组是否包含 ltree 的祖先？

ltree[] <@ ltree → boolean

ltree @> ltree[] → boolean

数组是否包含 ltree 的后代？

ltree[] ~ lquery → boolean

lquery ~ ltree[] → boolean

数组是否包含与 lquery 匹配的任何路径？

ltree[] ? lquery[] → boolean

lquery[] ? ltree[] → boolean

ltree 数组是否包含与任何 lquery 匹配的任何路径？

ltree[] @ ltxtquery → boolean

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.14中。

表 F.14.ltree函数

函数描述示例
`subltree` ( `ltree`, `start` `integer`, `end` `integer` ) → `ltree` 从位置 `start` 到位置 `end`-1（从 0 开始计数）返回 `ltree` 的子路径。 `subltree('Top.Child1.Child2', 1, 2)` → `Child1`
`subpath` ( `ltree`, `offset` `integer`, `len` `integer` ) → `ltree` 从位置 `offset` 开始返回长度为 `len` 的 `ltree` 子路径。如果 `offset` 为负数，则子路径从路径末尾开始。如果 `len` 为负数，则从路径末尾移除那么多标签。 `subpath('Top.Child1.Child2', 0, 2)` → `Top.Child1`
`subpath` ( `ltree`, `offset` `integer` ) → `ltree` 从位置 `offset` 开始返回 `ltree` 子路径，一直延伸到路径末尾。如果 `offset` 为负数，则子路径从路径末尾开始。 `subpath('Top.Child1.Child2', 1)` → `Child1.Child2`
`nlevel` ( `ltree` ) → `integer` 返回路径中的标签数。 `nlevel('Top.Child1.Child2')` → `3`
`index` ( `a` `ltree`, `b` `ltree` ) → `integer` 返回 `a` 中 `b` 的首次出现的索引，如果未找到，则返回 -1。 `index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6')` → `6`
`index` ( `a` `ltree`, `b` `ltree`, `offset` `integer` ) → `integer` 返回 `a` 中 `b` 的首次出现的索引，如果未找到，则返回 -1。搜索从索引 `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`

函数

描述

示例

subltree ( ltree, start integer, end integer ) → ltree

从位置 start 到位置 end-1（从 0 开始计数）返回 ltree 的子路径。

subltree('Top.Child1.Child2', 1, 2) → Child1

subpath ( ltree, offset integer, len integer ) → ltree

从位置 offset 开始返回长度为 len 的 ltree 子路径。如果 offset 为负数，则子路径从路径末尾开始。如果 len 为负数，则从路径末尾移除那么多标签。

subpath('Top.Child1.Child2', 0, 2) → Top.Child1

subpath ( ltree, offset integer ) → ltree

从位置 offset 开始返回 ltree 子路径，一直延伸到路径末尾。如果 offset 为负数，则子路径从路径末尾开始。

subpath('Top.Child1.Child2', 1) → Child1.Child2

nlevel ( ltree ) → integer

返回路径中的标签数。

nlevel('Top.Child1.Child2') → 3

index ( a ltree, b ltree ) → integer

返回 a 中 b 的首次出现的索引，如果未找到，则返回 -1。

index('0.1.2.3.5.4.5.6.8.5.6.8', '5.6') → 6

index ( a ltree, b ltree, offset integer ) → integer

返回 a 中 b 的首次出现的索引，如果未找到，则返回 -1。搜索从索引 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.23.3. 索引#

ltree支持多种类型的索引，可以加快指定的运算符

B 树索引超过 ltree：<、<=、=、>=、>
基于 ltree 的 GiST 索引（gist_ltree_ops opclass）：<、<=、=、>=、>、@>、<@、@、~、?
gist_ltree_ops GiST opclass 将一组路径标签近似为位图签名。其可选整数参数 siglen 确定签名长度（以字节为单位）。默认签名长度为 8 个字节。长度必须是 int 对齐的正倍数（大多数机器上为 4 个字节），最大为 2024。较长的签名会导致更精确的搜索（扫描索引的较小部分和较少的堆页），但代价是索引更大。
使用默认签名长度 8 个字节创建此类索引的示例
```
CREATE INDEX path_gist_idx ON test USING GIST (path);
```
使用签名长度 100 个字节创建此类索引的示例
```
CREATE INDEX path_gist_idx ON test USING GIST (path gist_ltree_ops(siglen=100));
```
基于 ltree[] 的 GiST 索引（gist__ltree_ops opclass）：ltree[] <@ ltree、ltree @> ltree[]、@、~、?
gist__ltree_ops GiST opclass 的工作方式类似于 gist_ltree_ops，并且也采用签名长度作为参数。 gist__ltree_ops 中 siglen 的默认值为 28 个字节。
使用默认签名长度 28 个字节创建此类索引的示例
```
CREATE INDEX path_gist_idx ON test USING GIST (array_path);
```
使用签名长度 100 个字节创建此类索引的示例
```
CREATE INDEX path_gist_idx ON test USING GIST (array_path gist__ltree_ops(siglen=100));
```
注意：此索引类型有损。

F.23.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 ~ '*[email protected].*';
                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.23.5. 转换#

ltree_plpython3u扩展为 PL/Python 中的ltree类型实现了转换。如果在创建函数时安装并指定，ltree值将映射到 Python 列表。（但目前不支持反向转换。）

警告

强烈建议将转换扩展安装在与ltree相同的模式中。否则，如果转换扩展的模式包含恶意用户定义的对象，则在安装时存在安全隐患。

F.23.6. 作者#

所有工作均由 Teodor Sigaev (<[[email protected]](/cdn-cgi/l/email-protection#85f1e0eae1eaf7c5f6f1e4e6eeabebe0f1)>) 和 Oleg Bartunov (<[[email protected]](/cdn-cgi/l/email-protection#f49b989193b487959dda998781da8781)>) 完成。有关更多信息，请参阅http://www.sai.msu.su/~megera/postgres/gist/。作者要感谢 Eugeny Rodichev 提供的帮助性讨论。欢迎提出评论和错误报告。

F.23. ltree — 层次树状数据类型# ​

F.23.1. 定义# ​

F.23.2. 运算符和函数# ​

F.23.3. 索引# ​

F.23.4. 示例# ​

F.23.5. 转换# ​

警告 ​

F.23.6. 作者# ​