Реклама

Materialized Path в PostgreSQL

PostgreSQL, MaterializedPath

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

Распространёнными подходами для организации древовидных структур являются:

Adjacency List
Список смежных вершин

Организация структуры данных заключается в том, что каждый объект хранит информацию о родительском объекте, то есть в строке таблицы имеется дополнительное поле, в котором указывается ID объекта, в который вложен данный объект.
Nested Set
Вложенное множество
Вложенные множества хранят информацию не Только о так называемых левом и правом ключе, а также уровне вложенности. Данный вариант организации структуры данных удобен для чтения, но более тяжело поддаётся модификации.
Materialized Path
Материализованный путь
Идея этой структуры данных заключается в том, что каждая запись хранит полный путь к корневому элементу дерева.

Рассмотрение этих структур данных было вызвано необходимостью внедрения на сайт поддержки комментариев для статей.

Adjacency List показался мне несколько неудобным решением для организации комментариев, поскольку могут быть проблемы с нахождением родительских объектов и выстраиванием древовидной структуры, хотя сам по себе подход позволяет довольно быстро удалять и добавлять элементы.

Nested Set довольно громоздкий метод для организации комментариев на небольшом сайте, да если даже посмотреть в сторону крупных ресурсов, наподобие Хабра, то там под статьями не так уж часто бывает по 5000 комментариев. Также меня смутил тот факт, что необходимо будет добавлять скрываемый root элемент, так называемый первый пустой комментарий в статье, от которого будет строится всё дерево. Зачем плодить лишние сущности? - Хотя может я и ошибаюсь. Ну и последним аргументом "против" стала необходимость пересчёта ключей при добавлении новых комментариев. В общем, несмотря на преимущества данной структуры, в рамках данного сайта и его текущего состояния - этот путь хранения комментариев станет стрельбой из пушки по воробьям.

А вот Materialized Path показался как раз тем, что нужно. Каждый комментарий содержит полный путь. И при этом под статьёй может организовываться несколько деревьев комментариев. То есть любой комментарий, который находится на первом уровне, автоматически считается корневым для своего дерева. А при добавлении нового комментария необходимо взять полный путь из будущего родителя и прибавить к нему только лишь ID нового комментария. К тому же применительно к конкретной БД, а речь идёт о PostgreSQL , хранение пути можно представить в виде массива целочисленных значений, поскольку PostgreSQL поддерживает массивы (Кстати, чем больше читаю о работе с PostgreSQL в противовес MySQL , тем больше он мне нравится). А также при выборке деревьев комментариев можно выполнять сортировку по данным массивам, что автоматически позволит располагать все комментарии в хронологическом порядке с сохранением структуры дерева, а потом уже в шаблоне Django сформировать страницу в обычном цикле без всяких рекурсий, поскольку все комментарии уже будут отсортированы должным образом средствами базы данных.

Использование в PostgreSQL

А теперь представим, что у нас есть некая абстрактная страница, у которой имеется несколько комментариев со следующей структурой:

id | name
-------------------
1  | comment_1
2  |   comment_1_1
3  |     comment_1_1_1
4  |   comment_1_2
5  | comment_2
6  |     comment_2_1
7  |     comment_2_2
8  | comment_3

В итоге структура комментария будет формироваться следующим запросом:

CREATE TABLE comments (
  id serial primary key,
  path integer[] not null,
  content varchar(200) not null
);

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

Заполним базу данных комментариями:

INSERT INTO comments (path, content) VALUES 
  ('{1}', 'comment_1'),
  ('{1,2}', 'comment_1_1'),
  ('{1,2,3}', 'comment_1_1_1'),
  ('{1,4}', 'comment_1_2'),
  ('{5}', 'comment_2'),
  ('{5,6}', 'comment_2_1'),
  ('{5,7}', 'comment_2_2'),
  ('{8}', 'comment_3');

В итоге получим следующую таблицу:

id | path    | content       
-------------------------
1  | {1}     | comment_1    
2  | {1,2}   | comment_1_1  
3  | {1,2,3} | comment_1_1_1
4  | {1,4}   | comment_1_2
5  | {5}     | comment_2  
6  | {5,6}   | comment_2_1
7  | {5,7}   | comment_2_2
8  | {8}     | comment_3  

Поиск дочерних элементов

Для поиска дочерних элементов необходимо использовать оператор перекрытия массива && . С помощью данного оператора будем находить элементы, которые содержат в своём пути ID родительского элемента. Выберем все дочерние элементы для элемента с ID = 1.

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

В приведённом ниже запросе :id = 1 .

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

На выходе получим следующим вывод:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  4 | {1,4}   | comment_1_2
  3 | {1,2,3} | comment_1_1_1
(4 rows)

Поиск родительских элементов

Получение списка всех родительских элементов заключается в том, чтобы выбрать все элементы, которые входят в состав пути текущего элемента. Например получим список родительских элементов комментария с ID = 3 , то есть comment_1_1_1.

В приведённом ниже запросе :id = 3.

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

В результате получим следующий вывод:

 id | path  |   content   
----+-------+-------------
  1 | {1}   | comment_1
  2 | {1,2} | comment_1_1
(2 rows)

Добавление элементов

При создании новой записи нам необходимо сформировать путь по текущему пути родительского элемента, к которому будет добавлен ID нового элемента. Допустим добавим новую запись, у которой ID родительского элемента будет равен 4.

В ниже следующем запросе :id = 4.

INSERT INTO comments (content, path)
values (
  'comment_1_2_3', 
  (SELECT path FROM comments WHERE id = :id) || (select currval('comments_id_seq')::integer)
);

