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

Модуль реализует тип данных 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 поддерживает несколько типов индексов, которые могут ускорить указанные операторы:

• 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 (обратный процесс в настоящее время не поддерживается).