Ukládáme hierarchická data v databázi – I

Ať už chcete vytvořit vlastní fórum, publikovat zprávy z mailing listů nebo vytvářet vlastní cms, budou případy, kdy budete chtít ukládat hierarchická data do databáze. A pokud nepoužíváte databázi na principu XML, tabulky nebudou hierarchické – jsou jen plochým seznamem. Proto budeme muset najít způsob, jak přeložit hierarchii do plochého souboru.

Seriál: Ukládáme hierarchická data v databázi (3 díly)

  1. Ukládáme hierarchická data v databázi – I 5.3.2012
  2. Ukládáme hierarchická data v databázi – II 14.3.2012
  3. Ukládáme hierarchická data v databázi – III 19.3.2012

Tento článek je volným překladem anglického originálu, vydaného na portálu SitePoint.

Pozn. překladatele: První část mini-seriálu pojednává o ukládání dat do databáze pomocí parametru „parent“. Osobně si myslím, že nepotřebuje příliš představovat – naopak předpokládám, že drtivá většina čtenářů tento způsob již používá. Zároveň jsem ale zastáncem, že používání pouze této metody (zejména pokud ji máte ve svém überCMSTM) je nesmysl. Pro bilancování neváhejte přeskočit přímo na konec článku. Základním smyslem prvního dílu tedy je se ujistit, že všichni mluvíme o jednom a tom samém – a plynule navázat v druhém dílu seriálu.

Ukládání stromů je obecný problém s několika způsoby řešení. Existují dva hlavní přístupy: adjacency list (rekurzivně procházený seznam) a MPTT – metoda, kterou budeme přezdívat jako „traverzování stromu“.

V tomto mini-seriálu se podíváme na oba způsoby ukládání dat. Pro demonstraci použiji strom z fiktivního e-shopu s jídlem. V e-shopu organizujeme jídlo podle kategorie, barvy a typu. Strom vypadá následovně:

Tento článek obsahuje několik příkladů kódu, který ukazuje jak ukládat a získávat data. Protože ten jazyk používám také, a mnoho lidí ho používá nebo ho alespoň zná, rozhodl jsem se příklady napsat v PHP. Pravděpodobně budete schopni příklady přepsat do dalších jazyků bez větších problémů.

Pozn. překladatele: vzhledem k tomu, jaké příklady jsou u původního článku použity (styl php 4), pro seriál na zdrojáku jsem příklady aktualizoval. Věřím, že budou jednodušší na pochopení než příklady použité v originálním článku. Rovněž jsme pro příklady použil databázovou knihovnu dibi, která je v českých končinách myslím dostatečně známá a je více samo-vysvětlující než při použití MySQLi (nehledě na fakt, že skutečně nemám rád používání  global)

Rekurzivně procházený seznam

První, a nejelegantnější přístup, který si vyzkoušíme, se jmenuje „Adjacency list model“ nebo „Rekurzivní metoda“. Je to elegantní přístup, protože budete potřebovat jenom jednu jednoduchou metodu, která bude procházet váš strom. V našem obchodě s jídlem, tabulka seznamu vypadá následovně:

ID PARENT TITLE
1 NULL Jídlo
2 1 Ovoce
3 2 Červené
4 2 Žluté
5 3 Třešeň
6 4 Banán
7 1 Maso
8 7 Hovězí
9 7 Kuřecí

(příslušný .sql soubor je v příkladech jako „rekurze.sql“)

Jak můžete vidět, v rekurzivní metodě si ukládáme „parent“ („rodič“ v překladu) každé položky. Můžeme vidět, že Banán je potomek položky Žluté, což je potomek položky Ovoce a tak dále. Nejvyšší bod stromu nemá hodnotu rodiče (parent je NULL.)

Dej mi strom

Když jsme si vytvořili databázi, je čas na vytvoření funkce, která bude položky zobrazovat. Taková funkce musí začít u vrchní položky seznamu – tedy položky která nemá uvedeného otce (parent), a získat si všechny potomky dané položky. Pro každého potomka funkce musí získat daného potomka a zobrazit jeho děti – a tak až do aleluja.

Jak jste si mohli všimnout v popisu funkce, tato funkce je rekurzivní. Můžeme tedy napsat jednu funkci, která vrátí pouze potomky daného ID a zavolá sama sebe na všechny získané položky. A proto se této metodě říká „rekurzivní metoda“.

function display_tree($id = null) {
    // Získáme děti daného ID - akorát nesmíme zapomenout na možnost,
    // že je $id NULL - v takovém případě potřebujeme jinou klauzuli WHERE
    $query = dibi::select('*')->from('tree');
    if($id === null) {
        $query->where('[parent] IS NULL');
    }
    else {
        $query->where('[parent] = %i', $id);
    }
    $nodes = $query->fetchAll();

    // Zobrazíme výsledky stromu jako seznam
    echo '<ul>';
    foreach($nodes as $one) {
        echo '<li>' . $one['title'];

        // Zobrazíme děti dané položky - způsobí vygenerování samostatného <ul>
        // v rámci našeho <li> tagu
        display_tree($one['id']);

        echo '</li>';
    }
    echo '</ul>';
}

