Cookies op Tweakers

Tweakers maakt gebruik van cookies, onder andere om de website te analyseren, het gebruiksgemak te vergroten en advertenties te tonen. Door gebruik te maken van deze website, of door op 'Ga verder' te klikken, geef je toestemming voor het gebruik van cookies. Wil je meer informatie over cookies en hoe ze worden gebruikt, bekijk dan ons cookiebeleid.

Meer informatie
Toon posts:

Binaire boom in een database. Beste aanpak?

Pagina: 1
Acties:

Onderwerpen


  • rubenski
  • Registratie: december 2001
  • Laatst online: 20-10-2017

rubenski

kletskoppen for president

Topicstarter
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.

People that want a pet go to a pet shop
People that want a pet shop go to a pet shop shop
People that want a pet shop shop, well, they're just being silly


  • orf
  • Registratie: augustus 2005
  • Nu online
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
  • Registratie: december 2001
  • Laatst online: 21:20

RobIII

Admin Devschuur®

^ Romeinse 3 ja!

quote:
rubenski 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

RobIII wijzigde deze reactie 30-09-2009 21:34 (78%)

There are only two hard problems in distributed systems: 2. Exactly-once delivery 1. Guaranteed order of messages 2. Exactly-once delivery.

Roses are red Violets are blue, Unexpected ‘{‘ on line 32.

Over mij


  • rubenski
  • Registratie: december 2001
  • Laatst online: 20-10-2017

rubenski

kletskoppen for president

Topicstarter
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!

People that want a pet go to a pet shop
People that want a pet shop go to a pet shop shop
People that want a pet shop shop, well, they're just being silly


  • orf
  • Registratie: augustus 2005
  • Nu online
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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:
1
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
  • Registratie: januari 2000
  • Niet online

ACM

Software Architect

Werkt hier

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.

Saai uitzicht in je tuin? Hang er een foto voor!


  • Soultaker
  • Registratie: september 2000
  • Laatst online: 12-02 14:23
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.
quote:
rubenski 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.)

PGP public key


  • cariolive23
  • Registratie: januari 2007
  • Laatst online: 23-02 15:29
Zie voor een CTE in PostgreSQL om een boomstructuur op te vragen, dit voorbeeld: http://wiki.phpfreakz.nl/CommonTableExpression

  • MSalters
  • Registratie: juni 2001
  • Laatst online: 17:06
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.

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


  • HuHu
  • Registratie: maart 2005
  • Niet online
quote:
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.

  • 14124
  • Registratie: oktober 2000
  • Laatst online: 15-10-2016
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.
Pagina: 1


Apple iPhone 11 Microsoft Xbox Series X LG OLED C9 Google Pixel 4 CES 2020 Samsung Galaxy S20 4G Sony PlayStation 5 Nintendo Switch Lite

'14 '15 '16 '17 2018

Tweakers vormt samen met Hardware Info, AutoTrack, Gaspedaal.nl, Nationale Vacaturebank, Intermediair en Independer DPG Online Services B.V.
Alle rechten voorbehouden © 1998 - 2020 Hosting door True