Немного о деревьях

Вступление

Встречалась ли вам ситуация, когда необходимо реализовать хранение древовидной структуры в реляционной БД?



Примеров можно привести множество. Это и древовидные комментарии, и каталог продукции, и населенные пункты, разделенные по странам и областям. Я думаю, что каждый сможет самостоятельно привести несколько примеров.

В данном топике мы с вами поговорим об одной из тех возможностей, которые существуют для организации хранения деревьев в PostgreSQL — ltree.

Установка

Процесс установки будет описан для debian-подобных систем.

1. необходимо установить пакет postgresql-contrib;
2. psql -U postgres -d database-name -1 -f SHAREDIR/contrib/ltree.sql — вливаем в базу database-name содержимое модуля (SHAREDIR — каталог с разделяемыми данными PostgreSQL)
3. …
4. PROFIT!

Краткое описание

ltree позволяет хранить древовидные структуры в виде меток, а так же предоставляет широкие возможности поиска по ним. [1, 2].

Метка может состоять из букв латинского алфавита, цифр и нижнего подчеркивания. Из меток можно составлять пути, которые и хранятся в ltree.

Путь меток — это совокупность из 0 и более меток, разделенных точками. Для поиска по путям используется специальные запросы — lquery.

Примеры lquery:

1. foo — записи с путем меток в точности равным foo;
2. foo.* — записи у которых путь меток начинается с foo;
3. *.foo.* — любые записи путь меток которых содержит foo.

Модификаторы lquery:

1. *{n} — путь содержит в точности n меток;
2. *{n,} — путь содержит как минимум n меток;
3. *{n,m} — путь содержит от n до m меток;
4. *{,m} — путь содержит не более m меток.

Кроме того, существуют модификаторы для меток:

1. foo* — любая метка начинающаяся на foo;
2. foo@ — метка без учета регистра, например: Foo, FOO, FoO — подойдут;
3. foo% — выберет foo_bar, но не выберет foo и foobar.

Модификаторы можно комбинировать.

ltree можно сравнивать между собой и c lquery, т.е. стандартные операции сравнения =, <>, >, <, >=, <= полностью поддерживаются. Помимо них, введены еще несколько операций:

1. ltree @> ltree — является ли левый член выражения предком правого;
2. ltree <@ ltree — является ли левый член выражения потомком правого;
3. ltree ~ lquery или lquery ~ ltree — соответствует ли ltree запросу в lquery.

С полным списком операций и функций можно ознакомиться в официальной документации [2].

Пример использования

О деревьях мы немного узнали. Давайте попробуем реализовать на примере.

Перед нами стоит задача реализовать хранение территориальных единиц в виде: страна — регион — город.

Создадим таблицу:

create table "world" (
  "id" serial primary key,
  "name" varchar(150) not null,
  "tree" ltree not null
);

Наполним данными:

 id |      name      | tree
----+----------------+-------
  1 | Россия         | 1
  2 | США            | 2
  3 | Канада         | 3
  4 | Москва         | 1.4
  5 | Химки          | 1.4.5
  6 | Мытищи         | 1.4.6

И теперь у нас с вами, есть простой способ получить информацию. Например для получения списка всех стран достаточно выполнить следующий запрос:

select "id", "name" from "world" where "tree" ~ '*{1}' 

Для получения всех регионов России:

select "id", "name" from "world" where "tree" ~ '1.*{1}' 

Примеров применения данного инструмента можно привести множество. Но в силу обзорности данного топика остановимся на этом.

Заключение

Как мне кажется, ltree — является отличным способом организации древовидных структур. Благодаря простым и удобным методам поиска и сортировки информации, он подойдет для широкого круга задач.

В данной статье, я перечислил далеко не все возможности ltree. Совсем не был рассмотрен вопрос о индексировании, функциях и вопросы полнотекстового поиска ltxtquery. С полной документацией можно ознакомится по приведенным ниже ссылкам [1, 2].

А вообще, у PostgreSQL есть много дополнительных полезных модулей [3]. Приятного изучения!

Ссылки

1. Описание ltree на сайте разработчика
2. Описание ltree на сайте PostgreSQL
3. Contrib-модули PostgreSQL