[PHP/SQL] Sorteerbare boomstructuur opslaan (nested set?)

[Aphax]

Ik moet voor een webapplicatie een folderstructuur weergeven, waar bestanden in geplaatst zijn. Deze folderstructuur moet worden opgeslagen in een (My)SQL database, en moet tevens gesorteerd kunnen worden op verschillende velden zoals naam, aanmaakdatum of op de grootte van de bestanden in de folderstructuur. Ik wil het ongeveer zoals in dit plaatje (screenshot van Nautilus, Gnome's filebrowser) presenteren aan de gebruiker:



Nou zit ik een beetje te tobben over welke methode ik het beste kan gebruiken om de boomstructuur in MySQL op te slaan. Aangezien het uitlezen van de tree efficient moet gebeuren dacht ik in eerste instantie aan de nested set methode (overigens is het uitlezen van subtrees niet nodig), maar dat maakt het sorteren op de verschillende velden aan de database kant lastig (onmogelijk?). Misschien dat ik dit in PHP kan doen, aangezien de tree daar toch opgebouwd moet worden. Ik vraag me echter af of er nog alternatieven zijn.

Iets anders waar ik niet zeker van ben is of ik de bestanden zelf en de folders het beste in aparte tabellen, of in de zelfde tabel kan op slaan. Het lijkt me aan de ene kant efficienter voor updates in de folderstructuur om ze apart te houden, maar ik weet niet of/hoe ik dan in één query de folders en bestanden kan ophalen.

Kan iemand mij adviseren of een duwtje in de juiste richting geven?

PS: Een andere optie die ik had overwogen, maar toch niet voor gekozen heb, is om simpelweg direct het lokale bestandssysteem te gebruiken. Maar vanwege mogelijke verschillen in character sets, toegestane tekens en bestandsnaam-lengtes onder verschillende besturingssystemen/filesystems heb ik hier toch niet voor gekozen. Op het moment worden de bestanden zelf wel opgeslagen direct in het bestandssysteem, maar in één enkele directory en als bestandsnaam wordt simpelweg de primary key van een bijbehorend record in de database (waar info zoals datum, de persoon die het bestand geplaatst heeft etc. in staan.)

[BtM909]

Er zijn een aantal mogelijkheden. Als je de boomstructuur in je database opslaat, dan kan je toch simpelweg een redelijk platte tabel bijhouden met een kolom voor file type en een kolom voor parentID?

[Soultaker]

edit:
Ok, het voorstel werkt niet. Back to the drawing board!

[ Voor 159% gewijzigd door Soultaker op 29-01-2007 18:10 ]

[gvanh]

Zelf heb ik vrij veel succes/profijt gehad van dit artikel: http://www.sitepoint.com/...rarchical-data-database/2.
Wellicht is dat het lezen eens waard.

Dat heet de "Modified Preorder Tree Traversal".

Overigens gebruik ik zelf een "dubbel-op" systeem. Naast de in het artikel beschreven methode, sla ik voor iedere node ook nog de parentID op. Dat geeft me twee mogelijkheden voor het ophalen van een (onderdeel van) een boom.

Voordeel van bovenstaande methode voor jou is - volgens mij - dat je op de gewenste manier kan sorteren, namelijk eerst op "diepte" van de node, en daarna op alle items op hetzelfde niveau.

[T-MOB]

Ik ben zelf iets dergelijks aan het maken en heb daarin de volgende keuzes gemaakt.
* In de database worden directories opgeslagen volgen het adjacent list principe. Dat is een platte tabel met nodeid -> parentid relaties.
* Bestanden staan in een aparte tabel
* De directorytree wordt altijd in zijn geheel ingeladen. Ofwel uit de database , ofwel uit een cache bestandje.

Bij het ophalen van de tree wordt een multidimensionaal array opgebouwd die in de basis de volgende structuur heeft. Elke directory vormt een key in het array, de waarde die bij de key hoort is een array met alles subdirs. Als speciale subdir wordt '..' aangemaakt met een referentie naar de parentnode in het array:

PHP:

$tree['foo']['..'] => &$tree
            ['sub']['..'] => &$tree['foo']
            ['sb2']['..'] => &$tree['foo']
            
     ['bar']['..'] => &$tree
     
     ['qux']['..'] => &$tree
            ['sub']['..'] => &$tree['qux']

Hiermee kun je op zich nog niet zoveel. Om eea nuttig te maken heb hang ik aan elke directory meta-informatie. Omdat ik slashes gebruik om directories te scheiden, leek de slash mij een veilig karakter om dat mee te doen. Aan elke node hangen dus ook de volgende array members:

PHP:

$tree['foo']['/id'] => {int}
            ['/name'] => 'foo'

Tot slot bleek ik nogal wat lookups te doen aan de hand van het id van een directory. Om dat efficient te laten verlopen hou ikin de root node een indexje bij met referenties aan de hand van id. Bij het opbouwen van de tree wordt deze gevuld.

PHP:

$tree['/map'][1] => &$tree
             [2] => &$tree['foo']
             [3] => &$tree['bar']

Het uitlezen van deze tree is ontzettend snel, omdat je nergens meer recursie nodig hebt. Het opbouwen vanuit de database is acceptabel (~3s bij 15.000 directories tot 12 levels diep op een PII 233), vanuit cache goed (0.6s op dezelfde P2II).

Voor het opvragen van een dirlisting maak ik een object aan dat een referentie naar de betreffende node in de directory tree meekrijgt. Daarmee heb je het id van de directory om alle files op te halen in elke gewenste sortering. Bovendien heb je weet van alle subdirectories.
Zoals ik al heb gemeld is een en ander nog in ontwikkeling. Als er animo is wil ik wel wat code on-line gooien. Eea heeft dan de vorm van een filesytem klasse waarin ls(), mkdir(), rmdir(), fileExists(), isDir(), du() en - voor directories - mv() zijn geimplementeerd. Het bestandsgedeelte heeft nog weinig invulling.

[xces]

Dit is erg intressant T-Mob. Ik ben in ieder geval wel geintresseerd in hoe je dit code gewijs hebt opgepakt.

Ik heb zelf een module geschreven waarmee klanten bestanden kunnen uploaden. Dit schrijf ik nu nog enkel weg in een filesysteem. Bij het ophalen van een directory lees ik de complete structuur van die directory uit, inclusief filemtime etc. Het geheel is ook OOP gebaseerd. Ik moet er wel bij vertellen dat dit, ook al werkte het perfect, wat nadelen heeft. Je moet continue op je disk hameren, terwijl het in principe op 2 verschillende manieren opgelost zou kunnen worden;
a) oplossing zoals hierboven door T-mob of door jou omschreven is; via SQL
b) sla de structuur op in een serialized text file, en "rebuild" deze na iedere wijziging. Meer risico natuurlijk, maar het scheelt je het bouwen.

