Увійти Реєстрація
Вакансії
Вакансії Laravel Компанії Статистика
Підготовка
Як підготуватися Співбесіди Тестування Документація
Блог
Всі статті Серії
Екосистема
Пакети Ресурси Проєкти Інструменти Події Відео
Інше
Про нас Реклама

Як зберігати деревовидні дані в реляційній базі?

Категорії, оргструктура, коментарі з відповідями, меню - дерева. Є кілька моделей, кожна з компромісами між простотою запису й читання.

1. Список суміжності (adjacency list) - parent_id:

CREATE TABLE categories (
    id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    parent_id bigint REFERENCES categories (id),
    name text NOT NULL
);
  • Найпростіше: вставка й переміщення - зміна одного parent_id, є зовнішній ключ.
  • Піддерево чи шлях до кореня - через WITH RECURSIVE. У PostgreSQL це працює добре, тож для більшості задач цього достатньо.

2. Матеріалізований шлях - шлях до вузла зберігається рядком: 1.5.12.

CREATE EXTENSION IF NOT EXISTS ltree;
ALTER TABLE categories ADD COLUMN path ltree;
CREATE INDEX categories_path_gist ON categories USING gist (path);

SELECT * FROM categories WHERE path <@ '1.5';     -- усе піддерево
SELECT * FROM categories WHERE path @> '1.5.12';  -- усі предки
  • Піддерево й предки - одним індексованим запитом без рекурсії; глибина - nlevel(path).
  • Переміщення вузла - оновлення шляхів усього піддерева.

3. Вкладені множини (nested sets) - кожен вузол має lft і rgt, піддерево - усе в проміжку між ними.

  • Дуже швидке читання піддерев і підрахунок нащадків.
  • Вставка чи переміщення перераховує межі для великої частини дерева - погано для дерев, що часто змінюються. У Laravel - пакет kalnoy/nestedset.

4. Таблиця замикань (closure table) - окрема таблиця всіх пар «предок - нащадок» з глибиною.

  • Будь-які запити до ієрархії - простими JOIN з індексами.
  • Таблиця зв'язків росте як O(n × глибина); вставка й переміщення - кілька запитів.

Як обирати:

  • Типова ієрархія (категорії, меню) у PostgreSQL - parent_id + WITH RECURSIVE, а за потреби в швидких запитах до піддерев - додати ltree.
  • Дерево рідко змінюється, а читається постійно - nested sets чи closure table.
  • Дуже глибокі дерева з частими переміщеннями - adjacency list.

Не забути: захист від циклів (вузол не може стати нащадком самого себе) і обмеження глибини для даних від користувачів.

Докладніше в документації: ltree

Схожі питання