(ukázku je možné najít v příkladech jako index.php)

Abychom se podívali na výsledek této funkce, stačí, když ji zavoláme bez jakéhokoliv parametru. Měli bychom poté vidět něco podobného následujícímu:

Nezapomínejme, že pokud chceme vidět jenom část stromu, pak můžeme funkci zavolat s příslušným parametrem ID – například když zavoláme display_tree(2); , pak uvidíme pouze veškeré potomky položky ovoce.

Cesta k uzlu (node)

Se skoro stejnou metodou se můžeme dostat k seznamu položek „otců“ – stačí nám vědět id daného uzlu. Toto je mnohdy využívané v drobečkové navigaci – představme si, že potřebujeme získat navigaci ze stránky detailu daného produktu (u nás banán a třešeň). V takovém případě pro změnu musí funkce začít v nejspodnější části a postupně se propracovat k nejvyššímu uzlu. V našem příkladě zavoláme funkci na třešeň a funkce by nám měla vrátit pole jejích rodičů:

function get_path($id) {
    $return = array();
    $parent = false;

    // Cyklus, který prochází strom dokud existuje rodič, dibi automaticky
    // vrátí FALSE ve chvíli, kdy rodiče nenalezne
    do {
        $parent = dibi::fetch('SELECT * FROM [tree] WHERE [id] = %i', $id);
        if($parent != false) {
            $return[] = $parent;
            $id = $parent['parent']; // předáme hodnotu další iteraci cyklu
        }
    } while($parent);

    // Odstraníme z výsledku první hodnotu, což je položka, pro kterou chceme strom
    array_shift($return);

    return $return;
}

Abychom si funkci vyzkoušeli, pak zavoláme jednoduše var_dump(get_pat­h(5)); – a dostaneme zpět pole stromu pro třešeň:

Bilancujeme (pozn. překl.)

Na rozdíl od autora původního článku se neztotožňuji s tím, že je to „velmi dobrá“ metoda. Navíc si nemyslím, že potřebuje příliš mnoho představování – ale pro zachování kontinuity celého miniseriálu bylo nutné ji zlehka nakousnout, abychom si byli jisti, že všichni mluvíme o jednom a tom samém. Navíc – metodika ukládání stromu pomocí položky parent je, troufám si říct, velmi rozšířená. Není na ní nic složitého, je velmi jednoduchá na pochopení, každý ji zvládne vymyslet prakticky na koleně a nakonec jsem ji i já sám dobrých 7 let používal.

Její velkou nevýhodu ale vidím především ve výkonu, resp. náročnosti na server. Při představě, že máme strom o desetitisících položek, jako je tomu na e-shopech typu alza.cz, kasa.cz a podobných, pak skutečně v kombinaci s jejich statistikou návštěvnosti není dobré tento způsob ukládání stromů používat.

Nevýhody jsou přitom jasné: pro získání všech potomků musím použít rekurzi (a nebo ji obcházet), ale hlavně – pro každou úroveň, resp. každou položku, musím spustit jeden SQL dotaz. Metoda MPTT, která je představena v dalším díle, přitom těmito neduhy netrpí – tedy alespoň na nejvíce zatěžované části, čímž je prezentační logika směrem k návštěvníkům. A k tomu, na co si dát u MPTT pozor, se dostaneme v závěrečném díle seriálu.

Přílohy

Příklad ke stažení

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Komentáře: 23

Přehled komentářů

Marek Hĺbka stromu
HerBeer Záleží také na DB
Ivan Re: Záleží také na DB
Petr Re: Záleží také na DB
logik Re: Záleží také na DB
Michal Kočárek Popis MPTT pro nedočkavce
František Kučera Re: Popis MPTT pro nedočkavce
Tomáš Fejfar Re: Popis MPTT pro nedočkavce
František Kučera Re: Popis MPTT pro nedočkavce
Pavel Ptáček Re: Popis MPTT pro nedočkavce
František Kučera migrace/importy vs. běžný provoz
libor Re: migrace/importy vs. běžný provoz
Pavel Ptáček Re: Popis MPTT pro nedočkavce
Oldis Re: Popis MPTT pro nedočkavce
Pavel Ptáček Re: Popis MPTT pro nedočkavce
Oldis Re: Popis MPTT pro nedočkavce
PCHe mimozni pristup
Mennion Re: mimozni pristup
Pavel Ptáček Re: mimozni pristup
Mennion Re: mimozni pristup
JanVoracek Closure Table – trochu jiný pohled na stromy
Jakub Vrána Počet komunikací s databází může být jen L+1
Radim Bača reprezentace stromu
Zdroj: http://www.zdrojak.cz/?p=3613