Traverzování kolem stromu prakticky

Školení, která pořádám

Pro uložení hierarchických struktur se dá použít několik různých přístupů, už jsem o tom konec konců psal. Strukturou umožňující snadnou a efektivní práci s hierarchickými daty je traverzování kolem stromu. Myšlenka této struktury je popsána jinde, já bych se chtěl zaměřit na praktický popis základních operací. Data budeme ukládat do tabulky strom (id, lft, rgt, hloubka, nadpis, ...). Hloubka záznamu je odvoditelná z hodnot lft a rgt, ale její zjišťování je poměrně pracné, navíc pro některé operace (např. výpis přímých potomků) se samostatně uložená hloubka může hodit.

Výpis stromu

<?php
$result = mysql_query("SELECT * FROM strom ORDER BY lft");
while ($row = mysql_fetch_assoc($result)) {
    echo str_repeat("- ", $row["hloubka"]) . htmlspecialchars($row["nadpis"]) . "<br />";
}
mysql_free_result($result);
?>

Výpis celého stromu je přímočarý, stačí vypsat prvky seřazené podle lft – nad tímto sloupcem je tedy vhodné mít index. Pokud bychom chtěli vypsat jen část stromu, stačilo by omezit hodnoty lft a rgt tak, aby byly mezi kořenem výpisu. Pokud bychom chtěli vypsat jen přímé potomky, stačilo by omezit hloubku.

Výpis stromu do seznamu s odrážkami

<?php
$result = mysql_query("SELECT * FROM strom ORDER BY lft");
$hloubka = -1;
while ($row = mysql_fetch_assoc($result)) {
    if ($hloubka < $row["hloubka"]) {
        echo "<ul>";
    } else {
        echo str_repeat("</li></ul>", $hloubka - $row["hloubka"]) . "</li>";
    }
    echo "<li>\n" . htmlspecialchars($row["nadpis"]);
    $hloubka = $row["hloubka"];
}
echo str_repeat("</li></ul>", $hloubka + 1) . "\n";
mysql_free_result($result);
?>

Při výpisu do seznamu s odrážkami musíme detekovat, jaký je vztah aktuálního a předchozího uzlu. Kód počítá s tím, že hloubka prvků nejvyšší úrovně je 0. Pokud by to byla 1, bylo by potřeba proměnnou $hloubka inicializovat na 0 a na závěr k ní nepřičítat jedinčku.

Drobečková navigace

<?php
$row = mysql_fetch_assoc(mysql_query("SELECT * FROM strom WHERE id = " . intval($_GET["id"])));
$result1 = mysql_query("SELECT * FROM strom WHERE lft < $row[lft] AND rgt > $row[rgt] ORDER BY lft");
while ($row1 = mysql_fetch_assoc($result1)) {
    echo "<a href='?id=$row1[id]'>" . htmlspecialchars($row1["nadpis"]) . "</a> &gt; ";
}
mysql_free_result($result1);
echo htmlspecialchars($row["nadpis"]);
?>

Seznam prvků od kořenu až k danému prvku získáme tak, že si necháme vrátit všechny prvky, které mají lft menší a rgt větší než vypisovaný prvek.

Přidání prvku na konec stromu

<?php
mysql_query("INSERT INTO strom (lft, rgt, hloubka, nadpis) SELECT IFNULL(MAX(rgt), 0) + 1, IFNULL(MAX(rgt), 0) + 2, 0, '" . mysql_real_escape_string($_POST["nadpis"]) . "' FROM strom");
?>

Pro přidání prvku na konec stromu potřebujeme zjistit maximální rgt. S využitím konstrukce INSERT SELECT to můžeme provést atomicky.

Přidání potomka uzlu

<?php
mysql_query("START TRANSACTION");
$row = mysql_fetch_assoc(mysql_query("SELECT * FROM strom WHERE id = " . intval($_GET["rodic"]) . " FOR UPDATE"));
mysql_query("UPDATE strom SET lft = lft + 2 WHERE lft > $row[rgt]");
mysql_query("UPDATE strom SET rgt = rgt + 2 WHERE rgt >= $row[rgt]");
mysql_query("INSERT INTO strom (lft, rgt, hloubka, nadpis) VALUES ($row[rgt], $row[rgt]+1, $row[hloubka]+1, '" . mysql_real_escape_string($_POST["nadpis"]) . "')");
mysql_query("COMMIT");
?>

