ltree — иерархический древовидный тип данных

note

Эта страница переведена при помощи нейросети GigaChat.

Модуль реализует тип данных ltree для представления меток данных, хранящихся в иерархической древовидной структуре. Предоставляются обширные возможности для поиска по деревьям меток.

Этот модуль считается «надежным», то есть его могут устанавливать обычные пользователи с привилегией CREATE на текущей базе данных.

Определения

Метка представляет собой последовательность буквенно-цифровых символов, подчеркиваний и дефисов. Допустимые диапазоны буквенно-цифровых символов зависят от локали базы данных. Например, в локали C разрешены символы A-Za-z0-9_-. Длина метки не должна превышать 1000 символов.

Примеры: 42, Personal_Services

Путь метки – это последовательность из нуля или более меток, разделенных точками, например L1.L2.L3, представляющая путь от корня иерархического дерева к конкретному узлу. Длина пути метки не может превышать 65 535 меток.

Пример: 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.

  Кроме того, можно написать несколько возможно измененных непустых элементов, разделенных | (ИЛИ), чтобы соответствовать любому из этих элементов, и поместить ! (НЕ) в начало непустой группы для соответствия любой метке, которая не соответствует ни одной из альтернатив. Квантификатор, если он есть, ставится в конце группы, это означает некоторое количество совпадений для всей группы (то есть некоторое количество меток, соответствующих или не соответствующих ни одной из альтернатив).

  Вот аннотированный пример использования 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. Слова могут быть объединены с помощью & (И), | (ИЛИ), ! (НЕ) и скобками. Ключевое отличие от lquery заключается в том, что ltxtquery соответствует словам без учета их положения в пути метки.

  Вот пример ltxtquery:

  Europe & Russia*@ & !Transportation

  Это будет соответствовать путям, которые содержат метку Europe и любую метку, начинающуюся с Russia (без учета регистра), но не путям, содержащим метку Transportation. Местоположение этих слов внутри пути не имеет значения. Кроме того, когда используется %, слово может быть сопоставлено с любым словом, разделенным подчеркиванием, внутри метки, независимо от положения.

Примечание: ltxtquery допускает наличие пробелов между символами, но ltree и lquery нет.

Операторы и функции

Тип ltree имеет обычные операторы сравнения =, <>, <, >, <=, >=. Сравнение сортируется в порядке обхода дерева с сортировкой дочерних элементов узла по тексту метки. Кроме того, доступны специализированные операторы, показанные в таблице ниже.

Операторы ltree:

Оператор	Описание
ltree @> ltree → boolean	Является ли левый аргумент предком правого (или равным)?
ltree <@ ltree → boolean	Является ли левый аргумент потомком правого (или равным)?
ltree ~ lquery → boolean	Совпадает ли ltree с lquery?
ltree ? lquery[] → boolean	Совпадает ли ltree с любым lquery в массиве?
ltree @ ltxtquery → boolean	Совпадает ли ltree с ltxtquery?
ltree || ltree → ltree	Конкатенирует пути ltree
ltree || text → ltree	Преобразует текст в ltree и объединяет
ltree[] @> ltree → boolean	Содержит ли массив предка элемента ltree?
ltree[] <@ ltree → boolean	Содержит ли массив потомка элемента ltree?
ltree[] ~ lquery → boolean	Содержит ли массив любой путь, соответствующий элементу lquery?
ltree[] ? lquery[] → boolean	Содержит ли массив ltree любой путь, соответствующий любому элементу lquery?
ltree[] @ ltxtquery → boolean	Содержит ли массив какой-либо путь, соответствующий ltxtquery?
ltree[] ?@> ltree → ltree	Возвращает первый элемент массива, который является предком ltree, или NULL, если нет
ltree[] ?<@ ltree → ltree	Возвращает первый элемент массива, который является потомком ltree, или NULL, если нет
ltree[] ?~ lquery → ltree	Возвращает первый элемент массива, соответствующий lquery, или NULL, если нет
ltree[] ?@ ltxtquery → ltree	Возвращает первый элемент массива, соответствующий ltxtquery, или NULL, если нет

Операторы <@, @>, @ и ~ имеют аналоги ^<@, ^@>, ^@, ^~, которые одинаковы за исключением того, что они не используют индексы. Они полезны только для целей тестирования.

Доступные функции показаны в таблице ниже.

Функции ltree:

Функция	Описание	Пример(ы)
subltree ( ltree, start integer, end integer ) → ltree	Возвращает подстроку из ltree от позиции start до позиции end-1 (счет начинается с 0)	subltree('Top.Child1.Child2', 1, 2) → Child1
subpath ( ltree, offset integer, len integer ) → ltree	Возвращает подстроку из ltree, начиная с позиции offset, длиной len. Если offset отрицательный, подстрока начинается так далеко от конца пути. Если len отрицательная, оставляет столько меток в конце пути	subpath('Top.Child1.Child2', 0, 2) → Top.Child1
subpath ( ltree, offset integer ) → ltree	Возвращает подстроку из ltree, начиная с позиции offset, простирающейся до конца пути. Если offset отрицательный, подстрока начинается так далеко от конца пути	subpath('Top.Child1.Child2', 1) → Child1.Child2
nlevel ( ltree ) → integer	Возвращает количество меток в пути	nlevel('Top.Child1.Child2') → 3
index ( a ltree, b ltree ) → integer	Возвращает позицию первого вхождения b в a или -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	Возвращает позицию первого вхождения b в a или -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

Индексы

ltree поддерживает несколько типов индексов, которые могут ускорить указанные операторы:

• B-дерево по значениям ltree: <, <=, =, >=, >.

• Хеш-индекс по значениям ltree: =.

• GiST по значениям ltree (класс операторов gist_ltree_ops): <, <=, =, >=, >, @>, <@, @, ~, ?

  Класс операций GiST для gist_ltree_ops аппроксимирует набор меток пути в виде сигнатуры битовой карты. Его необязательный целочисленный параметр siglen определяет длину подписи в байтах. Длина подписи по умолчанию составляет 8 байт. Длина должна быть положительным значением до 2024, кратным выравниванию по целым (int) (4 байта на большинстве машин). Более длинные подписи приводят к более точному поиску (сканированию меньшей доли индекса и меньшего количества страниц кучи), за счет увеличения размера индекса.

  Пример создания такого индекса с длиной подписи по умолчанию 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));

• GiST-индекс по массиву ltree[] (gist__ltree_ops opclass): ltree[] <@ ltree, ltree @> ltree[], @, ~, ?

  gist__ltree_ops Класс операций GiST работает аналогично gist_ltree_ops и также принимает длину подписи в качестве параметра. Значение по умолчанию для siglen в gist__ltree_ops составляет 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));

  Примечание: Индекс этого типа является неточным.

Пример

Этот пример использует следующие данные (также доступны в файле 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);
CREATE INDEX path_hash_idx ON test USING HASH (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)

Преобразования

Расширение ltree_plpython3u реализует преобразование для типа ltree для PL/Python. Если он установлен и указан при создании функции, значения ltree отображаются на списки Python (обратный процесс в настоящее время не поддерживается).

Внимание

Рекомендуется установить расширение преобразования в той же схеме, что и ltree. В противном случае существует опасность нарушения безопасности во время установки, если схема расширения преобразования содержит объекты, определенные враждебным пользователем.