Использование массивов PostgreSQL для работы с Materialized Path

Как известно иерархические структуры данных плохо ложатся на реляционную модель. Из-за этого хранение деревьев в РБД приводит к избыточности либо в количестве данных либо в количестве запросов. Есть несколько распространенных путей для решения этой проблемы. Сегодня мы поговорим о Materialized Path.

Суть этого подхода заключается в том, что мы добавляем в таблицу дополнительное поле path в котором храним список ключей предков текущей записи. Обычно они хранятся в виде строки, разделенные каким-нибудь символом, например 1.2.3. Это приводит к тому, что во всех запросах используется поиск с помощью like.

Но PostgreSQL предоставляет нам инструмент, гораздо лучше подходящий для этих целей, - массивы. И в этой статье расскажу, как работать с Materialized Path используя массивы PostgreSQL.

Создание дерева

Для начала создадим таблицу для нашего дерева и заполним ее данными. В таблице будет храниться следующее дерево (иерархия показана отступами).

id | name
-------------------
1  | item_1
2  |   item_1_1
3  |     item_1_1_1
4  |     item_1_1_2
5  |   item_1_2
6  |     item_1_2_1
7  |     item_1_2_2
8  | item_2

Запрос на создание таблицы:

CREATE SEQUENCE tree_id START 9;
CREATE TABLE tree (
  id integer primary key default NEXTVAL('tree_id'),
  path integer[] not null,
  name varchar(25) not null
);

CREATE INDEX tree_path ON tree (path);
CREATE INDEX tree_level ON tree (array_length(path, 1));

INSERT INTO tree (id, path, name) VALUES 
  (1, '{1}', 'item_1'),
  (2, '{1,2}', 'item_1_1'),
  (3, '{1,2,3}', 'item_1_1_1'),
  (4, '{1,2,4}', 'item_1_1_2'),
  (5, '{1,5}', 'item_1_2'),
  (6, '{1,5,6}', 'item_1_2_1'),
  (7, '{1,5,7}', 'item_1_2_2'),
  (8, '{8}', 'item_2');

В итоге получаем такую структуру:

id | path    | name       
-------------------------
1  | {1}     | item_1    
2  | {1,2}   | item_1_1  
3  | {1,2,3} | item_1_1_1
4  | {1,2,4} | item_1_1_2
5  | {1,5}   | item_1_2  
6  | {1,5,6} | item_1_2_1
7  | {1,5,7} | item_1_2_2
8  | {8}     | item_2    

Поиск дочерних записей

Начнем с самого простого - получения списка детей для конкретной записи. Для примера получим детей записи item_1_1 (id=2). Для этого мы используем оператор перекрытия массивов &&. С его помощью мы находим записи у которых поле path содержит в себе id предка. Для этого мы представляем id в виде массива с одним элементом при помощи конструкции array[].

Но нам нужно отсортировать список в порядке увеличения их уровня вложенности: сначала дети, потом дети детей и т.д. По сути уровень вложенности - это количество предков у элемента. Получить его мы можем посчитав длину массива path. Используем для этого функцию array_length().

SELECT * FROM tree
WHERE path && ARRAY[:id]
ORDER BY array_length(path, 1)

Поиск предков

Для того чтобы получить список предков надо получить записи у которых значение id пересекается со значением поля path нашей записи. Получим список предков для записи item_1_2_2 (id=7).

SELECT * FROM tree
WHERE id != :id 
AND array[id] && (
  SELECT path 
  FROM tree 
  WHERE id = :id
)
ORDER BY path

Добавление записей

При создании новой записи все, что нам надо - это сформировать path для новой записи из path предка и ее id. Добавим в запись item_1_2 (id=5) еще одну запись с именем item_1_2_3.

INSERT INTO tree (name, path)
values (
  'item_1_2_3', 
  (SELECT path FROM tree WHERE id = :parent_id) || (select currval('tree_id')::integer)
)

Здесь в поле path мы записываем значение path предка, полученное подзапросом. И конкатенируем его (оператор ||) с id новой записи. Обратите внимание: последовательности(sequence) возвращают значение типа biginteger, а массив у нас имеет тип integer[]. Оператор || работает только с аргументами одинакового типа, поэтому мы явно приводим текущий id к типу integer.

Перемещение записей

При перемещении записи в другого родителя будет логичным перемещать ее вместе со всеми ее потомками. Для этого нам надо взять ту часть поля path, которая соответствует текущему предку и заменить ее на значение поля path нового предка. Сделать это необходимо для выбранной записи и всех ее потомков. Т.к. каждая запись хранит полный список предков, это можно сделать одним запросом.

Для примера переместим запись item_1_1 (id=2) в нового родителя item_1_2_2 (id=7). Для этого нам в поле path надо заменить часть {1} на {1,5,7}. Данную процедуру будет не очень просто организовать в виде одного запроса. Поэтому для упрощения задачи мы заранее посчитаем текущий уровень вложенности старого предка переносимой записи. У нас он равен 2. Сделать это можно либо в хранимой процедуре либо средствами клиентского ПО и передать его в качестве аргумента.

Для начала посмотрим запрос:

UPDATE tree
SET path = (
  SELECT path
  FROM tree
  WHERE id = :new_parent_id
) || path[:level : array_length(path, 1)]
WHERE path && ARRAY[:id]

Здесь мы берем всех потомков переносимой записи вместе с ней и присваиваем им новое значение path, которое формируется из двух частей:

  1. значение path нового предка (получаем подзапросом);
  2. значение path самой записи из которой удален path старого предка.

Удаление записи

При удалении записи будет логично удалять и все ее дочерние записи. Делается это так же, как и с выборкой - через пересечение массивов:

DELETE FROM tree
WHERE path && ARRAY[:id]
ORDER BY array_length(path, 1)

Коментарии

Используйте Markdown

Thank you for comment!
Ваше сообщение будет доступно после проверки.