[PHP/MySQL/Alg] Trees vergelijken

[Matthis]

Ik ben bezig een intranet applicatie (PHP - MySQL) aan het ontwerpen waarin bijna alles draait rond het hiërarchisch opslaan van data. Trees dus.

De tree zal vermoedelijk enkele tienduizenden nodes bevatten en moet frequent worden upgedate (nodes toevoegen, verschuiven, ...). Het is echter niet zo dat de boom 100x per minuut zal upgedate worden....


Wat de backend betreft zijn er blijkbaar een tweetal veel voorkomende manieren om de data op te slaan (zie o.m. http://www.sitepoint.com/...archical-data-database/):
- id, parent_id, order
- modified preorder tree traversal algorithm

De frontend zou ik met JS en eventueel AJAX in elkaar zetten, zodat het geheel dynamisch geladen kan worden. Nu vraag ik me echter af welke methode het meest aangewezen is in mijn situatie. Als je een tree bewerkt, zal die op een bepaald moment moeten worden opgeslagen. Dus moet er vergeleken worden met de bestaande tree, zodat de wijzigingen kunnen bewaard worden.

Het lijkt me eenvoudiger om 2 adjacent trees met elkaar te vergelijken dan 2 MPT's?

Iemand ervaringen met deze problematiek?

[Kalentum]

Ik zou gaan voor dat Sitepoint-artikel. Je kunt dan real time wijzigingen opslaan aangezien het verplaatsen van nodes razendsnel is. Zeker met duizenden of meer nodes is dat eigenlijk de enige optie.

Wat betreft de frontend: ik zou gaan voor direct updaten ipv de gebruiker eerst een tijdje wijzigen te laten aanmaken en dan pas opslaan. Want wat doe je als een andere gebruiker ondertussen ook de tree zit te wijzigen? Waar laat je de tijdelijke kopie?

[chris]

Welke operaties worden het meest op je tree uitgevoerd: lezen of bewerken? Als je veel vaker leest en het erg belangrijk is dat je heel snel alle nodes uit moet lezen, zou ik voor de pre-order encoding gaan. Als het niet persé nodig is zou ik het niet doen, het maakt je operaties een stuk ingewikkelder. Ook als je er niet voor gaat kan je namelijk nog steeds een goede performance krijgen, door bijvoorbeeld lazy data te laden. Pas als je een node openklapt laad je al z'n directe kinderen. Zo laad je alleen wat je echt nodig hebt.

Wat je op de front-end doet, kan heel goed los staan van je keuze van opslaan. Op de front-end kan je goed een geschiedenis bijhoden van je acties, en die op een gegeven moment "committen" naar de server. Je zit dan wel, zoals rutgerw zegt, met mogelijke merge-problemen op de server, maar die heb je ook als je direct wijzigingen doorvoert (alleen lagere frequentie). Het ligt er een beetje aan hoe zwaar je je server wilt belasten, en of je vaak gebruikers hebt die tegelijkertijd hetzelfde stuk data zitten te bewerken.