[Php/mysql] recursief tree weergeven *

[Verwijderd]

Ik zit al een hele tijd de klooien met het volgende:

Ik heb een database met een aantal 'items'. Deze wil ik in een lijstje hebben, maar er zijn zegmaar: hoofd- en subitems, en weer subitems daarvan. (Een subitem moet een stukje inspringen ten opzichte van het hoofditem)

in mysql zit het zo in elkaar:

code:

id | main_id

1 niveau verschil lukt me nog wel, maar de sub-items dáárvan lukt me gewoon niet om weer te geven. Hoe doe ik dit?

[ Voor 3% gewijzigd door Verwijderd op 26-02-2003 15:53 ]

[Verwijderd]

En ik kan de topictitel niet aanpassen. Was m vergeten

[Janoz]

Die ga ik niet voor je verzinnen, geef een voorstel.. Daarnaast kun je met het potlood icoontje je post weizigen...

Over probleem:

Waar je heir mee bezig bent is een recursieve verwijzing. Elk onderdeel heeft weer een parent ed. Dit is nogal lastig te implementeren in een RDBMS, maar er zijn al behoorlijk wat topics hierover op GoT langs gekomen

[Fatamorgana]

Functie recursief aanroepen en een nummertje ophogen en meesturen, dan weet je ook hoe ver je moet inspringen en op welk nivo je zit.

[Verwijderd]

Moet ik verder mee kunnen komen.
Maar moet ik nu voor elk item een sqlquery doen? Je moet toch checken OF er een nivo onder zit? Of kan je dat op èèn of andere manier uit een array halen?

[Fatamorgana]

Gewoon de functie aanroepen en in de functie kijken of je records terug krijgt. Zo niet, dan roep je niet nog eens de functie aan, is dit wel zo dan roep je hem wel aan. Hierdoor loop je mooi alles door en werkt het gewoon goed. Het is alleen lastig debuggen als je een fout maakt.

Iets als dit zou moeten kunnen als ik ff snel iets bedenk:

code:

function showrecords(id){
  doquery met id
  indien records aanwezig{
    while not at end of records{
      laat record zien
      roep functie showrecords aan met id van dit record als parameter
      haal volgende record op
    }
  }
}

Resultaat is een mooie boomstructuur. Op zo'n soort manier heb ik ook een database managebaar menu gemaakt met allemaal submenu's enzo.

[ Voor 51% gewijzigd door Fatamorgana op 26-02-2003 16:26 ]

[Verwijderd]

Dat hoeft zeker niet met een hele rits losse queries, dat kan perfect met een array die je in 1 query vult.

Waar je aan zou kunnen denken is een lus die met alle items uit de array toont en daarna de recursieve functie 'subitems' aanroept.

Hiermee voorkom je dat je voor een menutje tientallen queries gaat lopen uitvoeren, wat uiteraard de database server niet zo ten goede komt...

[ Voor 25% gewijzigd door Verwijderd op 26-02-2003 16:31 ]

[Fatamorgana]

Verwijderd schreef op 26 February 2003 @ 16:29:
Dat hoeft zeker niet met een hele rits losse queries, dat kan perfect met een array die je in 1 query vult.

Als je me die query kunt geven dan zou ik heel blij zijn, ik heb hem niet kunnen bedenken. Ik loop steeds vast op het punt dat MySQL geen subqueries kent.

[Verwijderd]

Ja. T is geen menu, meer een overzichtje.
For the record: K heb nu dit. Om het sneller te maken ga ik wel even wat met arrays klooien.

PHP:

function createTree($main_id, $nivo, $onderdeel_id) {
    $result = mysql_query("SELECT item_id, main_id, kop FROM items WHERE main_id=$main_id blabla");
    if (mysql_num_rows($result) > 0) {
        while ($row = mysql_fetch_object($result)) {
            $space = $nivo*10;          
            echo "<div style=\"margin-left: ".$space."px;\">$main_id - $row->item_id -->".$row->kop."</div><br>";
            createTree($row->item_id, $nivo+1, $onderdeel_id);
        }
    } 
}
createTree(0,0,$onderdeel_id);

