Binaire boom in een database. Beste aanpak?

[Verwijderd]

Hoi Tweakers,

Ik heb met een collegaatje wat zitten brainstormen over de implementatie van een binaire boom in een relationele database. Daar zijn voor zover wij weten 2 methodes voor: met parent-child relaties en met left en right values. Op sitepoint staat een mooi artikel met achetrgrondinfo hierover.

De schrijver van het artikel merkt terecht op dat een parent-child relatie in je database werkt, maar dat je tegen het 'probleem' van recursie aanloopt. Als je boomstructuur diep wordt en je wilt alle nodes pakken onder node X, dan moet je, net als bij een filesysteem, alle nodes direct onder X pakken, dan per node kijken of er subnodes zijn, dan weer per subnode kijken of er subsubnodes zijn, etc. Recursie dus. En dat is traag, want je moet telkens een nieuwe query op de DB afvuren om sub(subsubsub)nodes te pakken.

Het alternatief is een oplossing met right en left values voor elk node. Met deze aanpak kun je van node X de left en right value pakken en dan in 1 query alle nodes pakken die een left-waarde groter dan die van X en een right-waarde kleiner dan die van X hebben. Lekker makkelijk en het performt als een beest vergeleken met de recursieve aanpak, want je hebt maar 1 query nodig.

ECHTER! Wat gebeurt er als je een boom hebt met 2 miljoen nodes, zoals in ons systeem..... Op het moment dat je een node insert of delete, dan moeten alle left en right waardes van nodes te rechterzijde van de toegevoegde (of verwijderde) node ge-update worden en da's niet zo leuk als je dat voor 2 miljoen nodes moet doen DENK IK.

Ik denk daarom dat ik ondanks het recursieprobleem toch tot een parent-child aanpak 'veroordeeld' ben. De boom van ons systeem zal waarschijnlijk niet heel diep worden (4 levels max) dus ik denk dat het het beste is om voor die parent-child optie te gaan.

A penny for your thoughts.

[orf]