Оператор || конкатенирует путь родительского элемента с ID нового элемента. При этом получая новое значение ID из последовательности comments_id_seq , которая создаётся автоматически при создании таблицы, нам необходимо выполнить приведение типов, поскольку путь содержит массив типа Integer[] , а currval возвращает тип biginteger .

Получим следующую таблицу:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  3 | {1,2,3} | comment_1_1_1
  4 | {1,4}   | comment_1_2
  5 | {5}     | comment_2
  6 | {5,6}   | comment_2_1
  7 | {5,7}   | comment_2_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
(9 rows)

Удаление элемента

Удаление элемента сделаем с удалением всех дочерних элементов, что также реализуется через пересечение массивов.

Например удалим элемент с ID равным 5. ( :id = 5 )

DELETE FROM comments
WHERE path && ARRAY[:id];

В результате таблица станет такой:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  2 | {1,2}   | comment_1_1
  3 | {1,2,3} | comment_1_1_1
  4 | {1,4}   | comment_1_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
(6 rows)

Перемещение элемента

В заключение сделаем перемещение одного из элементов вместе с потомками на другой элемент. Поскольку выбирать уже особо не из чего, то переместим элемент с ID = 2, на элемент с ID равным 8.

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

Единственная сложность состоит в том, что для получения уровня элемента потребуется написать хранимую процедуру, которая поможет нам сделать перемещение одним запросом. Назовём её level и будем передавать в неё ID того элемента, который будем перемещать.

CREATE OR REPLACE FUNCTION level(element_id integer) RETURNS integer AS
$$
DECLARE result integer;
BEGIN
SELECT array_length(path, 1) FROM comments WHERE comments.id = element_id INTO result;
RETURN result;
END
$$ LANGUAGE plpgsql;

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

В данном запросе имеется:

  • :new_parent_id - это уникальный идентификатор будущего родителя, (Равен 8 );
  • :movable_id - это уникальный идентификатор переносимого элемента (Равен 2).
UPDATE comments
SET path = (
  SELECT path
  FROM comments
  WHERE id = :new_parent_id
) || path[(SELECT level(:movable_id)) : array_length(path, 1)]
WHERE path && ARRAY[:movable_id];

В результате получим таблицу следующего вида:

 id |  path   |    content    
----+---------+---------------
  1 | {1}     | comment_1
  4 | {1,4}   | comment_1_2
  8 | {8}     | comment_3
  9 | {1,4,9} | comment_1_2_3
  2 | {8,2}   | comment_1_1
  3 | {8,2,3} | comment_1_1_1
(6 rows)

Реклама

Комментарии

Комментарии

Только авторизованные пользователи могут оставлять комментарии.
Пожалуйста, Авторизуйтесь или Зарегистрируйтесь
  • BlinCT
  • 22 октября 2017 г. 12:46

C++ - Тест 003. Условия и циклы

  • Результат 64 баллов
  • Очки рейтинга -1
  • Kiops
  • 22 октября 2017 г. 3:56

C++ - Тест 001. Первая программа и типы данных

  • Результат 86 баллов
  • Очки рейтинга 6
  • Kiops
  • 22 октября 2017 г. 2:41

Qt - Тест 001. Сигналы и слоты

  • Результат 100 баллов
  • Очки рейтинга 10
Последние комментарии
  • EVILEG
  • 21 октября 2017 г. 3:06

Qt/C++ - Урок 031. QCustomPlot - строим график по времени

Добавил архив с проектом

  • EVILEG
  • 20 октября 2017 г. 20:06

Qt/C++ - Урок 031. QCustomPlot - строим график по времени

После работы поищу, должен где-то быть на винте.

  • Миша
  • 20 октября 2017 г. 20:04

Qt/C++ - Урок 031. QCustomPlot - строим график по времени

не могли бы вы выложить архив с рабочей версией скрипта?

  • EVILEG
  • 20 октября 2017 г. 20:03

Qt/C++ - Урок 030. QCustomPlot - быстрый старт в работе с графиками

Использование дизайнера в Qt Creator и использование ui файлов является распространённой практикой в Qt фреймворке. Написать отдельную статью про то, что это такое? - может быть. Опи...

  • Миша
  • 20 октября 2017 г. 19:43

Qt/C++ - Урок 030. QCustomPlot - быстрый старт в работе с графиками

Но почему вы это не описали? Не могли бы вы описать.

Сейчас обсуждают на форуме
  • EVILEG
  • 22 октября 2017 г. 12:05

Закрепление якорей в момент создания объекта через JS

Добрый день! Якоря - это не те свойства, которые можно устанавливать сразу по инициализации, лучше их править после создания объекта, поскольку при одновременной установке они могут в...

  • EVILEG
  • 21 октября 2017 г. 23:33

Создание истории редактирования постов на сайте

Ясно. Тогда я лучше не буду тратить время на его проверку. Тем более, что я использую гугловский prettyprint для подсветки кода. Спасибо за информацию.

QFile::copy() возвращает false

Получилось! Спасибо огромное! path1 = "C:/Users/555/Pictures/00GAF13AP001-002.jpg"true

  • cordsac
  • 19 октября 2017 г. 15:49

How can I select the QGraphicView Item and change the properties

Ok I'll check it sir,If you can please do article(tutorial) about this,Its really useful.Thank you if you can give me some sample code when you free.thanks again

  • cordsac
  • 17 октября 2017 г. 19:28

How can I open SVG file through QT

Okay,Thank you sir :)