[PHP] / [MySQL] 3-level menustructuur / sitemap

[koekiemonster]

Ik ben momenteel bezig met een CMS en daarin is het mogelijk om een 3-level menu aan te maken, wijzigen, sorteren,verwijderen etc.
Dit gaat prima, maar nu wil ik de voorkant maken......

De basis staat al en dat is het volgende:

<?php
TABEL menu
+----+-----------+--------------+--------------------------+ -----------------+----------------------------------------------
| id | parentid | sortorder | titel | newwindow | url
+----+-----------+--------------+--------------------------+ -----------------+---------------------------------------------
| 1 | 0 | 0 | Algemeen | 0 | http://cms.nl/test.php?id=21
| 2 | 0 | 0 | Contact | 0 | http://cms.nl/test.php?id=13
| 3 | 1 | 1 | Wie zijn wij? | 0 | http://cms.nl/test.php?id=1
| 4 | 1 | 2 | Wat doen we? | 1 | http://cms.nl/test.php?id=210
| 5 | 4 | 0 | Projects | 0 | http://cms.nl/test.php?id=5
| 6 | 1 | 1 | Brochure | 0 | http://cms.nl/test.php?id=22
+----+-----------+--------------+--------------------------+ ------------------+---------------------------------------------
?>

Kortom, een mooie tabel, maar nu wil ik deze zo simpel mogelijk presenteren aan de gebruikers.
Als parentid 0 is, dan hebben we te maken met een hoofdmenu.
Hoe kan ik met zo min mogelijk queries dit op een volgende manier presenteren?
Ik heb het idee dat het met 1 query kan, maar ik heb nu 3 query's (1 hoofd, 1 sub, 1 subsub) wat ik een beetje te veel van het goede vind.
Stiekem was ik namelijk wel trots op het menu in 1 tabel en de werking in het cms gaat prima, maar daar toon ik dus eerst een rij met hoofdmenuitems en als ik er 1 aanklik worden de subs getoond. Nu wil ik alles tonen en niet per klik een sub of hoofdgegevens.

code:

<ul>
<li><a href="http://cms.nl/test.php?id=21" >Algemeen</a>
<ul>
   <li><a href="http://cms.nl/test.php?id=1" >Wie zijn wij?</a></li>
   <li><a href="http://cms.nl/test.php?id=210" rel="external">Wat doen we?</a>
   <ul>
      <li><a href="http://cms.nl/test.php?id=5">Projects</a></li>
   </ul>
   </li>
   <li><a href="http://cms.nl/test.php?id=22">Brochure</a></li>
</ul>
</li>
<li><a href="http://cms.nl/test.php?id=13">Contact</a></li>
</ul>

[Janoz]

Als het antal niveaus gelimiteerd is op 3 kun je de tabel natuurlijk gewoon 3x joinen. Je hebt dan alles keurig in 1 query binnen. Als je vervolgens ook nog goed sorteerd kun je het binnen 1 lusje afdrukken in je html.

[BoAC]

1 functie maken die je recursief gebruikt (parentid meegeven)

[ Voor 6% gewijzigd door BoAC op 10-11-2006 15:15 ]

[rewind.]

http://www.sitepoint.com/article/hierarchical-data-database

[Upsal]

Hier was kort geleden nog een topic over:
[PHP] Webshop menu probleem.

[vitrix]

Ik heb ook zoiets gemaakt met een unlimited lvl.
In het main menu had ik een functie submenu die de parentid mee kreeg.
Aan de hand daarvan zocht ik de links.
Als die een link vondt had ik weer de zelfde functie geinclude met die link id.
Zo kon die blijven door gaan.

[Verwijderd]

Ik zou niets recursiefs doen, en niets joinen.
Simpelweg je tabel drie niveaus geven dus:

surrogaat_id | root_id | sub_id | sub_sub_id | overige_meuk

met relaties:
root_id 1-n sub_id
sub_id 1-n sub_sub_id

geen joins, geen gedoe.
Opbouwen als tree in je script moet je toch

[Genoil]

Stoney187 schreef op vrijdag 10 november 2006 @ 15:18:
http://www.sitepoint.com/article/hierarchical-data-database

Voordat mensen over deze link heenlezen, dit artikel is denk ik wel zo'n beetje het meest gerefereerde artikel als het over boomstructuren in PHP/MySQL gaat. Lees het!

Wat je nu hebt is het Adjacency model, maar aangezien je graag de boom uitleest in 1 query zou ik het Nested-set model toepassen. Het wordt dan wel iets lastiger om bewerkingen in de structuur door te voeren.

