Antwoord.

Werken met hiërarchische structuren is een klassieker in relationele databases. Voorbeelden: catalogi, boomstructuren in menu's, organisatiestructuren.

Geschiedenis van het probleem: Databases zijn op tabellen gebaseerd. Er zijn verschillende benaderingen voor boomstructuurdata, elk met zijn voor- en nadelen.

Probleem: Het standaard model met parent_id leidt tot trage recursieve SELECT's. Werkelijke taken (zoeken naar alle nakomelingen, paden, herberekenen van subbomen) vereisen optimalisatie.

Oplossingen:

Adjacency List - een eenvoudige verwijzing naar parent_id.
Materialized Path - een tekenreeks die het volledige pad weergeeft.
Nested Sets - opslag van linker/rechter grenzen (left/right) die het gemakkelijk maakt om subbomen te extraheren.
Closure Table - een aparte tabel van relaties (van->tot) die alle relaties in de boom weergeeft.

Voorbeeldcode voor Materialized Path (PostgreSQL):

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

-- Voorbeeld van padopslag: '1/2/5/' (wortel/subcategorie/huidig)
SELECT * FROM categories WHERE path LIKE '1/2/%'; -- alle nakomelingen van 2

Voorbeeldcode voor Nested Sets:

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

-- Kindknopen
SELECT * FROM nested_categories WHERE lft > 2 AND rgt < 15;

Belangrijke kenmerken:

Adjacency List is handig voor eenvoudige boomstructuren (lage diepte).
Materialized Path — snelle extractie van subbomen, eenvoudig te implementeren.
Nested Sets — onmiddellijke toegang tot alle nakomelingen, snelle lezing, maar complexe modifiëring.

Vragen met een valstrik.

Kan ik gewoon een geneste SELECT gebruiken met parent_id om alle nakomelingen op een willekeurige diepte te vinden?

Dit werkt alleen voor kleine dieptes. Voor recursief zoeken is een recursieve CTE (WITH RECURSIVE) of complexere schema's vereist, aangezien eenvoudige JOIN's leiden tot een enorme hoeveelheid aanroepen en slechte prestaties.

Voorbeeld:

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;

Waarom haalt het moleculaire boom (Nested Sets) snel een subboom op, maar is het langzaam om knopen toe te voegen/verwijderen?

Bij het wijzigen van de boom moeten de lft/rgt waarden van veel rijen direct worden aangepast (de wijzigingsstap — alle waarden groter dan de invoeging/verwijdering). Het is ideaal voor lezen, maar voor frequente wijzigingen gebruik je andere methoden.

Wanneer de Closure Table gebruiken in plaats van parent_id of materialized path?

Closure Table werkt perfect voor veelvuldig verzoeken naar nakomelingen op elke niveau en regelmatige herberekening van relaties. Minpuntje — vereist meer ruimte.

Voorbeeld:

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

Typische fouten en anti-patronen

Opslag van hiërarchie alleen via parent_id, wanneer snelle zoekopdrachten naar geneste structuren vereist zijn.
Handmatig herberekenen van paden of lft/rgt zonder hulpfuncties.
Ontbreken van indexering van sleutelkolommen (parent_id/path/lft/rgt).

Voorbeeld uit de praktijk

Negatief geval

In een online winkel zijn categorieën geïmplementeerd met parent_id. Alle geneste worden handmatig ingesteld, het zoeken naar subcategorieën gebeurt met geneste SELECT's.

Voordelen:

Eenvoud, geen uitgebreide ondersteuning vereist.

Nadelen:

Prestaties dalen zelfs op 3-4 niveau's van diepte.
Verplaatsingsoperaties van knopen zijn niet voor de hand liggend en leiden tot logische fouten.

Positief geval

Er wordt gebruik gemaakt van materialized path of closure table. Alle verzoeken om geneste categorieën zijn snel, herberekening gebeurt met groepsscripts.