Misschien zou een combinatie van beide ook wel werken?

[Aphax]

Bedankt voor de suggesties! Ik heb nog even zitten nadenken, en ik denk dat ik inderdaad toch het beste de goede oude 'parentId' methode kan gebruiken. Aangezien ik geen subtrees hoef te selecteren, kan ik gewoon alle folders en bestanden in één query zonder recursie fetchen, en in PHP alles structureren en sorteren (hoe ik dat laatste het beste kan doen weet ik overigens nog niet, maargoed, dat is een ander probleem).

EDIT: Wat ik ook nog even wou aanhalen is dit: http://epsilondelta.net/2...ing-a-tree-in-a-database/

Weet iemand van een artikel dat uitlegt hoe dit te implementeren valt? Op het eerste gezicht ziet het er interessant uit, maar echt snappen doe ik het niet ik kan er weinig informatie over vinden.

[ Voor 27% gewijzigd door Aphax op 30-01-2007 08:50 ]

[Brakkie]

Ik gebruik een PHP ORM ( php doctrine) en die heeft op dit moment een implementatie van Nested set voor het opslaan van tree structures in de database. Misschien dat je daar wat ideeen vandaan kan halen. http://doctrine.pengus.ne...documentation.php?index=6

SVN repository voor download: http://doctrine.pengus.net/svn

[ Voor 3% gewijzigd door Brakkie op 30-01-2007 10:15 ]

[xces]

