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

V minulém díle miniseriálu jsme si osvěžili klasickou metodu ukládání stromů do databáze tak, jak ji každý z nás zná. Dnes se podíváme na tzv. MPTT – traverzování kolem stromu. Rovnou se podíváme i na reálnou implementaci tak, jak ji můžete použít ve svých projektech.

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.

Podívejme se dnes na druhou metodu ukládání stromů. Rekurze může být pomalá, takže ji nechceme použít. Také bychom rádi minimalizovali počet dotazů na databázi – ideálně tak, aby pro jednu aktivitu existoval jeden dotaz.

Začneme tím, že si strom překreslíme do jiné podoby – jako kdybychom ho kreslili na papír. Začneme u hlavního uzlu („Jídlo“) a napíšeme 1 na jeho levou stranu. Budeme pokračovat na prvního potomka a napíšeme 2 vedle něj. Touto cestou „jdeme kolem stromu“ (pozn. překl: v angličtině traverse – v překladu „překračovat“, proto pro tento typ používám název „traverzování kolem stromu“.) Při procházení stromu píšeme čísla nejdříve na levou stranu a vždy, když jsme na nejspodnější části, přecházíme na pravou stranu – poslední číslo je napsané na pravou stranu uzlu „jídlo“. Níže můžete vidět obrázek s celým očíslovaným stromem:

Nazveme tahle čísla jako „left“ a „right“ (levá a pravá). Jak můžete vidět, tahle čísla indikují vztah mezi každým uzlem stromu. Protože „červené“ má čísla 3 a 6, je potokem uzlu Jídlo, který má čísla 1–18. Stejně tak můžeme říct, že všechny uzly s levým číslem větším než 2, které mají pravé číslo menší než 11, jsou potomkem uzlu 2–11 „Ovoce“. Díky tomu můžeme zjednodušit dotazy na databázi a tento způsob se jmenuje „Modified preorder tree traversal“, tedy MPTT.

Pozn. překl.: jak bude uvedeno níže v článku, nejsem zastáncem ani jednoho ze způsobů – mám rád jejich kombinaci s doplněním parametru „level“ – tedy úrovně ve stromu. Všechny příklady v tomto a dalším díle budou vycházet z tohoto předpokladu, ačkoli pro funkci samotného MPTT stačí udržovat pouze údaje left a right.

Podívejme se tedy, jak bude vypadat naše databáze:

id parent left right level title 1 1 18 1 Jídlo 2 1 2 11 2 Ovoce 3 2 3 6 3 Červené 4 2 7 10 3 Žluté 5 3 4 5 4 Třešeň 6 4 8 9 4 Banán 7 1 12 17 2 Maso 8 7 13 14 3 Hovězí 9 7 15 16 3 Kuřecí

(strukturu databáze lze nalézt v příkladech v souboru mptt.sql)

Nezapomínejme, že „left“ a „right“ mají speciální význam v SQL. Proto nesmíme zapomínat na escape sekvenci MySQL – v dibi (a tím pádem i příkladech) ji ale používáme stejně, znaky [ a ].

Získáme strom

Pokud chceme získat celý strom, pak můžeme klasicky rekurzivně postupovat pomocí parametru parent. Díky MPTT nám ale k tomu bude stačit jeden SQL příkaz, který nám získá pouze položky, které mají parametr left mezi 2 a 11, tedy:

SELECT * FROM `mptt` WHERE `left` BETWEEN 2 AND 11;

Což vrátí:

id parent left right level title 2 1 2 11 2 Ovoce 3 2 3 6 3 Červené 4 2 7 10 3 Žluté 5 3 4 5 4 Třešeň 6 4 8 9 4 Banán

No, a tady to máme – celý strom v jednom dotazu. Nicméně abychom zobrazili strom, stejně jako jsme to udělali v naší rekurzivní funkci, budeme muset přidat klauzuli ORDER BY – použijeme parametr left, který nám k tomuto účelu perfektně postačí:

SELECT * FROM `mptt` WHERE `left` BETWEEN 2 AND 11 ORDER BY `left`;

Jediný problém je otevírání a uzavírání tagů <ul> – a k tomu se nám právě perfektně hodí parametr level. Pozn. překl: rovněž lze použít sekvenční zobrazování s tím, že si udržujeme frontu pravých hodnot. K účelům, které používá autor původního článku, to bohatě stačí – nicméně zastávám názor, že každý programátor, který k MPTT přijde, by ho měl umět používat více méně automaticky s trochou logiky a přemýšlení. Výsledkem je, že jsme v našich implementacích začali používat parametr level, čistě proto, že je pak vše jasnější.