[edit]
Ja wat hierboven gezegd wordt is ook wel een aardige manier, vooropgesteld dat je met maximaal 3 niveau's te maken hebt. Wil je meer, dan wordt het toch wel een beetje een puinhoopje.

[ Voor 14% gewijzigd door Genoil op 10-11-2006 15:31 ]

[koekiemonster]

Janoz schreef op vrijdag 10 november 2006 @ 15:14:
Als het antaal niveaus gelimiteerd is op 3 kun je de tabel natuurlijk gewoon 3x joinen. Je hebt dan alles keurig in 1 query binnen. Als je vervolgens ook nog goed sorteerd kun je het binnen 1 lusje afdrukken in je html.

Juist lijkt me het proberen waard. Ik blijf ook binnen een drietal niveaus, hoewel hetgeen ik nu heb ongelimiteerd is.

http://www.sitepoint.com/article/hierarchical-data-database

Al gezien, maar niet geheel de oplossing die ik zoek (alhoewel erg mooi). gezien de structuur er nu helemaal staat en klanten al aan het opvoeren zijn.

[Verwijderd]

Verwijderd schreef op vrijdag 10 november 2006 @ 15:27:
Ik zou niets recursiefs doen, en niets joinen.
Simpelweg je tabel drie niveaus geven dus:

surrogaat_id | root_id | sub_id | sub_sub_id | overige_meuk

met relaties:
root_id 1-n sub_id
sub_id 1-n sub_sub_id

geen joins, geen gedoe.
Opbouwen als tree in je script moet je toch

Wat is nu het voordeel van de structuur die je hierboven beschrijft ten opzichte van de reeds eerder aangegeven structuur door Stonley

Stoney187 schreef op vrijdag 10 november 2006 @ 15:18:
http://www.sitepoint.com/article/hierarchical-data-database

koekiemonster schreef op vrijdag 10 november 2006 @ 15:37:
Al gezien, maar niet geheel de oplossing die ik zoek (alhoewel erg mooi). gezien de structuur er nu helemaal staat en klanten al aan het opvoeren zijn.

Had je misschien eerder over je probleem na moeten denken

[ Voor 18% gewijzigd door Verwijderd op 10-11-2006 15:40 ]

[Verwijderd]

Verwijderd schreef op vrijdag 10 november 2006 @ 15:38:
Wat is nu het voordeel van de structuur die je hierboven beschrijft ten opzichte van de reeds eerder aangegeven structuur door Stonley

Die van Stonley is recursief. Dus voor elk menu item een apparte query. Het model wat ik beschrijf kan een menu tree inladen met 1 query die nog relatief simpel is. het is alles behalve een heilige graal maar voor dit doel behoorlijk geschikt.

[Verwijderd]

Verwijderd schreef op vrijdag 10 november 2006 @ 15:42:
[...]

Die van Stonley is recursief. Dus voor elk menu item een apparte query. Het model wat ik beschrijf kan een menu tree inladen met 1 query die nog relatief simpel is. het is alles behalve een heilige graal maar voor dit doel behoorlijk geschikt.

In het artikel wordt het Modified Preorder Tree Traversal algoritme beschreven. Dit is juist niet recursief en is alles met 1 query binnen te halen. Heb je het artikel toch wel helemaal doorgelezen

[Verwijderd]

Verwijderd schreef op vrijdag 10 november 2006 @ 15:57:
In het artikel wordt het Modified Preorder Tree Traversal algoritme beschreven. Dit is juist niet recursief en is alles met 1 query binnen te halen. Heb je het artikel toch wel helemaal doorgelezen

Nope dat had ik niet, dan moet de juiste pagina ook gewoon geciteerd worden.
Anyways het verschil zit hem dan in het updaten, dat is bij mij weer vele malen simpeler. Je hoeft dan namelijk niet bovenliggende nodes af om de links rechts grens aan te passen.

Edit:
En wat natuurlijk behoorlijk error prone is (vanuit php) is het updaten van het 'Modified Preorder Tree Traversal algoritme'. Twee gelijktijdige rebuilds slopen naar alle waarschijnlijkheid het menu. Je kan immers met dit 'algoritme' helemaal geen integriteit afdwingen. Nee, ik ben er eigenlijk helemaal neit van gecharmeert.

[ Voor 22% gewijzigd door Verwijderd op 10-11-2006 16:13 ]

[koekiemonster]

Verwijderd schreef op vrijdag 10 november 2006 @ 15:27:
Ik zou niets recursiefs doen, en niets joinen.
Simpelweg je tabel drie niveaus geven dus:

surrogaat_id | root_id | sub_id | sub_sub_id | overige_meuk

met relaties:
root_id 1-n sub_id
sub_id 1-n sub_sub_id

geen joins, geen gedoe.
Opbouwen als tree in je script moet je toch

Dit lijkt inderdaad de sneltse uitwerking voor de gebruiker. Echter ik zit nu al vast aan bepaalde data, waardoor een recursieve oplossing dan toch meer voor de hand ligt.

[Verwijderd]

Verwijderd schreef op vrijdag 10 november 2006 @ 16:07:
En wat natuurlijk behoorlijk error prone is (vanuit php) is het updaten van het 'Modified Preorder Tree Traversal algoritme'. Twee gelijktijdige rebuilds slopen naar alle waarschijnlijkheid het menu. Je kan immers met dit 'algoritme' helemaal geen integriteit afdwingen. Nee, ik ben er eigenlijk helemaal neit van gecharmeert.

Hoezo is het updaten van het algoritme error prone. Dat twee gelijktijdige rebuilds het menu slopen hoeft niet het geval te zijn. Daarvoor is transaction handling uitgevonden in een RDBMs.

Dit 'probleem' is overigens op te lossen door naast een left en right kolom ook nog een parent kolom op te nemen. Niet dat dat een ideale oplossing is in het kader van normalisatie, maar het zou wel kunnen. Dan zijn de left en right kolom dus een aanvulling die voor een optimalisatie zorgen.

Bij jou oplossing kunnen er overigens ook twee handelingen tegelijk gebeuren:

• een gebruiker voegt sub_sub_node y toe aan sub_node x;
• een andere gebruiker verwijdert sub_node x.

In een dergelijke situatie kan het voorkomen dat de sub_sub_node y is verdwenen...

Niet dat ik een groot voorstander ben van het algoritme (er zitten inderdaad haken en ogen aan) maar het zou een flinke optimalisatie kunnen zijn voor boomstructuren waarin voornamelijk wordt gelezen. Het grote nadeel van jou implementatie vind ik de schaalbaarheid. Maar het blijft een persoonlijke keuze

[Janoz]

Verwijderd schreef op vrijdag 10 november 2006 @ 22:58:
[...]

Hoezo is het updaten van het algoritme error prone. Dat twee gelijktijdige rebuilds het menu slopen hoeft niet het geval te zijn. Daarvoor is transaction handling uitgevonden in een RDBMs.

Normaal wel, maar bedenk dat we het hier over een PHP/MySQL combo hebben. Dat is ook precies wat Mark aanhaalt in zijn beargumentatie.

[tech-no-logical]

mysql heeft al een tijdje support voor transactions, en dat mechanisme is ook vanuit php prima te gebruiken.

maar in dit geval, als 't om een redelijk beperkt aantal items gaat (meestal toch het geval in een menu) zou ik gewoon in 1 query alle records binnenhalen, en met php recursief de structuur bouwen. simpele code, en de performance-hit is (als je geen site met extreem veel requests hebt) verwaarloosbaar. het model wat de ts hier gebruikt, gebruik ik ook, en deze manier van werken heeft mij nog nooit problemen opgeleverd.

[StephanVierkant]

Sorry dat ik deze even omhoog schop, maar het leek mij het beste topic om deze vraag te stellen.

De vraag van TS heb ik ook, alleen heb ik het echte antwoord nog niet gevonden. Ik probeer nu een goede boomstructuur hebben.

Ik heb nu dit:

PHP:

function display_children($parent, $level) {
   // retrieve all children of $parent
   $result = mysql_query('SELECT * FROM cms WHERE parent="'.$parent.'";');

   // display each child
   while ($row = mysql_fetch_array($result))
   {
        echo "<ul>\n";
        echo "\t<li><a href=\"?id=" . $row["id"] . "\">". $row['title'] . "</a>";
        display_children($row['title'], $level+1);
        echo "</li>\n";
        echo "</ul>\n";
    }
}

Ik krijg echter een code terug die me niet helemaal bevalt:

HTML:

<ul>
    <li><a href="?id=1">Food</a>
    <ul>
        <li><a href="?id=2">Fruit</a>
        <ul>
            <li><a href="?id=7">Appel</a>
            <ul>
                <li><a href="?id=8">Geel</a></li>
            </ul>
            <ul>    <li><a href="?id=6">Green</a></li>
            </ul>
            </li>
        </ul>
        <ul>
            <li><a href="?id=11">Peer</a></li>
        </ul>
        </li>

    </ul>
    <ul>
    <li><a href="?id=9">Soep</a>
    </li>
    </ul>