na het bestuderen van dit sitepoint artikel zat ik me meteen af te vragen hoe je dit nu zou moeten doen als je een node (met childnodes en childnodes etc. etc.) van de tree zou "moven", maar volgens mij is dit juist rete simpel. Je weet immers hoeveel nodes erin zitten, en kan dus makkelijk de nieuwe tree bouwen door middel van een paar SQL statements toch?

[gvanh]

na het bestuderen van dit sitepoint artikel zat ik me meteen af te vragen hoe je dit nu zou moeten doen als je een node (met childnodes en childnodes etc. etc.) van de tree zou "moven", maar volgens mij is dit juist rete simpel. Je weet immers hoeveel nodes erin zitten, en kan dus makkelijk de nieuwe tree bouwen door middel van een paar SQL statements toch?

Ik neem aan dat je het artikel bedoelde dat ik had gepost (is het enige sitepoint artikel dat ik tussen de reacties zag).

In principe is het vrij eenvoudig om de hele boom opnieuw op te bouwen op het moment dat er iets verandert - door middel van een recursieve functie. Maaarrrr ... ik heb gemerkt dat dat al snel geen alternatief meer is op het moment dat je database-tabel een beetje serieuze omvang krijgt. Ik heb wat dat betreft al wel redelijk wat werk zitten in een handige manier om nodes te kunnen verwijderen en toevoegen.

Zelfs met een efficientere functie om nodes toe te voegen of te verwijderen loopt de executie-tijd vrij snel op. Op zich met het verwijderen/verplaatsen van één node nog niet zo'n probleem ... maar wanneer je een aantal nodes tegelijker verwijderd is de vertraging wel heel duidelijk merkbaar. Dan is het dus handiger om de boom-structuur acties die nodig zijn voor alle nodes samen te pakken. Daar heb ik de ideale manier nog niet echt voor gevonden.

Overigens is het idee van deze boomstructuur dat de bewerk-acties vrij database-intensief zijn, maar dat de lees-acties juist weer erg licht zijn (bijvoorbeeld doordat je een hele tak uit de boom met één enkele query kan ophalen. Wanneer je dus binnen een systeem veel meer lees- dan schrijf-acties hebt, is het een mooie systematiek. Wanneer je meer schrijf- dan leesacties hebt, of ze redelijk in balans zijn ... dan is het misschien niet de meest ideale oplossing.

[ Voor 16% gewijzigd door gvanh op 30-01-2007 14:37 . Reden: aanvulling en typo. ]

[xces]

Dat vraag ik me af, als ik het sitepoint artikel lees, zijn er 2 query's nodig om een node te verwijderen.
De eerste is de query die ervoor zorgt dat de node verwijderd zal worden, de tweede query zal de onderliggende nodes updaten met de nieuwe lft en rght values. Je hoeft hiervoor dus geen nieuwe boom te bouwen.

Ook als je een node moved (beetje lastig uitleggen zonder plaatje) zou het niet zo moeilijk moeten zijn.

Ik zie dat dan zo voor me, maar het kan zijn dat ik het niet snap:
1) Je weet welke node je verplaatst, je weet hier dus de lft en rght values van. Ik ga even van een node uit die als lft "4" heeft, en als rght "9".
2) Je haalt de node even uit de structuur, eventueel door het in een tijdelijke tabel te "selecten". Om het straks in 1 keer op de juiste plaats weer in te voegen (en om het rekenen makkelijker te maken) moet je de lft value wel naar 1 brengen, in dit geval dus -3. Je zult dan voor de lft "1" over houden, en voor de rght "6".
3) Je verwijderd de node uit de tree tabel, zoals je normaal doet, met 2 query's (zie boven).

Nu ga je de node invoeren op de nieuwe positie, maar dit doe je eigenlijk andersom dan bij een delete. Je weet waar de node moet komen, je weet de lft en rght values (die heb je immers straks opnieuw berekend). Je weet dus ook hoeveel de achterliggende nodes geupdate moeten worden.

Je gaat als volgt te werk:
1) Maak ruimte: Update de nodes met een lft en rght hoger dan de node van waar je hem in wilt voegen. Je hebt nu ruimte om de nieuwe nodes in te voeren
2) Voer de nieuwe nodes in
3) Leeg de tijdelijke tabel.

Je boomstructuur is weer klaar voor gebruik. Volgens mij moet dit toch kloppen...