Евгений Легоцкой25 сентября 2016 г. 13: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 хостинг.
Поддержать автора Donate

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

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

  • #
  • 2 ноября 2020 г. 11: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 сохранит это????

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

Комментарии

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

Позвольте мне порекомендовать вам отличный хостинг, на котором расположен EVILEG.

В течение многих лет Timeweb доказывает свою стабильность.

Для проектов на Django рекомендую VDS хостинг

Посмотреть Хостинг
ВС

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

  • Результат:14баллов,
  • Очки рейтинга-10
ВС

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

  • Результат:14баллов,
  • Очки рейтинга-10
ИП

C++ - Тест 004. Указатели, Массивы и Циклы

  • Результат:10баллов,
  • Очки рейтинга-10
Последние комментарии
A
  • Andrey
  • 28 апреля 2021 г. 1:25

Django - Урок 036. Как добавить аутентификацию через социальные сети. ВКонтакте

после того как дам разрешение для просмотра моего емайл, вот такая ошибка: AuthForbidden at /social-auth/complete/vk-oauth2/ Your credentials aren't allowed Вот сетингс: SOC…
DV

Qt/C++ - Урок 051. QMediaPlayer - Аудио плеер на Qt

Добрый вечер. Хотел бы получить консультацию по работе с проектом на Mac OS. Открыл проект в QT и собрал его. Проблема в том, что он не воспроизводит треки и их названия зацикленно мелькают в по…
SS

Как соответствовать новым требованиям Google Play

Добрый день. Спасибо вам огромное за вашу статью! только начинаю изучать QT под Андроид 4 дня потратил на то чтобы подобрать версию QT которая наконец то скомпилирует мне на windo…
YA

PyQt5 - Урок 009. Использование QThread с применением moveToThread

Hello. Let's say I want to send some variables to "run" define. How can we do that? I modified your code, I tried something like below, but the GUI is frozen that way. I could not be able to und…
R

Распознавание изображений на Python с помощью TensorFlow и Keras

почему то вместо 50000 обрабатывает по 782 картинки кажду. эпоху
Сейчас обсуждают на форуме
M

Qt/QML/Android(navigation button) - Стандартные клавиши навигации Андроид

Здравствуйте, пытаюсь заставить работать стандартную андроид-клавишу "назад", пытался разными способоами, они приведены в закомментированном коде. В том числе использовал https://evileg.com/ru/f…
M

Как включить OpenGL в Adnroid эмуляторе QtCreator

Здравствуйте, у меня работают виртуальные машины с Android, но только в дефолтной был включен OpenGL. Потом я удалил дефолтную, создал новые, а в них OpenGL отключен. Справа на втором скриншоте …

QScrollArea dynamically add QCheckBoxes

Всё правильно. Это просто спамер, который отправился в вечный бан.

qml зажатая кнопка мыши в одной MouseArea и сигналы мыши из другой MouseArea

добрый, вы не пробовали отслеживать область видимости мышки через: _mouseArea.containsMouse и когда мышка будет в другой зоне видимости обрабатывать ее состояния?
О нас
Услуги
© EVILEG 2015-2021
Рекомендует хостинг TIMEWEB