Odpowiedź.

Praca z hierarchicznymi strukturami to klasyka relacyjnych baz danych. Przykłady: katalogi, menu drzewiaste, struktury organizacyjne.

Historia problemu: Bazy danych to model tabelaryczny. Istnieje kilka podejść do danych drzewiastych, z których każde ma swoje plusy i minusy.

Problem: Standardowy model parent_id prowadzi do wolnych rekurencyjnych SELECT'ów. Rzeczywiste zadania (wyszukiwanie wszystkich potomków, ścieżki, zliczanie poddrzew) wymagają optymalizacji.

Rozwiązanie:

Lista sąsiedziska — prosta referencja do parent_id.
Ścieżka zmaterializowana — ciąg, który odzwierciedla pełną ścieżkę.
Zestawy zagnieżdżone — przechowywanie lewych/prawych granic (left/right), co pozwala łatwo wydobywać poddrzewa.
Tabela zamknięcia — osobna tabela związków (from->to), odzwierciedlająca wszystkie relacje w drzewie.

Przykład kodu dla ścieżki zmaterializowanej (PostgreSQL):

CREATE TABLE categories (
    id SERIAL PRIMARY KEY,
    name TEXT,
    path TEXT
);

-- Przykład przechowywania path: '1/2/5/' (korzeń/podkategoria/aktualna)
SELECT * FROM categories WHERE path LIKE '1/2/%'; -- wszyscy potomkowie 2

Przykład kodu dla zestawów zagnieżdżonych:

CREATE TABLE nested_categories (
    id SERIAL PRIMARY KEY,
    name TEXT,
    lft INT NOT NULL,
    rgt INT NOT NULL
);

-- Węzły potomne
SELECT * FROM nested_categories WHERE lft > 2 AND rgt < 15;

Kluczowe cechy:

Lista sąsiedziska jest wygodna dla prostych struktur drzewiastych (niska zagnieżdżenie).
Ścieżka zmaterializowana — szybkie wydobywanie poddrzew, łatwe do zrealizowania.
Zestawy zagnieżdżone — natychmiastowe uzyskiwanie wszystkich potomków, szybkie odczyty, ale trudna modyfikacja.

Pytania pułapki.

Czy można po prostu użyć zagnieżdżonego SELECT z parent_id do wyszukiwania wszystkich potomków na dowolną głębokość?

Działa to tylko dla małych głębokości. Do wyszukiwania rekurencyjnego wymagany jest albo rekurencyjny CTE (WITH RECURSIVE), albo bardziej złożone schematy, ponieważ proste JOIN prowadzą do ogromnej liczby zapytań i złej wydajności.

Przykład:

WITH RECURSIVE cte AS (
    SELECT id, parent_id, name FROM categories WHERE id = 1
    UNION ALL
    SELECT c.id, c.parent_id, c.name
    FROM categories c
    INNER JOIN cte ON c.parent_id = cte.id
)
SELECT * FROM cte;

Dlaczego drzewo molekularne (Zestawy zagnieżdżone) szybko wydobywa poddrzewo, ale wolno dodaje/usuwa węzły?

Podczas zmiany drzewa trzeba zmieniać lft/rgt w wielu wierszach (zakres zmiany — wszystkie wartości większe niż wstawianie/usuwanie). Dla odczytu podejście jest idealne, dla częstych zmian używaj innych metod.

Kiedy używać Tabeli zamknięcia, a nie parent_id lub ścieżki zmaterializowanej?

Tabela zamknięcia idealnie sprawdza się w przypadku wielokrotnych zapytań do potomków na różnych poziomach oraz regularnego przeliczania relacji. Minusem jest to, że wymaga więcej miejsca.

Przykład:

CREATE TABLE closure (
    ancestor INT,
    descendant INT,
    depth INT
);

Typowe błędy i antywzorce

Przechowywanie hierarchii tylko przez parent_id, kiedy wymagana jest szybka wyszukiwarka zagnieżdżonych struktur.
Ręczne przeliczanie ścieżek lub lft/rgt bez funkcji pomocniczych.
Brak indeksowania kluczowych kolumn (parent_id/path/lft/rgt).

Przykład z życia

Negatywny przypadek

W sklepie internetowym kategorie są realizowane przez parent_id. Wszystkie zagnieżdżone są ustawiane ręcznie, wyszukiwanie podkategorii — zagnieżdżonymi SELECT'ami.

Plusy:

Prostota, nie wymaga rozszerzonego wsparcia.

Minusy:

Wydajność spada nawet przy 3-4 poziomach zagnieżdżenia.
Operacje przenoszenia węzłów — nieoczywiste, prowadzą do błędów logicznych.

Pozytywny przypadek

Używana jest ścieżka zmaterializowana lub tabela zamknięcia. Wszystkie zapytania o zagnieżdżone kategorie są natychmiastowe, przeliczanie — grupowymi skryptami.