Hiërarchie in de database

Niet te lang geleden stond er een artikel op Netters over het taggen van berichten in plaats van een hiërarchische structuur. In principe een goed systeem voor nieuwberichten en artikelen bijvoorbeeld, maar in veel gevallen heb je nog steeds een structuur nodig die vast staat. Een forum is hiervan een goed voorbeeld, taggen werkt hier niet.

Een forum heeft vaak subforums, en deze subforums kunnen weer diepere subforums bevatten, en die weer diepere subforums, enzovoorts. Nu heeft een forum vaak een beperkte diepte, je zal niet snel een forum tegen komen die een grotere diepte heeft dan vijf. In dit artikel gebruik ik de volgende boom structuur om het één en ander uit te leggen:

Als je deze structuur in de database zou willen zetten dan kom je al snel problemen tegen. Aangezien de meeste databases simpele tabellen zijn, zullen we het hiërarchisch model op een platte manier de database in zien te krijgen.

Manieren om een boom structuctuur in de database te zetten

Het niet genormaliseerde model

Mensen die nog niet zolang met databases werken zullen het volgende bedenken:

ID	Niveau 1	Niveau 2	Niveau 3	Niveau 4
1	Fruit	Groen	Klein	Druif
2	Fruit	Groen	Klein	Kiwi
3	Fruit	Groen	Groot	Peer
4	Fruit	Rood	Appel	Null
5	Fruit	Rood	Aardbei	Null
6	Fruit	Geel	Banaan	Null
7	Fruit	Geel	Citroen	Null
8	Fruit	Geel	Perzik	Null

De reden dat deze manier niet goed is is simpel: de structuur staat vast, het is onmogelijk om later een extra niveau toe te voegen zonder de database aan te hoeven passen. Op deze mogelijkheid wil ik niet te lang in gaan aangezien de meesten zullen snappen dat dit simpelweg fout is.

Een database dient genormaliseerd te zijn, over database normalisatie staan genoeg artikelen online daarom ga ik niet in op wat normalisatie inhoudt.

Het genormaliseerde adjency list model

Het genormaliseerde model ziet er zou uit:

ID	Parent_ID	Name
1	Null	Fruit
2	1	Groen
3	2	Klein
4	3	Druif
5	3	Kiwi
6	2	Groot
7	6	Peer
8	1	Rood
9	8	Appel
10	8	Aardbei
11	1	Geel
12	11	Banaan
13	11	Citroen
14	11	Perzik

Dit heet een Adjacency List Model.

In principe is dit een prima manier om gestructureerd dingen in de database te zetten. Er zit alleen één groot nadeel aan: het is heel onhandig. Als ik bijvoorbeeld het deel van de boomstructuur wil ophalen dat boven Kiwi staat dan zou ik de volgende query uit moeten voeren:

SELECT
a.Name AS naam_1,
b.Name AS naam_2 ,
c.Name AS naam_3,
d.Name AS naam_4
FROM
tabel_naam AS a
WHERE
ID = 5
JOIN tabel_naam AS b
ON a.ID = b.ID
JOIN tabel_naam AS c
ON b.ID = c.ID
JOIN tabel_naam AS d
ON c.ID = d.ID;

Deze self-join is ten eerste niet erg snel als je grotere datasets krijgt, daarnaast weet je niet van te voren hoe vaak je de self-join uit moet voeren. Er zou dus eerst een query moeten worden uitgevoerd om te kijken hoe diep het element in de boomstructuur staat.

Al met al kost dit een hoop code en een hoop tijd, nu is dat bij een kleine site niet zo?n probleem maar als veel mensen de boomstructuur opvragen dan merk je al snel dat dit niet handig is.

Het modified preorder tree traversel model

Er is echter een oplossing voor dit probleem, het vergt een andere manier van denken en is minder overzichtelijk maar uiteindelijk zal blijken dat dit een stuk sneller werkt. Dit model wordt modified preorder tree traversal genoemd. Om het model duidelijk uit te leggen zal ik beginnen met de boomstructuur een kwartslag te draaien en er wat getallen en pijltjes bij te zetten:

Bij dit type wordt er niet aangegeven wat de parent van de node is, maar in plaats daarvan wordt er aan elke node een linker en rechterwaarde toegekend. De manier waarop deze waardes worden gegeven zie je aan de richting van de pijltjes. Het komt er op neer dat er bovenaan links wordt begonnen en dat telkens de volgende linkerkant van een node de volgende waarde krijgt. Dit gaat door tot het diepste niveau wordt bereikt, dan wordt de rechterwaarde genomen waarna de rest van de boom wordt afgewerkt (childs gaan voor siblings, siblings gaan voor parents wat betreft nummering).

ID	Name	Links	Rechts
1	Fruit	1	28
2	Groen	2	13
3	Klein	3	8
4	Druif	4	5
5	Kiwi	6	7
6	Groot	9	12
7	Peer	10	11
8	Rood	14	19
9	Appel	15	16
10	Aardbei	17	18
11	Geel	20	27
12	Banaan	21	22
13	Citroen	23	24
14	Perzik	25	26

Let op: Als je de kolomnamen van tabellen in het engels doet, vergeet dan niet dat binnen SQL de woorden LEFT en RIGHT gereserveerd zijn, deze kunnen dus niet als kolomnaam op worden gegeven.