function display_tree($id = null) {
    // Nejdříve si získáme uzel, pro který chceme zobrazit děti. Pokud je ID
    // NULL, pak chceme získat celý strom od "shora"
    $query = dibi::select('*')->from('mptt');
    if($id === null) {
        $query->where('[parent] IS NULL');
    }
    else {
        $query->where('[id] = %i', $id);
    }
    $root = $query->fetch();
    if(!$root) {
        return;
    }

    // A teď si získáme všechny potomky
    $children = dibi::fetchAll('SELECT * FROM [mptt] WHERE [left] BETWEEN %i AND %i ORDER BY [left]', $root['left'], $root['right']);

    // Pro ne-rekurzivní zobrazení si budeme udržovat aktuální "level"

    $level = -1;

    // A postupně zobrazíme děti
    foreach($children as $one) {
        // Ukončíme otevřené <ul> a <li> tagy
        if($one['level'] < $level) {
            $dismiss = $level - $one['level'];
            for($i = 0; $i < $dismiss; ++$i) {
                echo '</li></ul>';
            }
        }

        // Ukončujeme aktuální <li>?
        if($one['level'] == $level) {
            echo '</li>';
        }

        // Máme zobrazit tag <ul>?
        if($one['level'] > $level) {
            echo '<ul>';
        }

        echo '<li>' . $one['title'];
        $level = $one['level'];
    }

    // A nesmíme zaponemout uzavřít všechny otevřené tagy
    for($i = $level+1; $i >= $root['level']; --$i) {
        echo '</li></ul>';
    }
}

Po jejím spuštění bychom měli vidět něco podobného následujícímu:

Cesta k uzlu

S algoritmem MPTT můžeme také jedním dotazem získat drobečkovou navigaci (cestu) k danému uzlu stromu. Pomocí left a right to není ani raketová věda: například, pokud chceme získat cestu k třešni, můžete se podívat, že všechny rodiče mají levé id menší než 4 a zároveň pravé id větší než 5. Použijeme tedy následující dotaz:¨

SELECT * FROM `mptt` WHERE `left` < 4 AND `right` > 5 ORDER BY `level` ASC;

Dotaz nám vrátí následující výsledek:

id parent left right level title 3 2 3 6 3 Červené 2 1 2 11 2 Ovoce 1 1 18 1 Jídlo

Pozn. překl.: Pro jednoduchost opět používáme atribut level, nicméně stejné funkčnosti lze dosáhnout i s použitím třídění podle parametru  left.

Kolik je položek v kategorii

Pokud bychom potřebovali získat počet potomků, pak nám stačí jednoduchá aritmetika mezi left a right parametrem: prostě je od sebe odečteme, a vydělíme 2. Každý uzel stromu totiž přičte k celkovému počtu 2. Stačí nám tedy následující rovnice:

$count = ($node['right'] - $node['left'] - 1) / 2;

Přepočítáváme strom

Jednou za čas, například ve chvíli, kdy se rozhodnete MPTT implementovat do vašeho již běžícího projektu, potřebujeme funkci, která vezme nejvyšší uzel stromu a přepočítá všechny dílčí uzly. A zde se právě dostáváme k tomu, proč jsem v příkladech nechal parametr parent:

function rebuildTree() {
    $root = dibi::fetch('SELECT * FROM [mptt] WHERE [parent] IS NULL');
    if (!$root) {
        return;
    }

    // Pošleme parametr $left jako 1, tedy první položku stromu
    _rebuildTreeWorker($root, 1);
}

/**
* Actually rebuild the tree
*/
function _rebuildTreeWorker($parent, $left, $level = NULL, $output = false)
{
    $right = $left + 1;

    if ($level === NULL) {
        $level = (int)$parent['level'];
    }

    $children = dibi::fetchAll('SELECT * FROM [mptt] WHERE [parent] = %i', $parent['id']);

    foreach ($children as $row) {
        $right = _rebuildTreeWorker($row, $right, $level + 1, $output);
    }

    $update = array(
        'left'  => $left,
        'right' => $right,
        'level' => $level,
    );

    dibi::update('mptt', $update)->where('[id] = %i', $parent['id'])->execute();

    return $right + 1;
}

Ano, toto je rekurzivní funkce – ve skutečnosti používáme dvě. První si najde nejvyšší bod uzlu a spustí na něj funkci, která fyzicky prochází stromem. Ta si vždy najde veškeré děti a vrátí novou pravou hodnotu. Nakonec ji nastaví i u rodičovské­ho uzlu.