Pokud přidáváme existujícímu uzlu potomka, potřebujeme zjistit jeho rgt. Hodnota lft vkládaného prvku bude odpovídat zjištěnému číslu, rgt bude o jedničku vyšší. Všechny následující prvky posuneme. Všechny operace je nutné provést atomicky, proto používáme transakce. S MyISAM tabulkami bychom místo transakcí použili exkluzivní zámek tabulky.

Smazání podstromu

<?php
mysql_query("START TRANSACTION");
$row = mysql_fetch_assoc(mysql_query("SELECT * FROM strom WHERE id = " . intval($_GET["id"]) . " FOR UPDATE"));
mysql_query("DELETE FROM strom WHERE lft >= $row[lft] AND rgt <= $row[rgt]");
$rozdil = $row["rgt"] - $row["lft"] + 1;
mysql_query("UPDATE strom SET lft = lft - $rozdil WHERE lft > $row[rgt]");
mysql_query("UPDATE strom SET rgt = rgt - $rozdil WHERE rgt > $row[rgt]");
mysql_query("COMMIT");
?>

Pro smazání podstromu musíme zjistit lft a rgt kořene mazání a smazat všechny prvky mezi těmito hodnotami. Následující prvky opět musíme posunout.

Viz také přesuny uzlů.

Přijďte si o tomto tématu popovídat na školení Návrh a používání MySQL databáze.

Jakub Vrána, Řešení problému, 27.8.2007, diskuse: 56 (nové: 0)

Diskuse

Matej:

Stalo by za to rict, ctj lft, rgt a hloubka.
Jinak je to vytrzene z kontextu.

štíhloprd:

Vizte onen odkaz na interval.cz

http://interval.cz/clanky/metody-ukladani-…-databazich/

(kapitola "Traverzování kolem stromu")

Ondra:

Pěkné. Nicméně operace typu mazání, vkládání jsou poměrně jednoduché. Spíš by mě zajímalo, jak provést přesunutí položek z jednoho uzlu pod jiný. Ptám se poto, že tohle mě v nejbližších dnech asi potká, proto jestli byste třeba mohl naznačit ideální řešení :)

Ondrej Ivanic:

Ano vsetko je jednoduche az na insert a presun casty stromu. Ak sa tieto operacie budu robit casto je rozumne zvolit iny sposob ulozenia.

Ulozenie takeho stromu je velmi vhodne do roznych eshop-ov kde je strom kategorii ktory je prekticky nemenny a pomocou jedneho select-u sa viem dopracovat k vsetkym produktom v danej kategorii, atd...

Odporucam jednu knihu a jeden clanok v ktorom je tak niha uvedena:
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html
Joe Celko: Trees and Hierarchies in SQL for Smarties

Ondra:

Hmm zajímavé čtení. Ale opět zde chybí ono přesmisťování mezi uzly :) Ale určitě to půjde. Jen jsem myslel, že by mi tu někdo mohl ušetřit práci :) Ale asi se na to budu muset vrhnout sám :(

klevo:

http://api.cakephp.org/1.2/tree_8php-source.html

Michal:

Ja to nedavno delal "jednoduse" - krome 'lft' a 'rgt' mam v u kazdeho zaznamu i 'parent'. Kdyz strom preorganizuju tak na nem udelam "rebuild_tree" a ten mi znovu vypocita lft a rgt. Ja vim, neni to elegantni reseni, ale je pomerne strucne a jasne. Ovsem v mem pripade jde o stromy s radove jen desitkami polozek takze prepocitani trva okamzik.

Filip:

Já jsem přesouvání uzlů stromu vymyslel následovně:
vypočítám si $size (rgt-lft+1 přesouvaného uzlu) a $shift. U posunu vpravo je $shift rgt nového rodiče - rgt uzlu - 1 a u posunu vlevo je to lft uzlu - rgt nového rodiče.
Nejprve se "udělá místo". $size se přičte všem rgt a lft větším rovno rgt nového rodiče (lft a rgt zvlášť ve dvou dotazech), u posunu doleva se tímto zvětší lft a rgt posouvaného uzlu.
U přesunu doprava se poté k hodnotám lft a rgt přesouvanému uzlu a jeho případných potomků přičte hodnota $shift i $size a nakonec se odečte $size od lft a rgt u uzlů s větším rgt než byla hodnota rgt přesouvaného uzlu na počátku (ve dvou dotazech zvlášt lft a rgt).
U přesunu doleva je pak nutné odečíst od lft a rgt přesouvaných uzlů $size i $shift a nakonec odečíst $size od lft a rgt u uzlů s větším rgt než nová hodnota rgt po "udělání místa" (ve dvou dotazech zvlášt lft a rgt).
Doufám, že to dává trochu smysl, umožňuje to přesouvat uzly doprava i do leva mezi úrovněmi, kdy přesouvaný uzel je zařazen jako nejvíce pravý potomek nového rodiče. Přesouvání v rámci jedné urovně stejného rodiče lze udělat podobně.

Ondra:

Hmm velice fajn řešení. Původně jsem udělal své, kde bylo o dva dotazy do DB méně, ale potřeboval jsem k tomu pole, do kterého jsem si ukládal id přenášených položek. To tvé řešení se mi ale zdá být lepší.

Dobrá práce ;)
Dík