Op het eerste gezicht lijkt dit een rare manier om een boomstructuur op te slaan, maar wanneer je de relaties tussen getallen en positie goed ziet dan merk je dat dit heel handig is.

Gegevens ophalen

Weet je nog al die self-joins (of meerdere queries)? Met een tabel die op deze manier ingedeeld kan dat allemaal stukken makkelijker. Laten we nog eens proberen om alles wat boven Kiwi staat op te halen:

SELECT
*
FROM
tabel_naam
WHERE
Links < 6 && Rechts > 7
ORDER BY links ASC;

Met één query kunnen we alles ophalen wat boven Kiwi staat!

Maar er kan veel meer, wil je bijvoorbeeld de hele boom structuur onder een bepaalde node ophalen (alle childs), dan kan dat op deze manier:

SELECT
*
FROM
tabel_naam
WHERE
Links BETWEEN 2 AND 13
ORDER BY Links ASC;

We hebben nu alle groene vruchten opgehaald.

Een ander simpel rekenkundige trucje om het aantal “descendants” van de boom (of een deel ervan) te weten te komen: (Rechts ? Links ? 1) / 2

Nodes toevoegen en verwijderen

Het is nu duidelijk hoe je informatie ophaalt uit de database, maar wat als je een node wilt toevoegen of verwijderen? Om het probleem op te lossen zou je de parent-node-id in de rij in de database kunnen laten staan. Door de parent-node te laten staan zou je het adjency list model kunnen gebruiken om waardes toe te voegen en te verwijderen. In sommige gevallen zou het handig kunnen zijn om beide manieren door elkaar heen te gebruiken, maar over het algemeen kunnen we stellen dat het handigste is om op één manier de database in te richten, dit voorkomt ook verwarring.

Hoe kunnen we dan een node toevoegen? Eigenlijk is dit vrij simpel, als voorbeeld willen we een node toevoegen tussen groen en rood. Het is dus niet een van het diepste niveau, al zou dit ook kunnen. Als we na groen iets in zouden voegen betekent dit het volgende:

• Tot en met de rechter waarde van groen blijft alles gelijk
• Na groen worden twee getallen ingenomen de linker en rechter-waarde
• Om ruimte te maken voor de nieuwe node moeten alle rechter en linker waardes rechts van groen met twee verhoogd worden

De rechter waarde van groen is 13, alles wat groter is dan 13 zal met 2 verhoogd worden om plaats te maken:

UPDATE
tabel_naam
SET
Links = Links + 2
WHERE
Links > 13;
UPDATE
tabel_naam
SET
Rechts = Rechts + 2
WHERE
Rechts > 13;

Nu is er ruimte om een node toe te voegen. Deze zal de naam paars krijgen, de linkerwaarde is 13 + 1 = 14, de rechterwaarde is 13 +2 = 15.

INSERT INTO
tabel_naam
(Name, Links, Rechts)
VALUES
(?paars?, 14, 15);

Met hetzelfde idee kunnen nodes ook verwijderd worden. Uiteraard zal er wel eerst gecontroleerd moeten worden of de betreffende node geen childs heeft. Voor het gemak gaan we er nu even vanuit dat alleen nodes zonder diepere niveaus verwijderd mogen worden, en dat we vóór de volgende query uitgevoerd wordt al weten dat de node verwijderd kan worden.

We willen in het volgende voorbeeld kiwi verwijderen. We weten de linker en rechterwaardes van kiwi, zodoende kunnen we deze verwijderen en wat er na komt twee plekjes terug schuiven.

We beginnen met het verwijderen van de kiwi:

DELETE FROM
table_naam
WHERE
Links = 6;

Kiwi is nu verwijderd, voor de veiligheid hadden ook in de where-clausule kunnen toevoegen dat Rechts een waarde moest hebben van Links + 1. Dit zou voorkomende dat nodes worden verwijderd die zelf childs hebben.

Alles na kiwi moet nu twee getallen terug worden geschoven:

UPDATE
tabel_naam
SET
Links = Links ? 2
WHERE
Links > 7; // neem laatste waarde van kiwi

Update
tabel_naam
SET
Rechts = Rechts ? 2
WHERE
Rechts > 7;

Conclusie

Er zijn meerdere manieren om een boom-structuur in een database te zetten, elke manier heeft zijn voor en nadelen. Het modified preorder tree traversel model is in eerste instantie vrij moeilijk te bevatten, maar wanneer je de techniek eenmaal begrijpt zal je zien dat dit een heel handige manier is om informatie in de vorm van een boom-structuur op te slaan. Deze manier gebruikt meer queries bij het toevoegen of verwijderen van een node, maar het ophalen van informatie daarentegen gaat vele malen sneller. Het ophalen zal veel vaker gebeuren dan het wijzigen van de structuur, zodoende kunnen we stellen dat dit een heel handige en snelle manier is voor het opslaan van structuren in de database.

Voor de SEO-freaks onder onder ons: het bovenstaande artikel geeft de theorie van een bepaalde manier van het opslaan van boom-structuren. Indirect gezien heeft dit weinig met SEO te maken, echter wanneer je van plan bent om een module te schrijven voor een website zal je zien dat in veel gevallen je met boom-structuren zal werken. Op deze manier kan je de site sneller maken en een hoop extra gebruiksvriendelijkheid geven (denk aan breadcrumbs binnen een forum, foto-album, etc.).

• Tweet