Pull to refresh

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

PostgreSQL *

Вступление


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

PostgreSQL on tree

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

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

Установка


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

  1. необходимо установить пакет postgresql-contrib;
  2. psql -U postgres -d database-name -1 -f SHAREDIR/contrib/ltree.sql — вливаем в базу database-name содержимое модуля (SHAREDIR — каталог с разделяемыми данными PostgreSQL)
  3. 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
Tags:
Hubs:
Total votes 86: ↑84 and ↓2 +82
Views 22K
Comments Comments 54