[drm]

offtopic:
topictitle aangepast

[Genoil]

Er zijn ook manieren om zonder subselects zo'n tree met 1 query er uit te fietsen, maar dat vereist weer een heel andere benadering. Er is hierover wel eens iets langsgekomen in /14, zal je ff moeten zoeken. Wat je ook kunt doen is het volgende, aangenomen dat je de tree veel minder vaak van structuur verandert dan dattie uitgelezen word (en dat is heel vaak het geval): Je maakt een extra tabel aan met de kolommen (PRIMARY id, item_id, nivo), die je elke keer nadat je wijzigingen in de structuur van de tree hebt aangebracht (dus bij een toevoeging, verwijdering of verplaatsing van een node) leegmaakt en opnieuw vult met de "lineaire" resultaten van je createTree functie. Dus op de plek van je echo "<div.." doe je een INSERT in je schaduwtabel met de waarden $row->item_id en $nivo.

Het uitlezen van de tree is dan 1 vrij eenvoudige query (SELECT items.*, schaduw_items.nivo FROM items, schaduw_items WHERE items.item_id = schaduw_items.item_id ORDER BY schaduw_items.id). Zo doe ik het zelf overigens niet, ik gebruik een tree voor windows-explorer-achtige navigatie, waarbij ik alleen de nodes openklap die zich in het pad bevinden. Het aantal queries blijft daarbij beperkt tot de diepte van je huidge pad.

Bovenstaande oplossing is handig voor wanneer je de hele tree altijd wilt laten zien, niet wanneer je de boel open en dicht wilt kunnen klappen. Kan ook wel, maar dan wordt het weer een stukje lastiger

[ Voor 19% gewijzigd door Genoil op 26-02-2003 18:38 ]

[Verwijderd]

Fatamorgana schreef op 26 February 2003 @ 16:34:
Als je me die query kunt geven dan zou ik heel blij zijn, ik heb hem niet kunnen bedenken. Ik loop steeds vast op het punt dat MySQL geen subqueries kent.

Wat ik bedoelde is het volgende:
- met 1 simpele query alle rijen ophalen
- alle resultaten in een multidimensionale array zetten (met een lusje)
- met die array gaan werken

Het 'met die array werken' kan alsvolgt:
- met lusje door array gaan, en voor iedere rij die een 'basis' item is een functie aanroepen
- die functie krijgt een rijnummer, plaatst dat rijnummer, en zoekt alle 'subitems' die bij zichzelf horen (via in_array oid). In een lusje roept de functie zichzelf aan met alle gevonden rijnummers (recursief dus)

Dat is de methode die ik gebruik voor een menu structuur, en is een stuk sneller in verhouding tot allemaal losse queries (wat ik in een oude versie had)

[plakbandrol]

zie dit topic

[rml][ php] trees mooi opbouwen[/rml]

daar ben ik dus mee bezig, op die ene bug na werkt ie goed

[Genoil]

Verwijderd schreef op 26 February 2003 @ 20:45:
[...]


Wat ik bedoelde is het volgende:
- met 1 simpele query alle rijen ophalen
- alle resultaten in een multidimensionale array zetten (met een lusje)
- met die array gaan werken

Het 'met die array werken' kan alsvolgt:
- met lusje door array gaan, en voor iedere rij die een 'basis' item is een functie aanroepen
- die functie krijgt een rijnummer, plaatst dat rijnummer, en zoekt alle 'subitems' die bij zichzelf horen (via in_array oid). In een lusje roept de functie zichzelf aan met alle gevonden rijnummers (recursief dus)

Dat is de methode die ik gebruik voor een menu structuur, en is een stuk sneller in verhouding tot allemaal losse queries (wat ik in een oude versie had)

Betekent dat nou dat je gewoon ongeacht de hierarchie ALLE nodes ophaalt en vervolgens met php de hierarchie gaat berekenen? In mijn php boek staat dat ik altijd zoveel mogelijk door MySQL moet laten uitzoeken