Pokud nejsou žádné položky ve stromu, kromě té nejvyšší, nastaví rodičovskému uzlu 1 a jako pravou hodnu +1, tedy 2.

Díky rekurzi se funkce tváří složitější než vypadá – ve skutečnosti ale dělá přesně to, co jsme na začátku udělali ručně na papíře. Prochází kolem stromu a přidává 1 ke každému uzlu, který uvidí. Vyzkoušejte a uvidíte, že ve skutečnosti všechna čísla i po jejím spuštění zůstala stejná. Rychlá kontrola – hodnota right by měla být dvojnásobkem počtu uzlů.

Přidávání položek do stromu

Jak automatizujeme přidávání položek do stromu? Jsou dva přístupy: můžeme prostě přidat položku do stromu a celý strom následně přepočítat pomocí funkce rebuildTree() – jednoduché, ale ne příliš elegantní řešení; nebo můžeme aktualizovat levé a pravé hodnoty na všech uzlech, které jsou napravo od uzlu, který přidáváme.

První volba je jednoduchá, ale ne příliš efektivní s velkými stromy: prostě přidáte nový uzel, který bude mít správný parametr parent a ostatní (left, right, level) necháte nastavené na 0. Poté přepočítáte strom a vše je v pořádku.

Druhá cesta k přidávání a odebírání uzlů je nejdříve přepočítat všechny položky napravo od uzlu. Udělejme si příklad, kdy chceme přidat nový uzel „Jahoda“ pod červené ovoce. Nejdříve budeme muset udělat místo: pravá hodnota „Červené“ musí být změněna z 6 na 8, uzel 7–10 by měl být 9–12 atp. Aktualizace uzlu „Červené“ znamená, že budeme přidávat hodnotu 2 pro všechny uzly, kde je hodnota větší než 5.

UPDATE `mptt` SET `right` = `right` + 2 WHERE `right` > 5;
UPDATE `mptt` SET `left`  = `left`  + 2 WHERE `left`  > 5;

Teď můžeme přidat novou položku do uzlu. Tento bod musí mít hodnoty 6 a 7:

INSERT INTO `mptt` (`parent`, `left`, `right`, `level`, `title`) VALUES ('3', '6', '7', '4', 'Jahoda');

Teď spustíme funkci displayTree() a podíváme se, zda se uzel přidal správně:

Pokud chceme položku smazat, pak použijeme stejný přístup jako když ji přidáváme – jen v update místo přičítání použijeme znaménko -.

Nevýhody

Napoprvé může MPTT vypadat složitě. Je skutečně složitější než klasická metoda s ukládáním pouze pomocí parent. Nicméně, jakmile si zvyknete na hodnoty left a right velmi rychle poznáte, že s tímto modelem můžete dělat vše co s klasickou metodou – s tím, že tato metoda je mnohem rychlejší. Aktualizace stromu se skládá z více SQL dotazů, což je pomalejší, ale získávání stromu je mnohem rychlejší díky použití pouze jednoho dotazu a cyklu bez rekurze.

Příští díl

V příštím díle si ukážeme, jak jsme celé MPTT implementovali ve společnosti WDF před třemi lety. V rámci WDF se tyto stromy používají dodnes, i když prošli pár úpravami. Narazili jsme totiž na implementační chyby, tak na další aspekty MPTT, které vylezou na povrch až když máte 500 000+ položek v jednom stromu. Nicméně na to, jak jsme si s nimi poradili, si ještě chvilku počkejte.

Další čtení v angličtině

More on Trees in SQL by database wizard Joe Celko: http://searchda­tabase.techtar­get.com/…7290,0­0.html

Two other ways to handle hierarchical data: http://www.evol­t.org/…7/index­.html

Xindice, the ‘native XML database’: http://xml.apache­.org/xindice/

An explanation of recursion: http://www.strat­h.ac.uk/…on3_9_5­.html

Komentáře: 13

Přehled komentářů

Flaiming Jiný způsob
Eda Formátování článku
Pepca Nested Intervals
Tomáš Fejfar Re: Nested Intervals
Dingo Re: Nested Intervals
Radim Bača uložení stromu
František Kučera Re: uložení stromu
Oldis Re: uložení stromu
Dingo MPTT
dingo Re: MPTT
Oldis Učel
P Nested Set
plynař úprava
Zdroj: https://www.zdrojak.cz/?p=3615