Antwoord.

Werken met bomen en hiërarchieën is een veelvoorkomende situatie in SQL-programmering: productcategorieën, organisatiestructuren, menu's. Oorspronkelijk ondersteunden de meeste DBMS alleen een verwijzing naar de ouder (ParentId), maar na verloop van tijd zijn er alternatieve methoden ontstaan, zoals geneste sets en paden (Path), evenals recursieve queries via CTE.

Probleem van de traditionele Parent-Child aanpak is de lage snelheid bij het doorlopen van grote hiërarchieën; selecties die dieper zijn dan 2-3 leiden tot een explosieve toename van JOINs. Complexere technieken (Nested Sets, Path Enumeration) versnellen massale doorlopen, maar bemoeilijken invoegen/verwijderen.

Oplossing is het kiezen van het optimale opslagmodel voor een specifieke taak:

Voor zeldzame wijzigingen en massale lezing: Nested Sets (behoud van de grenzen left/right in knopen voor snelle zoektocht naar afstammelingen)
Voor frequente wijzigingen: Adjacency List + recursieve CTE
Voor snelle padzoektochten — Path en opslaan van het volledige pad in een string

Voorbeeld van recursief zoeken naar een subboom via CTE:

WITH RecursiveTree AS (
  SELECT id, parent_id, name, 0 as level
  FROM categories
  WHERE parent_id IS NULL
  UNION ALL
  SELECT c.id, c.parent_id, c.name, rt.level + 1
  FROM categories c
  INNER JOIN RecursiveTree rt ON c.parent_id = rt.id
)
SELECT * FROM RecursiveTree;

Belangrijke kenmerken:

Kies de opslagstructuur voor het scenario (Parent-Child, Nested Sets, Path)
Gebruik recursieve CTE voor willekeurige dieptes
Beoordeel de frequentie van wijzigingen en lezing voor het kiezen van de optimale methode

Vragen met een addertje onder het gras.

Kan de opslag van bomen worden vervangen door één denormaliseerde tabel met één niveau van verwijzingen, als de diepte vastligt?

Alleen als de diepte klein is en altijd vastligt (2-3 niveaus) — verder worden JOINs onbeheerbaar en wordt het moeilijker om wijzigingen door te voeren.

Zal CTE niet "vastlopen" met grote bomen — zijn er geen beperkingen op de stack, diepte van recursie?

Ja, in de meeste DBMS zijn er limieten ingesteld voor de diepte van recursie (bijvoorbeeld, 100/32767). Voor bomen met 1000+ niveaus is handmatige controle van de diepte of aangepaste traverserings-/splitalgoritmen vereist.

Zijn Nested Sets de oplossing voor alle problemen?

Nee, nested sets zoeken onmiddellijk alle afstammelingen, maar invoegen/verwijderen vereist massale updates van alle indices links/rechts — dit is traag bij een groot aantal frequente wijzigingen.

Voorbeeld van invoegen (vereenvoudigd):

UPDATE tree SET lft = lft + 2 WHERE lft > @parent_right;
UPDATE tree SET rgt = rgt + 2 WHERE rgt >= @parent_right;
INSERT INTO tree(id, name, lft, rgt) VALUES(@new_id, @name, @parent_right, @parent_right + 1);

Typische fouten en anti-patronen

Verwachting dat Parent-Child eenvoudig schaalt — bij een diepe boom snel toenemende kosten
Geneste sets voor gegevens in bewerking (invoegen/verwijderen) — duur
Geen rekening houden met CTE-limieten/Stack Overflow in grote bomen

Voorbeeld uit de praktijk

Negatief geval

Een grote webwinkel bewaarde de boom van categorieën in een adjacency list en bouwde menu's met geneste subquery's. Bij 6+ niveaus van het menu duurde de hoofdaanroep enkele minuten, en elke wijziging in de boom leidde tot cascade-updates. Voordelen:

Eenvoudige code
Ondersteuning van standaard SQL-schema

Nadelen:

Trage doorloop, moeilijk om aggregaten en rapporten op te stellen

Positief geval

We gingen over op Nested Sets voor statische bomen (categorieën), en voor paden in het menu — op Path. We gebruikten CTE voor dynamische scenario's. Het zoeken naar afstammelingen werd onmiddellijk, wijzigingen gebeurden in batches. Voordelen:

Snelle zoekopdracht naar elk niveau van diepte
Flexibiliteit, verschillende modellen voor verschillende taken