Voor een menuutje kannik me zoiets nog wel voorstellen, voor een enorme hierarchisch ingedeelde database wordt dit imho problematisch.

[Verwijderd]

Genoil schreef op 26 February 2003 @ 23:27:
[...]


Betekent dat nou dat je gewoon ongeacht de hierarchie ALLE nodes ophaalt en vervolgens met php de hierarchie gaat berekenen? In mijn php boek staat dat ik altijd zoveel mogelijk door MySQL moet laten uitzoeken

Voor een menuutje kannik me zoiets nog wel voorstellen, voor een enorme hierarchisch ingedeelde database wordt dit imho problematisch.

Ja, want je zal ze uiteindelijk toch allemaal nodig hebben... En ja, je moet zoveel mogelijk uitlaten zoeken door mysql maar ik ben iig niet tot een oplossing gekomen waarbij dat kon zonder voor ieder lusje een losse query te doen.
Bij mij bleek deze manier vele malen sneller te zijn.

En wat betreft de grootte: zolang het beperkt blijft tot enkele honderden menu-items is er nog niets aan de hand. Mocht je boven dat aantal komen heeft een menu weinig zin meer, daar het dan een meter lang wordt.

Overigens als iemand een betere manier weet hoor ik het graag, want ik vind dit in principe ook geen geweldige manier, wel het beste wat ik tot nogtoe heb.

[ Voor 8% gewijzigd door Verwijderd op 27-02-2003 07:56 ]

[drm]

Fuego:
Ja, want je zal ze uiteindelijk toch allemaal nodig hebben... En ja, je moet zoveel mogelijk uitlaten zoeken door mysql maar ik ben iig niet tot een oplossing gekomen waarbij dat kon zonder voor ieder lusje een losse query te doen.
Bij mij bleek deze manier vele malen sneller te zijn.

Dat is waar, er zijn uberhaupt weinig dbmsen die wel met dergelijke recursie om kunnen gaan...

En wat betreft de grootte: zolang het beperkt blijft tot enkele honderden menu-items is er nog niets aan de hand. Mocht je boven dat aantal komen heeft een menu weinig zin meer, daar het dan een meter lang wordt.

Mja, daar hebben we andere systeempjes voor. Je harddisk bevat toch ook wel meer dan honderden bestanden?

Overigens als iemand een betere manier weet hoor ik het graag, want ik vind dit in principe ook geen geweldige manier, wel het beste wat ik tot nogtoe heb.

Qua performance is het idd de beste manier, die ik ook kan bedenken

[Fatamorgana]

Ik denk dat ik voor mijn menu het volgende ga doen. Gewoon met de manier van bergen queries het menu opbouwen en dan alles naar een mooie include file schrijven en pas wanneer het menu is aangepast dit weer opnieuw doen. Zo vaak wordt een menu nl niet aangepast.

[bigtree]

Nu ik voor de zoveelste keer een dergelijk topic voorbij zag komen, heb ik nog eens over dit probleem na zitten denken. Het doel van deze methode is dat je met één simpele query een item en alle onderliggende items wilt ophalen.
Toen kwam ik met een leuke oplossing, maar misschien willen jullie nog nadenken over de puntjes op de ı. Weliswaar met 2 queries, maar het werkt wel een stuk makkelijker.

Je hebt 2 tabellen: Items en Children. In de Children-tabel worden items met onderliggende items gelinkt. Bijvoorbeeld Item 1 heeft twee onderliggende items (Items 2 en 3), dan is de inhoud van tabel Children:
ItemID ChildID
1 2
1 3

Om nu item 1 en alle onderliggende items op te halen, heb je 2 queries nodig:
- Eentje om Item 1 op te halen
SELECT * FROM Items WHERE ItemID = 1

- Eentje om alle onderliggende Children op te halen
SELECT Items.* FROM Children INNER JOIN Items ON Children.ChildID = Items.ItemID WHERE Children.ItemID = 1