Ondra:

to Matej: Doporučuji přečíst si článek, na který autor v úvodu odkazuje :) Pak by mělo být vše jasno.

Jozka:

Diky za clanek.

Petan:

mám s tímto typem stromu zkušenosi V PostgreSQL.
Doporučuju jeho ho používání zvážit. Hlavně s ohledem na to jak často se bude aktualizovat (update, delete, insert) a jak bude velký. Realizoval jsem tento typ stromu (+ zakomponoval  jsem jakési klony) takže fce typu MoveNode(), CloneNode() apod jsem realizoval.
Problém toho to typu stromu je že se musí přepočítat celý při každé akci DELETE nebo INSERT, MOVE či CLONE (lft a rgt hodnoty se mění). Takže se nehodí na data která se příliš často mění. Nemluvím o přidávání na konec stromu ale kamkoliv do struktury - a čím výše to je tím více se toho bude přepočítávat.
Teorii jsem čerpal z pěkného článku (en):
teorie Modified Preorder Tree Traversal
http://www.sitepoint.com/article/hierarchical-data-database/

matak:

Také mám s tímto typem stromu už nějakou dobu zkušenosti pokud jde o výpisy různých ne moc často obměňovaných kategorií tak není problém do 1000 položek, víc nemohu říci. Už nějaký rok to běží na různých diskusích se stromovou strukturou, ale tam bych to příliš nedoporučoval, časté změny jsem vyřešil oddělením stromu diskuse od každého článku, ale hlavně když diskusi napadl spam robot a během dne tam bylo kolem půl milionu příspěvků (použití captcha neřešme to je jiná věc), takové množství pak bylo nejsnažší promazat natvrdo v dtb a tedy neproběhlo přepočítání levých a pravých hodnot, nikdo nespustil opravu stromu pomocí rebuild a pak je zacyklení velice snadné pokud nejsou synchronizované lgt a rgt hodnoty. Asi bych se bál toho zacyklení nejvíce.

ikona zaachi:

Dobry den, pokud nekoho zajima traverzovani, tak se mrknete sem:
http://zaachi.com/cs/category/blog/php/
Jsou tam zatim zakladni operace se stromem, ale doplnim tam jeste presouvani a podobne.

ikona xuffo:

Pro ty, kteri maji mene rozsahle struktury a chteji upravy stromu vyresit jednoduse a transparentne - staci si ukladat hloubku a id rodicovskeho uzlu a pri upravach menit pouze tyto hodnoty. Po kazde uprave lze potom zavolat rekurzivni funkci, ktera automaticky na zaklade techto dvou sloupcu prepocita lft a rgt:

<?php
function ObnovStrom($hloubka = 0, $rodic_id = 0)
{
$sql1 = mysql_query("SELECT * FROM strom WHERE hloubka = '$hloubka' AND rodic_id = '$rodic_id' ORDER BY nazev ASC");
  while ($data1 = mysql_fetch_assoc($sql1)) {
    mysql_query("UPDATE strom SET lft = '{$GLOBALS["index"]}' WHERE id = '{$data1["id"]}' LIMIT 1");
    $GLOBALS["index"]++;

    $this->ObnovStrom($hloubka + 1, $data1["id"]);

    mysql_query("UPDATE strom SET rgt = '{$GLOBALS["index"]}' WHERE id = '{$data1["id"]}' LIMIT 1");
    $GLOBALS["index"]++;
  }
?>

Danik:

Modified Preorder Tree Traversal se pouziva predevsim proto, aby bylo mozno vyhnout se rekurzi. Rekurze je u velmi rozsahlych aplikaci neskutecne pomala a neefektivni. Ja pouzivam MPTT proto, ze potrebuji jednim dotazem ziskat cely strom od daneho uzlu nahoru (dedicnost, zejmena uzivatelska opravneni) i dolu (vypisy etc.). Zaroven potrebuji, aby muj system byl schopen snadnych zmen a rychleho provozu a pritom neprekonatelne stability. Cetl jsem pred casem kdesi clanek o optimalizaci MPTT z hlediska manipulace s daty. Vnukl mi nekolik napadu. Predpokladejme nasledujici podminky:

1. Strom je co do rozsahu neomezeny.
2. Kazdy uzel muze mit libovolne mnozstvi potomku.
3. Z hlediska redundance a duplicity je vyhodnejsi pouzivat spise neco na zpusob odkazu na uzly nez klonovani.
4. Ziskavani dat musi byt naprosto jednoduche a maximalne rychle.

Udaje o strukture udrzujeme pomoci sloupcu lft, rgt a parent. Parent je dulezity proto, ze neni mozne jednim sql dotazem ziskat pouze prime potomky resp. primeho rodice uzlu. Ono to mozne je, ale jedine za pouziti subselectu a snizuje to efektivitu a prehlednost kodu.
Veskere selecty jsou nyni jednoduche a intuitivne odvoditelne, nebudu se zabyvat jejich presnym popisem, protoze se prakticky shoduji s tim, co bylo popsano vyse. Ted jde o manipulaci s daty stromu.

1. Uzly nemazeme pomoci dotazu DELETE, spise si nejakym zpusobem pamatujeme, ze jsou smazany, napriklad pomoci bitove masky, ktera zaroven umoznuje uchovavat dalsi informace o uzlu. To nam poslouzi dale.
2. Kdyz vkladame novy uzel jako potomka jiz existujiciho uzlu, nejdrive zkontrolujeme, jestli cilovy rodicovsky uzel nahodou neobsahuje potomka, oznaceneho jako SMAZANO. Pripadneho nalezeneho potomka pak jednoduse nahradime novym uzlem a usetrime si prestavbu stromu.
3. Kdyz uz situace jinak neda a my musime strom prebudovat, usetrime si rovnou trochu prace do budoucna. Jednoduse vytvorime vetsi mezery, nez jake nezbytne potrebujeme, coz nam da priste moznost vlozit k tomu kteremu rodici potomka bez nutnosti prestavovat cely strom. Rekneme, ze si zvolime sude cislo vetsi nez 2, nazveme si jej treba minimum. Spocteme pocet primych potomku, ktere cilovy rodicovsky uzel jiz ma, a vynasobime dvema; nazveme si vysledek optimum. Strom posleze upravujeme vyssim z techto dvou cisel. Dochazi tim k efektu jakehosi "samoladeni": uzly, ktere casto ziskavaji nove potomky, pro sebe alokuji vice mista, cimz do budoucna snizuji pocet nutnych prestaveb.
4. Poslednim krokem pri uprave by melo byt vycisteni stromu. Vsechny operace predpokladaji "zarovnani vlevo", tj. hodnota lft je pro dany uzel vzdy co nejnizsi, zatimco vpravo (vne uzlu) muze zbyt jeste nejake misto. Takova situace muze nastat, jestlize smazeme natvrdo uzel oznaceny jako SMAZANO a na jeho misto prilepime jiny uzel, ktery nebude tak siroky, napriklad bude mit mene potomku. Potom je treba uzly napravo prisunout blize, aby na "konci" prostoru v ramci rodice zustalo co nejsirsi misto vyuzitelne bez nutnosti prestavovat strom. Tento bod je posledni, ktery jsem jeste nevyresil, nicmene nepovazuji to za kdovijak slozity problem, pokud se to bude provadet pravidelne. Je to trochu jako s defragmentaci disku :o).

