Evgenii Legotckoi
Evgenii Legotckoi25 сентября 2016 г. 23:37

Materialized Path в PostgreSQL

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

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

Наименование Описание
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)
Рекомендуем хостинг TIMEWEB
Рекомендуем хостинг TIMEWEB
Стабильный хостинг, на котором располагается социальная сеть EVILEG. Для проектов на Django рекомендуем VDS хостинг.

Вам это нравится? Поделитесь в социальных сетях!

Mitai .
  • 5 января 2020 г. 14:54

простите а Django MPTT в этом варианте не подходит? она вроде как раз для этих целей разрабатывалась

Evgenii Legotckoi
  • 6 января 2020 г. 14:11

Добрый день. Почитал описание Django MPTT, и да, подойдёт. Рассматривайте статью как базовую теорию.

Nomad
  • 2 ноября 2020 г. 22:02
  • (ред.)

Django MPTT использует для построения дерева алгоритм Nested Set

во вторых если надо создавать динамическое дерево прямо в хтмл документе, Django MPTT, не подойдет, а вернее подойдет только если вы знакомы с алгоритмом Nested Set, а это означает что при добавлении нового элемента в дерево надо перешитать полностью все значения записей по полям lft и rght имея в виду еще поля parent_id и tree_id

=====

вопрос к автору статьи, скажите а Materialized Path сохраняет ордер элементов дерева. предположим что у нас есть дерево:

comment_1
comment_1_1
comment_1_1_1
comment_1_2
comment_2
comment_2_1
comment_2_2
comment_3

мы тут видим 3 родителя: comment_1, comment_2, comment_3

и мы видим что у родителя comment_2 есть 2 чаилда: comment_2_1 и comment_2_2

вот если мы поменяем местами данные чаилды как Materialized Path сохранит это????

Evgenii Legotckoi
  • 28 января 2021 г. 15:06

Самый простой способ, который приходит на ум, это скопировать comment_2_1 до нового комментария comment_2_3, чтобы у него был более старший id и переписать колонку path. А оригинальный comment_2_1 удалить. Только так.

Комментарии

Только авторизованные пользователи могут публиковать комментарии.
Пожалуйста, авторизуйтесь или зарегистрируйтесь
m

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

  • Результат:85баллов,
  • Очки рейтинга6
в

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

  • Результат:50баллов,
  • Очки рейтинга-4
l

C++ - Тест 005. Структуры и Классы

  • Результат:91баллов,
  • Очки рейтинга8
Последние комментарии
k
kmssr9 февраля 2024 г. 5:43
Qt Linux - Урок 001. Автозапуск Qt приложения под Linux как сделать автозапуск для флэтпака, который не даёт создавать файлы в ~/.config - вот это вопрос ))
АК
Анатолий Кононенко5 февраля 2024 г. 12:50
Qt WinAPI - Урок 007. Работаем с ICMP Ping в Qt Без строки #include <QRegularExpressionValidator> в заголовочном файле не работает валидатор.
EVA
EVA25 декабря 2023 г. 21:30
Boost - статическая линковка в CMake проекте под Windows Ошибка LNK1104 часто возникает, когда компоновщик не может найти или открыть файл библиотеки. В вашем случае, это файл libboost_locale-vc142-mt-gd-x64-1_74.lib из библиотеки Boost для C+…
J
JonnyJo25 декабря 2023 г. 19:38
Boost - статическая линковка в CMake проекте под Windows Сделал всё по-как у вас, но выдаёт ошибку [build] LINK : fatal error LNK1104: не удается открыть файл "libboost_locale-vc142-mt-gd-x64-1_74.lib" Хоть убей, не могу понять в чём дел…
G
Gvozdik19 декабря 2023 г. 8:01
Qt/C++ - Урок 056. Подключение библиотеки Boost в Qt для компиляторов MinGW и MSVC Для решения твой проблемы добавь в файл .pro строчку "LIBS += -lws2_32" она решит проблему , лично мне помогло.
Сейчас обсуждают на форуме
P
Pisych27 февраля 2023 г. 15:04
Как получить в массив значения из связанной модели? Спасибо, разобрался:))
AC
Alexandru Codreanu19 января 2024 г. 22:57
QML Обнулить значения SpinBox Доброго времени суток, не могу разобраться с обнулением значение SpinBox находящего в делегате. import QtQuickimport QtQuick.ControlsWindow { width: 640 height: 480 visible: tr…
BlinCT
BlinCT27 декабря 2023 г. 19:57
Растягивать Image на парент по высоте Ну и само собою дял включения scrollbar надо чтобы был Flickable. Так что выходит как то так Flickable{ id: root anchors.fill: parent clip: true property url linkFile p…
Дмитрий
Дмитрий10 января 2024 г. 15:18
Qt Creator загружает всю оперативную память Проблема решена. Удалось разобраться с помощью утилиты strace. Запустил ее: strace ./qtcreator Начал выводиться весь лог работы креатора. В один момент он начал считывать фай…
Evgenii Legotckoi
Evgenii Legotckoi12 декабря 2023 г. 17:48
Побуквенное сравнение двух строк Добрый день. Там случайно не высылается этот сигнал textChanged ещё и при форматировани текста? Если решиать в лоб, то можно просто отключать сигнал/слотовое соединение внутри слота и …

Следите за нами в социальных сетях