Maar nu: als je een item toevoegt aan de Items tabel moet je er ook voor zorgen dat de Children tabel correct wordt bijgewerkt. Als we bijvoorbeeld onder item 3 een nieuw item hangen, wordt dat een onderliggend Child voor item 3 èn 1. Stel; dit nieuwe item is Item 4, deze heeft als directe parent Item 3. We moeten nu 2 invoegqueries doen:
- Eentje om Item 4 als Child aan te melden bij alle Items die Item 3 als Child hebben
INSERT INTO Children (ItemID, ChildID) SELECT ItemID, 4 FROM Children WHERE ChildID = 3

- Eentje om Item 4 als Child van Item 3 aan te melden
INSERT INTO Children (ItemID, ChildID) VALUES (3, 4)

Op deze manier heb je voor het invoegen en ophalen steeds maar 2 queries nodig. De performance van deze methode zal daarom een stuk beter zijn dan met een recursieve functie.

[ Voor 4% gewijzigd door bigtree op 27-02-2003 10:31 ]

[Verwijderd]

je hebt het over 2 queries, maar dat is per basis-item en bijbehorende subitems. Kortom de enige winst haal je bij niveau 3 en verder.
En omdat het aantal basisitems meestal vrij groot is krijg je toch heel veel keer 2 queries. Voeg daarbij nog het lastiger toevoegen/verplaatsen en een onnodige tabel, en je houdt imho weinig voordeel meer over...

[edit]
ik heb weer eens te snel gelezen het heeft toch duidelijk wel voordelen. Maar ik blijf het omslachtig vinden

[ Voor 17% gewijzigd door Verwijderd op 27-02-2003 11:00 ]

[bigtree]

Verwijderd schreef op 27 februari 2003 @ 10:57:
je hebt het over 2 queries, maar dat is per basis-item en bijbehorende subitems.

Nee nee, ALLE onderliggende items.

edit:
Je had het al gezien

[ Voor 8% gewijzigd door bigtree op 27-02-2003 11:00 ]

[Bosmonster]

Mwah.. ik ga ook niet voor iedere recursie een nieuwe query uit lopen voeren. Haal wel eerst alle items op (is toch alleen maar zooitje ID's en titel), zet ze in een array en loop hier doorheen. Ik heb de recursie wel omgedraaid (? ) om volgorde te behouden zoals ik ze in de query opvraag (op volgnr, titel)

PHP:

$sql = "SELECT ID, titel, parent, type, locked FROM gb_menu ORDER BY volgnr, titel";
$rs  = mysql_query ($sql) or gb_error (ERROR_MYSQL_QUERY);
    
$menu = array();

while ($row = mysql_fetch_object($rs))
    $menu[$row->parent][] = array($row->ID, $row->titel, $row->type, $row->locked);

Dat geeft me een array waarin alles gegrouped is op parent, en iedere parent z'n subitems goede volgorde onder zich heeft. Hier loop ik doorheen met een structuur als deze (verschilt naar wat ik ermee wil):

PHP:

function gb_write_menu ($arr, $par, $lvl = 0)
{
    for ($i = 0; $i < sizeof($arr[$par]); $i ++)
    {
        $id     = $arr[$par][$i][0];
        $title  = $arr[$par][$i][1];
        $type   = $arr[$par][$i][2];
        $locked = $arr[$par][$i][3];

        $can_be_deleted = (($type == 1 || $type == 2 || ($type == 0 && !isset ($arr[$id]))) && $locked == 0);
        $can_have_subs  = ($type == 0 && $lvl < MENU_MAX_LEVEL);
        $can_have_menus = ($can_have_subs && $lvl < (MENU_MAX_LEVEL - 1))
        
        // write html per item here :)

        if ($type == 0 && isset ($arr[$id]))
            gb_write_menu ($arr, $id, $lvl + 1);
    }
}

Tis maar een voorbeeld.. Kan op tig manieren.. Maar ik ben persoonlijk niet voor het opnemen van een query in je recursie... Je script moet in de recursie zo tig keer wachten op de query-output, wat aardig op kan lopen.