Omlouvam se vsem za rozsah a slozity jazyk prispevku, stylistika mi nikdy nijak nesla :o) pokud budu mit trochu casu, muzu se to pokusit objasnit nejakym diagramem... Zaroven prosim o dalsi napady a kritiku :o)
Nakonec se omlouvam za diakritiku, ale pisu z mobilu a uz tak jsem rad ze vubec napisu tolik textu :o)
Peace.

PetaN:

Zní to hezky, a rád bych Vaše řešení viděl v reálu. Ale má vlastní zkušenost říká, že to zas tak triviální není. Zajímalo by mě ja vypadá SQL na výpis stromu s těmi odkazy na uzly.
Už to asi nebude jednoduché SELECT * FROM a WHERE left> 1 AND right < 5.

viz. bod 3. Z hlediska redundance a duplicity je vyhodnejsi pouzivat spise neco na zpusob odkazu na uzly nez klonovani.

můžete naznačit? díky. Jestli jsem to nepochopil tak se omlouvám.

Danik:

Inu moje vlastní zkušenost mi říká, že je to opravdu peklo :o) není až tak těžké představit si to, ale programovat to je vážně hraniční zážitek... Já jsem to celé řešil tak, že jsem si udělal objektový framework a samotné sql už pak coby uživatel toho frameworku nemusím řešit. A jako programátor toho frameworku jsem se spokojil s tím, že když při načtení uzlu zjistím z příznakové bitmasky, že uzel je odkazem, jednoduše změní svoje ID (podle nějž je vyhledáván při načítání v databázi) a znovu se načte. Znamená to jeden SQL dotaz navíc na každý odkaz, který načteme, ale v praxi odkazy použijeme spíše zřídka a s rekurzivními odkazy (odkaz na odkaz na nějakou stránku etc.) se nesetkáme nejspíš vůbec; oběť jednoho SQL dotazu navíc už není tak velká, aby se nedala podstoupit. Myslím, že o této problematice asi napíšu něco většího, už kvůli tomu, abych si sám ujasnil myšlenky :o) kdyžtak sem pak hodím odkaz.

cokoliw:

Dobrej článek :) díky

Peter:

Hierarchický výpis stromu mnohým uľahčí prácu, ak použijú funkciu str_repeat(), tak ako to urobil autor článku. No čo takto vytvoriť zoznam <ul> a <li>. To by už bolo trochu ťažšie... možno tip na článok ;-).

ikona Jakub Vrána OpenID:

Doplnil jsem to do tohoto článku.

štíhloprd:

Co když chci některé uzly označit za "neviditelné" (tj. chci je mít v databázi ale nechci je zobrazovat uživateli)? Ovlivní to nějak funkčnost?

Tomáš Fejfar:

Článek je opravdu fajn. C&P sem z něj to UL vykreslovaní, na samotné menu na webu mám udělaný view helper. Jenže teď mám problém. Potřebuji zobrazit nultou úroveň - kategorie shopu a k nim cestu až k současné kategorii a pod ní jednu úroveň podstromu. Vůbec si s tím nevím rady. Zkoušel sem si to nakreslit, ale nic rozumného mě nenapadlo :)

Nejste někdo zběhlejší v matice, že byste měl nakopnul?

Ivo:

Tak nevím zda-li dělám něco špatně, ale pokud chci vytvořit to menu za pomocí seznamu (ul, li) vypisuje mi to, že u funkce str_repeat musí být druhý argument číslo vyšší nebo rovno 0.

Dokázal by mi někdo vysvětlit tento řádek:
echo str_repeat("</li></ul>", $hloubka - $row["hloubka"]) . "</li>";

Pokud je u hloubky předdefinované -1 a od toho ještě budu odečítat další číslo, tak to bude vždy číslo záporné ne?

ikona Jakub Vrána OpenID:

Do větve str_repeat() se vleze jen v případě, kdy neplatí $hloubka < $row["hloubka"]. Tudíž $hloubka - $row["hloubka"] je vždy nezáporné.