</li>
</ul>

Het moge duidelijk zijn dat dit niet helemaal juist is: er is een </ul> en een <ul> teveel in het geval van Geel en Groen. Ik heb de oplossing hiervoor nog nergens kunnen vinden.
Heeft iemand een idee?

[Sjoerd]

De ul buiten de loop plaatsen?

[Voutloos]

Stephan4kant schreef op woensdag 06 februari 2008 @ 14:02:
Sorry dat ik deze even omhoog schop, maar het leek mij het beste topic om deze vraag te stellen.

De vraag van TS heb ik ook, alleen heb ik het echte antwoord nog niet gevonden. Ik probeer nu een goede boomstructuur hebben.

Ik heb nu dit..

Wat dus heel veel queries oplevert.

Een mooiere, efficienter manier, welke nog steeds eenvoudig is, met eenzelfde recursieve truc, maar met 1 enkele query is beschreven door (oa) Crisp: http://crisp.tweakblogs.n...using-only-one-query.html

Alhoewel deze post dateert van na de topicstart, was ook in 2006 al menig tutorial met een betere aanpak beschikbaar. En al met al is dit ook geen rocket science.

[mithras]

Voutloos schreef op woensdag 06 februari 2008 @ 14:18:
[...]
Wat dus heel veel queries oplevert.

Een mooiere, efficienter manier, welke nog steeds eenvoudig is, met eenzelfde recursieve truc, maar met 1 enkele query is beschreven door (oa) Crisp: http://crisp.tweakblogs.n...using-only-one-query.html

Alhoewel deze post dateert van na de topicstart, was ook in 2006 al menig tutorial met een betere aanpak beschikbaar. En al met al is dit ook geen rocket science.

En dan stuur ik je gelijk door naar de laatste reactie, welke van mij is en tipt over MPTT. Je kan dan veel sneller een boomstructuur ophalen. En aangezien je een menu veel vaker ophaalt dan aanpast, is mptt ook stukken efficiënter!

[Voutloos]

Ik had de reacties gelezen, iedereen moet die afwegng zelf maken. Op zich is menu ook wel eenvoudig te cachen als je daar zin in zou hebben.

[mithras]

Tja, als je caching ziet als oplossing voor zware processing (bij sql of php), zou ik eerder een ander model kiezen waar je veel efficiënter omgaat met je middelen

[FragFrog]

Stukken efficienter valt nog te bezien - de manier die Crisp omschrijft vereist maar 1 query en doet daarna wat simpele logica. Ja, er zit een recursieve functie in, maar die vereist echt niet zoveel resources. Bovendien kun je het ook zo coden dat je een enkele instance van je recursieve functie hebt (wat, toegegeven, iets lastiger is) waarna het performanceverschil nauwelijks waarneembaar is.

Nadelen aan MPTT zijn er ook genoeg; zo moet je een enorme zut updatequeries uitvoeren bij een enkele wijziging, is het erg lastig om nodes altijd voor een bepaalde sectie uit te zetten (als je bijvoorbeeld een dynamisch menu hebt) en kost het je 2 extra kolommen. Daarnaast zul je altijd zelf een stack van rightvalues moeten bijhouden en updaten als je wilt indenten wat evengoed performance kost.

Ja, het is veel efficienter dan voor elke node een aparte query uitvoeren, dat spreekt voor zich. Maar als je het gaat vergelijken met de manier die oa Crisp beschrijft is het verschil verwaarloosbaar. Voor mij is door het extra gezeur wat je ermee op de hals haalt het al niet meer de moeite waard

[mithras]

Ik denk ook niet dat MPTT de hoogste performance heeft bij een simpele mogelijkheid als een menuweergave. Ik denk echter wel dat het goed is om er bekend mee te raken, want bij grotere problemen merk je pas echt voordeel.

Bijvoorbeeld een RBAC authenticatie en authorisatie systeem waarbij gebruikers in groepen zitten, groepen hiërarchische gerangschikt zijn en er rollen cq rechten aan groepen worden toegekend. Het kan dan zo zijn dat jouw subgroep een bepaald recht niet heeft gespecificeerd, maar de group een niveau hoger wel. Dat recht moet jij uiteraard wel krijgen.
Met zulke dingen ga je behoorlijke snelheidswinsten merken bij een MPTT model

[Voutloos]

Lang verhaal kort: Vandaar dat ik zei dat iedereen je eerdere reactie kan lezen en de afweging mag maken.