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

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

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