Koncové str_repeat() k závěrečné hloubce přičítá jedničku, takže bez průchodu cyklem to je opět nezáporné.

Usuzuji, že jsi špatně identifikoval str_repeat() generující chybu a zároveň máš ve stromě hloubku menší než -1.

Ivo:

Máte pravdu, nějak jsem se do toho zamotal. Už jsem celkem vše za pomocí vašich ukázek rozchodil (za což mnohokrát děkuji), akorát přemýšlím nad tím, jak nějak jednoduše vypsat menu, kde bude vždy otevřená ta větev, do které patří kategorie ve které se právě nacházím.

Př.
- kategorie 1
- kategorie 2
- kategorie 3
-- kategorie 3a
-- kategorie 3b - tady jsem
  -- kategorie 3b I
  -- kategorie 3b II
-- kategorie 3c
- kategorie 4

marek:

omezit výpis pomocí lft a rgt kategorie 3b a hloubku kategorie 3b plus 1

Andrej:

Na začiatok sa chcem poďakovať za článok. Zhodou okolností práve píšem bakalársku prácu na rovnakú tému, preto by som sa chcel spýtať, či by mi niekto nevedel poradiť vhodnú literatúru. Vyšlo niečo k stromovým dátam aj v češtine alebo slovenčine?, za odpoveď vopred ďakujem.....

xyzop:

zajímalo by mne jakym zpusobem lze presunot uzel. Pouziju li Př.
- kategorie 1
- kategorie 2
- kategorie 3
-- kategorie 3a
-- kategorie 3b - tady jsem
  -- kategorie 3b I
  -- kategorie 3b II
-- kategorie 3c
- kategorie 4
Pokud jsem postupoval dle(viz.vyse) http://php.vrana.cz/traverzovani-kolem-stromu….php#d-5377 tak lze presunout napr. "kategorie 3b II" do "kategorie 3a", ale pokud chci presunout "kategorie 3b II" do "kategorie 1", tak to uz nelze. Nevite nekdo jak na to?

ikona Jakub Vrána OpenID:

Viz http://php.vrana.cz/traverzovani-kolem-stromu-presuny-uzlu.php.

JB:

Udělal jsem si menu pro stránky. Poradil by mi někdo, jak bych měl něj přidat možnost rozbalení/sbalení její části? (id, nazev, poradi, parent, uroven, rozbalovaci). Daří se mi kategorii "rozbalit", ale když kliknu na druhou úroveň a níž, tak se mi strom zase zavře. Díky

VK:

Díky za článek. Teď už jen bojuji s algoritmem, který by celý strom namísto vypisování vrátil v podobě multidimenzionálního pole pro další zpracování. Neřešili jste někdo podobný problém? Díky předem.

MH:

Ahoj, chtěl jsem si upravit algoritmus pro přidání potomka uzlu tak, aby se potomek nepřidával na konec, jak je popsáno výše, ale na začátek. Mohl by prosím někdo potvrdit (autor článku nebo i někdo jiný), jestli jsem ten algoritmus upravil správně? díky moc

<?php
mysql_query
("START TRANSACTION");
$row = mysql_fetch_assoc(mysql_query("SELECT * FROM strom WHERE id = " . intval($_GET["rodic"]) . " FOR UPDATE"));
mysql_query("UPDATE strom SET lft = lft + 2 WHERE lft > $row[rgt]");
mysql_query("UPDATE strom SET rgt = rgt + 2 WHERE rgt >= $row[rgt]");

mysql_query("UPDATE strom SET lft = lft + 2, rgt = rgt + 2 WHERE lft > $row[lft] AND rgt < $row[rgt]");

mysql_query("INSERT INTO strom (lft, rgt, hloubka, nadpis) VALUES ($row[lft]+1, $row[lft]+2, $row[hloubka]+1, '" . mysql_real_escape_string($_POST["nadpis"]) . "')");
mysql_query("COMMIT");
?>

Mirek:

Děkuji Jakube za perfektní článek. Jsem sice v PHP oproti diskutujícím laik, ale dost jsem se díky traverzování přiučil.
Řeším však následující problém, s kterým si nevím rady.
Vytvářím menu, které je na způsob bar menu. Rád bych však při konkrétním výpisu např. kategorií v hloubce 3 přidal další (např. odkaz zpět), který by ukazoval na rodičovskou kategorii v hloubce 1, resp. potřebuji její ID. Pokud jsem v hloubce 4, potřebuji zjistit ID rodičovské kategorie v hloubce 2 apod.
Nějak se mi nedaří potřebný dotaz sesmolit.
Využívám klasické hodnoty id, název, hloubka, lft, rgt.

Díky za případnou pomoc

ikona Jakub Vrána OpenID:

lft < $lft AND rgt > $rgt AND hloubka = $hloubka - 2

Marek:

Zdravím,
akorát dělám web na kterém chci použít MPTT při ukládání stránek. V administraci chci stránky vypsat do tabulky a v tabulce mít odkazy pro posouvání stránek nahoru/dolů, ale pouze na stejné úrovni. Chci aby to vypadalo podobně jako v joomle př: http://www.packtpub.com/sites/default/files/…-image14.png. Dá se nějak v sql zjistit a přidat do výsledku jestli se jedná o první nebo poslední stránku v jednotlivých větvích? Nebo jak to jednoduše zkontrolovat, abych věděl jestli vypsat odkaz pro posunutí stránky nahoru nebo dolu (nebo oboji)?
PS: Píšu to v nette a v cyklu foreach porovnávám hodnotu předchozí (příp. následující) hloubky s aktuální a podle toho zjistím jestli vypsat odkaz pro posouvání nebo ne. Jenže u úplně první a úplně poslední položky mi to píše Notice Undefined offset, protože porovnávám položky které v resultsetu nejsou.
Tak jsem se chtěl zeptat jestli někdo nezná nějaké šikovnější řešení.

ikona Jakub Vrána OpenID:

Pokud se nepoužívá stránkování, tak bych to zjišťoval skutečně až při výpisu. Notice se dá jednoduše zbavit tím, že se nejprve podívám, jestli náhodou nejsem na první nebo poslední pozici.

Pokud by se stránkování používalo, tak by mi přišlo nejlepší si ke každému záznamu získat i jeho rodiče (lft < $lft AND rgt > $rgt AND depth = $depth - 1).

Jakub:

Zdravím, díky za názorné příklady, implementovat tuhle strukturu byla díky nim úplná hračka. ;)

Jediné co mi tu chybí je základní operace pro nějaké menu - tzn. výpis struktury ze zdola nahoru, přičemž každá vrstva ukazuje všechny položky, které nebyly rozkliknuty. á la windows průzkumník.
Jediné co mě napadá je použít funkci podobnou drobečkové navigaci s tím že v každé úrovni načtu všechny uzly dané větve, vždy ale musím zjistit lft a rgt rodičovského elementu a je to tedy strašne neefektivní. Kdyby někdo věděl jak to vyřešit elegantně byl bych vděčen ;)

Martin:

Tohle by se mi taky líbilo.

Holmistr:

Já řešil úplně stejný problém a nakonec jsem to vyřešil až na úrovni PHP, takže natáhnout vždy celý strom a pomocí cyklu a css display:none skrývat jednotlivé položky menu.

Udělal jsem to hlavně kvůli tomu, že ač některé menu není zobrazeno, mělo by být podle mě v kódu, aby vyhledávače mohly snadněji procházet.

Jeníček:

Zdravím, ty vypisuješ vždy celý strom? Nebude rychlejší tento zápis?

SELECT lft, id, rgt, level, name, round((rgt-lft)/2) sbcount
FROM `tree`
WHERE (`parent_id` IN (0, 193, 242, 459, 615, 876, 1183, 1811))
ORDER BY lft;

Jediné co mě štve, že je vždy v explain where, filesort.

Také mě napadlo nebylo by fajn používat: http://karwin.blogspot.com/2010/03/rendering-…-tables.html

Martin Lonský:

Na můj vkus je to příliš složité.. Principiálně lze strukturu stromu odrazit od Zend_Navigation a aby nebylo nutné načítat vždy celý strom, tak zaznamenávat i hloubku.

Martin Lonský:

O view už moc nejde, ale velice šikovná je ve Smartyfw rekurze

ikona Jakub Vrána OpenID:

Když chce člověk se stromem efektivně provádět rozličné operace, tak je tohle jedna z nejlepších struktur. Složitá mi nepřijde.

ikona Martin Lonský:

Podobně jsme to zpracovali pro MySQL, kde je možné to triggovat do event scheduleru hned po změně záznamů.

Jirka:

Používám úspěšně traverzování podle vzoru na svých webech.

V drobečkové navigaci umím zobrazit i kudy vede cesta. Mám ale jeden problém. Dokážu sice přesně zobrazit, kde se nacházím. ale jsem příliš hloupý, abych vymyslel, jak např. v menu ztučnit i předcházející položky. Tedy zanořím se např. do úrovně 3 - 1 - 2 a chci, aby nesvítila jen poslední aktivní, ale i 1 i 3

Díky za pomoc

ikona Jakub Vrána OpenID:

Ztučni ty, které mají menší LFT a větší RGT než aktivní.

Pavel:

Mohl by mi někdo poradi jak tento kod upravit tak, aby se mi nově založené příspěvky řadily na začátek výpisu. V současné době se mi nově založený příspěvek zobrazí až na konci výpisu z databáze.
Strom vypisuji pomocí
<?

$result
= mysql_query("SELECT * FROM strom ORDER BY lft");
?>

Pavel:

na mysli mám samozřejmě rodičovské příspěvky

ikona Jakub Vrána OpenID:

lft bude 1, rgt 2, ale je potřeba posunout všechny další prvky. Takže nejdřív bych udělal UPDATE strom SET lft = lft + 2, rgt = rgt + 2, a pak INSERT INTO strom (lft, rgt) VALUES (1, 2).

ikona Zemistr:

Nedávno jsem učil bratra rekurzivní funkce.
Z naší konverzace vzniklo toto.
Snad to někomu pomůže, nebo si aspoň vyslechnu zaslouženou kritiku. :)

SQL: http://pastebin.com/BJEvSHjf
PHP: http://pastebin.com/4XZqyh70

Stručně řečeno:
1) přes JEDEN SQL dotaz si získáme celou strukturu menu
2) výsledek uložíme do array, kde vše seskupíme podle parent_id
2 - info) výsledný array má tuto podobu: http://pastebin.com/26evRKeW
3) výsledný array se pošle do funkce která z něho vytvoří výsledné menu

ikona Jakub Vrána OpenID:

Tato struktura vyžaduje načtení celého stromu (nebo opakované kladení dotazů) i při vypsání drobečkové navigace nebo části stromu, takže je nevhodná při větším množství položek nebo větším zanoření.

duskohu:

Zdravím, nevedel by mi niekto poradiť ako z výstupu vygenerovať viacrozmerné pole?

ikona Martin Lonský:

Traverzování na úrovni MySQL. MySQL má své limity a omlouvám se za ofsset. LOCAL CURSOR tu bohužel nie je.

https://github.com/visitek/mysql_traversable_tree

David:

Ahoj, zajímalo by mě jak řešit uložení více stromů v jedné databázové tabulce. Pokud by měl každý strom své vlastní ohodnocení (left, right). Znamenalo by to přidat restrikci do všech dotazů, které updatují left a right. Druhá možnost, co mě napadá, je vložit si jeden "umělý" prvek, tzn. kořen. Prakticky: mějme strom kategorie e-shopu, na první úrovni budou třeba 1. televize, 2. notebooky, 3. mobily,...Myslíte, že je dobré řešení vytvořit 1 záznam = kořen, abychom dosáhli toho, že se bude jednat o jeden strom?

ikona Jakub Vrána OpenID:

Ano, udělal bych jeden strom.

Diskuse je zrušena z důvodu spamu.

avatar © 2005-2024 Jakub Vrána. Publikované texty můžete přetiskovat pouze se svolením autora. Ukázky kódu smíte používat s uvedením autora a URL tohoto webu bez dalších omezení Creative Commons. Můžeme si tykat. Skripty předpokládají nastavení: magic_quotes_gpc=Off, magic_quotes_runtime=Off, error_reporting=E_ALL & ~E_NOTICE a očekávají předchozí zavolání mysql_set_charset. Skripty by měly být funkční v PHP >= 4.3 a PHP >= 5.0.