Alles hangt van de verhoudingen af. Wij hebben voor ons CMS gekozen voor modified pre order traversal omdat de tree erg vaak uitgelezen moet worden (voor views: de structuur, menu's e.d). Het bewerken van de tree gebeurt niet zo vaak en daarmee is een update van de values ook niet zwaar. Nu hebben wij niet zo veel nodes in een tree als jij hebt. Maar een enkele update query op nodes waar x > y is bij ons erg snel. We doen zulke updates met stored procedures zodat we zeker weten dat een update volledig goed gaat.

In een parent child model mis je overigens nog de volgorde binnen de parent. Als je daarvoor een extra kolom voor moet bijhouden is het nadeel alweer een stukje groter.

[RobIII]

Verwijderd schreef op woensdag 30 september 2009 @ 21:24:
en da's niet zo leuk als je dat voor 2 miljoen nodes moet doen DENK IK.

Waarom benchmark je het niet
Meten = weten

[ Voor 78% gewijzigd door RobIII op 30-09-2009 21:34 ]

[Verwijderd]

Met een parent/child oplossing zal ik inderdaad een extra kolom moeten bijhouden voor de volgorde van nodes, maar ik denk niet dat dit performance-wise veel uitmaakt bij een insert/delete. In ons systeem zullen er redelijk vaak inserts (tientallen of misschien enkele honderden per dag) plaatsvinden, hoewel de verhouding met selects nog veeeerrr in het voordeel van selects ligt. Probleem alleen is dat ik niet zoveel zicht heb op de ontwikkelingen in de toekomst.. Het aantal inserts zou weleens toe kunnen nemen.

@Rob: je hebt ook gelijk. De boel helemaal aftesten is het best, maar je weet nooit, misschien loop je hier nog iemand tegen het lijf met exact hetzelfde issue en kan je direct een beslissing maken

Bedankt!

[orf]

Op sitepoint staat wel een voorbeeldje van hoe je een conversie doet van een parent child naar modified preorder. Wellicht kun je een kopie van een database maken, de conversie doen en eens kijken hoe snel een update / delete gaat.

Voor MySQL gebruiken wij hiervoor de volgende procedure:

SQL:

CREATE PROCEDURE sm_delete_node (IN _nodeId INT)
BEGIN
    DECLARE _targetRgt INT;
    DECLARE _targetLft INT;
    DECLARE _targetWidth INT;
    
    START TRANSACTION;

    SELECT lft, rgt, rgt - lft + 1 INTO _targetLft, _targetRgt, _targetWidth
    FROM sm_nodes
    WHERE id = _nodeId;

    DELETE FROM sm_nodes WHERE lft BETWEEN _targetLft AND _targetRgt;

    UPDATE sm_nodes SET rgt = rgt - _targetWidth WHERE rgt > _targetRgt;
    UPDATE sm_nodes SET lft = lft - _targetWidth WHERE lft > _targetRgt;

    COMMIT;
END//

Aanroep:

SQL:

CALL sm_delete_node [NODE ID]

Als je wilt kan ik ook move en insert procedures posten. Maar wellicht moet je eerst even testen hoe snel een delete is.

[ACM]

Zoek het boek Trees and Hierarchies in SQL for Smarties op en bekijk een serie mogelijkheden. E.e.a. vond ik vrij aardig uitgewerkt.

De variant van orf heeft als grootste nadeel dat je de helft van je tabel moet aanpassen voor elke insert, tenzij je een variant neemt met ruimte voor inserts. Maar dan moet je weer ingewikkelder checks daar bij hebben.

Wat betreft de queries, de SQL03 definitie heeft een uitbreiding voor recursieve queries, dat kan wellicht een uitkomst zijn (CONNECT BY enzo). Ik weet dat iig PostgreSQL 8.4 er ondersteuning voor heeft.

Als je bang bent dat elke representatie in SQL nadelen heeft, kijk dan of je een object- of graafdatabase kan gebruiken ervoor. Dat heeft zelf natuurlijk ook weer nadelen, maar dat heeft elke aanpak.

[Soultaker]

Bij een binaire boom kun je knopen eenvoudig identificeren aan de hand van het pad vanaf de root node. Bijvoorbeeld "010" is het de node links van de node rechts van de node links van de root node. Een subtree query is dan van de vorm WHERE id LIKE "prefix%" wat efficiënt met een standaard index kan worden opgelost. Als je van te voren een beperkte maximumdiepte kunt vastleggen, kun je die identifier opslaan in een VARCHAR veld; anders in een TEXT veld wat de overhead per node natuurlijk verhoogt.

Dit systeem valt ook te gebruiken voor bomen met ene variabel aantal nodes. Je krijgt dan een soort Dewey schema.

Verwijderd schreef op woensdag 30 september 2009 @ 21:24:
Wat gebeurt er als je een boom hebt met 2 miljoen nodes, zoals in ons systeem..... [..] De boom van ons systeem zal waarschijnlijk niet heel diep worden (4 levels max) dus ik denk dat het het beste is om voor die parent-child optie te gaan.

Hier spreek je jezelf behoorlijk tegen. Een binaire boom met hoogte 4 bevat maximaal 31 knopen, geen twee miljoen. (En voor 31 rijen maakt 't natuurlijk niets uit welke representatie je kiest; het is toch wel snel.)

[cariolive23]

Zie voor een CTE in PostgreSQL om een boomstructuur op te vragen, dit voorbeeld: http://wiki.phpfreakz.nl/CommonTableExpression

[MSalters]

Soultaker zit vermoed ik in de goede richting: heb je echt een binaire boom nodig?

En bij het deleten van nodes hoef je geen left/right values aan te passen; het idee blijft correct als de boom sparse is.

[HuHu]

MSalters schreef op dinsdag 20 oktober 2009 @ 13:16:
Soultaker zit vermoed ik in de goede richting: heb je echt een binaire boom nodig?

En bij het deleten van nodes hoef je geen left/right values aan te passen; het idee blijft correct als de boom sparse is.

2 miljoen nodes en 4 levels diep => geen binaire boom, dus blijkbaar haalt rubenski wat termen door elkaar.

[Verwijderd]

Andere vraag; moet je in een keer zoveel childnodes gaan ophalen? Als je een treeview control aan het laden bent kun je ook op uitklappen van een node de childnodes gaan ophalen en hoef je dit niet in één keer te gaan doen.