Evgenii Legotckoi
Evgenii Legotckoi25 вересня 2016 р. 13:37

Матеріалізований шлях у 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 .
  • 05 січня 2020 р. 03:54

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

Evgenii Legotckoi
  • 06 січня 2020 р. 03:11

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

Nomad
  • 02 листопада 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 сохранит это????

Evgenii Legotckoi
  • 28 січня 2021 р. 04:06

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

Коментарі

Only authorized users can post comments.
Please, Log in or Sign up
m
  • molni99
  • 26 жовтня 2024 р. 08:37

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

  • Результат:80бали,
  • Рейтинг балів4
m
  • molni99
  • 26 жовтня 2024 р. 08:29

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

  • Результат:20бали,
  • Рейтинг балів-10

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

  • Результат:42бали,
  • Рейтинг балів-8
Останні коментарі
A
ALO1ZE19 жовтня 2024 р. 15:19
Читалка файлів fb3 на Qt Creator Подскажите как это запустить? Я не шарю в программировании и кодинге. Скачал и установаил Qt, но куча ошибок выдается и не запустить. А очень надо fb3 переконвертировать в html
ИМ
Игорь Максимов05 жовтня 2024 р. 14:51
Django - Урок 064. Як написати розширення для Python Markdown Приветствую Евгений! У меня вопрос. Можно ли вставлять свои классы в разметку редактора markdown? Допустим имея стандартную разметку: <ul> <li></li> <li></l…
d
dblas505 липня 2024 р. 18:02
QML - Урок 016. База даних SQLite та робота з нею в QML Qt Здравствуйте, возникает такая проблема (я новичок): ApplicationWindow неизвестный элемент. (М300) для TextField и Button аналогично. Могу предположить, что из-за более новой верси…
k
kmssr09 лютого 2024 р. 02:43
Qt Linux - Урок 001. Автозапуск програми Qt під Linux как сделать автозапуск для флэтпака, который не даёт создавать файлы в ~/.config - вот это вопрос ))
АК
Анатолий Кононенко05 лютого 2024 р. 09:50
Qt WinAPI - Урок 007. Робота з ICMP Ping в Qt Без строки #include <QRegularExpressionValidator> в заголовочном файле не работает валидатор.
Тепер обговоріть на форумі
jd
jasmine disouza28 жовтня 2024 р. 11:58
GeForce Now India: Unlocking the Future of Cloud Gaming GeForce Now India has a major impact on the gaming scene by introducing NVIDIA's cloud gaming service to Indian gamers. GeForce Now India lets you stream top-notch PC games on any device, from b…
9
9Anonim25 жовтня 2024 р. 16:10
Машина тьюринга // Начальное состояние 0 0, ,<,1 // Переход в состояние 1 при пустом символе 0,0,>,0 // Остаемся в состоянии 0, двигаясь вправо при встрече 0 0,1,>…
J
JacobFib17 жовтня 2024 р. 10:27
добавить qlineseries в функции Пользователь может получить любые разъяснения по интересующим вопросам, касающимся обработки его персональных данных, обратившись к Оператору с помощью электронной почты https://topdecorpro.ru…
ИМ
Игорь Максимов03 жовтня 2024 р. 11:05
Реализация навигации по разделам Спасибо Евгений!
JW
Jhon Wick01 жовтня 2024 р. 22:52
Indian Food Restaurant In Columbus OH| Layla’s Kitchen Indian Restaurant If you're looking for a truly authentic https://www.laylaskitchenrestaurantohio.com/ , Layla’s Kitchen Indian Restaurant is your go-to destination. Located at 6152 Cleveland Ave, Colu…

Слідкуйте за нами в соціальних мережах