Přejít k navigační liště

Zdroják » Databáze » Ukládáme hierarchická data v databázi – I

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

Články Databáze

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.

Nálepky:

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í

Komentáře

Subscribe
Upozornit na
guest
23 Komentářů
Nejstarší
Nejnovější Most Voted
Inline Feedbacks
View all comments
Marek

V článku mi chýba jedno tvrdenie. Efektivita tohto algoritmu závisí od hĺbky stromu. Vyplýva to síce z textu, ale nie je to tam jasne povedané.

Pokiaľ je hĺbka stromu 2-3 a vieme, že to nikdy nebude inak napr. regióny (kraj, okres), potom je daný algoritmus dostatočne efektívny a netreba hľadať iné riešenia. Samozrejme pri väčšej hĺbke stromu efektivita klesá.

HerBeer

Zaleží nad jakou databází.
Oracle umí vytáhnout strom jediným SQL dotazem.
Tam je datová reprezentace zmiňovaná v článku ideální.

select lpad(‚ ‚,2*(level-1)) || to_char(child) s
from my_table
start with parent is null
connect by prior child = parent;

Ivan

Presne tak:
http://en.wikipedia.org/wiki/Hierarchical_query

BTW connect_by je (velmi stare) rozsireni Oracle. Pokud se nepletu tak SQL99 to resi pomoci CTE(WITH clause).

Petr
logik

To ale nic nemění na tom, že se to vnitřně provede jako těch X dotazů. Sice odpadne režie s posíláním dotazů sem a tam (to by šlo ale odstranit i použitím stored procedure), ale databáze nijak nemůže vědět, že takto přečte celou tabulku a tak to ani v optimalizacích nijak nezohlední.

Pokud např. v postgresql použijete left jako clustered index, tak CTE dotaz (v další kapitole) bude defakto sekvenční čtení – to s touto metodou nikdy nezískáte.

Michal Kočárek

Nedočkavcům doporučuji http://www.sitepoint.com/hierarchical-data-database-2/ , kde následuje popis MPTT metody.

A jen poznamenám, že naživo se můžeme s „lft“ a „rgt“ setkat v Joomle, která tímto způsobem implementuje hierarchii kategorií (tabulka #__categories).

František Kučera

Drupal zase ukládá cestu jako řetězec* a je tam redundantní informace (ale bez ní se strom komentářů správně nevykreslí). Pracovat s takovou databází jinak než přes Drupal je pak peklo.

Když už se nějaká takováhle forma „ručních indexů“ musí používat (kvůli výkonu), tak ať je to alespoň jako databázová procedura a starají se o to triggery.

*) ještě v takovém dementním kódování 01.00.00.00.01­.01.01.00.00/ (vancode)

Tomáš Fejfar

Tomu se říká genealogické stromy. Má to výhody i nevýhody – jako všechny postupy. Více viz http://www.root.cz/clanky/stromy/

František Kučera

Hloupé na tom je např. to, že při přidávání nového uzlu musím najít posledního sourozence*. O přesazování částí stromu ani nemluvě.

Nicméně co jsem se hlavně snažil říct: že by se tahle funkcionalita měla implementovat na úrovni databáze a pro aplikaci (resp. aplikace, protože těch může být víc) by to mělo být transparentní (normální ISERTy, UPDATy, aniž bych musel řešit tyhle dodatečné stromové „indexy“) a mělo by to poskytovat lepší výkon, nikoli obtěžovat programátora.

*) což by nebylo nutné, kdyby cesta nebyla zapsána jako 01.01.00.01 (pořadí potomka), ale jako id.id.id, kde id by bylo id uzlu (které tudíž nemusím dopočítávat inkrementací pořadí posledního sourozence). Také by to šlo zapsat jako pole místo jako textový řetězec.

František Kučera

Při hromadných importech nebo migracích je celkem běžné vypnout věci jako triggery, indexy, integritní omezení… a nahodit je až poté. Resp. to, zda se budou tyhle věci dělat individuálně pro každý záznam (jako při běžném provozu) nebo nějak hromadně, to je normální součást migrační/impor­tovací procedury. Není to ale důvod k tomu, aby při běžném provozu musela tyhle věci řešit aplikace.

libor

Nemusí se jednat pouze o import/migraci, ale např. přesun podstromu do jiné části podstromu v aplikaci.
Navíc pokud mi databáze zpřehází pomocné indexy (lft a rgt) aniž by to aplikace věděla, pak pokud mám položky celého stromu nacachované včetně lft a rgt pro rychlé hledání v podstromu, musím vždy po updatu stromu invalidovat celou jeho cache.

Oldis

Az ve treti? Zrovna zvazuju moznost, tahat celej strom, ikdyz potrebuju jen cast, jednim dotazem a slozit ho v php, a premyslim do jakeho poctu polozek to je schudne reseni.

Oldis

Tak samozrejme v prvni fazi pisu rekurzi, je to rychle a pohodlne a posleze ji prepisuji do plocheho cyklu. Pysnej sem na to byl tak pred deseti lety. u 100k+ je to samozrejme nesmysl. Pak mne napada, ze by u mensich stromu nebylo od veci, serializovat objekt(strom) a ten si ulozit.

PCHe

mel bych k tomu cca nasledujici:
– pro kazdy lvl stromu poustet sql prikaz je archetypalne spatne. a nezavisi to na predstavenem algoritmu. ale hrube spatnem naprogramovani. To mi predvest programator na pohovoru, tak si jde hladat praci nekde jinde.
– co se alzy tyce – tusim jedou na mssql serveru – tam je to mozne napsat jedinym dotazem. Oracle ma rekurzivni dotazy.
– chybi mi tu porovnani – jestli je lepsi mit odkaz na otce v jedne tabulce nebo v separatni tabulce a proc

Mennion

„pro kazdy lvl stromu poustet sql prikaz je archetypalne spatne. a nezavisi to na predstavenem algoritmu. ale hrube spatnem naprogramovani“

Jo jo to mě při čtení toho článku napadlo taky, že se programátor snadno s tímhle přístupem dostane do selet n + 1 stavu.

Pokud strom nebude extra hluboký, tak imho vyjde líp, si celý ten strom načíst v jednom dotazu a nad ním provádět rekurzi.

Mennion

Na to řešení např. Alzy mám stejný názor. Tam už je každý průchod stromem znát.

Na Select n+1 člověk nejčastěji narazí, pokud používá nějaký ten ORM a asi nemá u menších projektů smysl se tím nějak zabývat.

Ano, select plain simple by měl být rychlejší, než rekurzivní selecty na db, i přes to že můžou být kešované a uložené v nějakém pohledu nebo volané přes storku.

JanVoracek

Zhruba před měsícem jsem psal článek o alternativním přístupu ke stromům v MySQL s názvem Closure Table – http://blog.voracek.net/databaze/closure-table-stromy-v-mysql-trochu-jinak/

Má nějaké sice nějaké mouchy (aktuálně narážím na problém s řazením), ale myslím si, že je to zajímavý přístup ;)

Jakub Vrána

Ukládání rodiče také nemám zrovna v lásce, kromě horší složitosti taky nedovoluje na rozdíl od ostatních přístupů uložit pořadí prvku ve stromu.

N+1 komunikací s databází (kde N je počet zobrazených záznamů) se nicméně dá při použití odloženého pokládání dotazů zredukovat na L+1, kde L je hloubka zobrazeného stromu. A s Nette 2 a NotORM 2 se dá zapsat i velmi jednoduše:

{block #categories}
  {with $db->category('parent_id', $parent) as $categories}
    <ul n:if="count($categories)">
      <li n:foreach="$categories as $category">
        {$category['title']}
        {include #this, parent => $category}
      </li>
    </ul>
  {/with}
{/block}
Radim Bača

Řešit uložení stromu bez specifikace podporovaných operací je jako by jste řešili jaký je nejlepší dům bez určení toho k čemu bude sloužit (kanceláře asi budou mít jiné preference než rodinný dům). Bude velký rozdíl v tom, když budeme chtít podporovat operace typu descendant, nebo jen půchod stromem na základě vztahu přímý předek potomek. Podstatná otázka také je jaké máme priority co se týče vkládání do stromu a měnění celkové struktury stromu.

Enum a statická analýza kódu

Mám jednu univerzální radu pro začínající programátorty. V učení sice neexistují rychlé zkratky, ovšem tuhle radu můžete snadno začít používat a zrychlit tak tempo učení. Tou tajemnou ingrediencí je statická analýza kódu. Ukážeme si to na příkladu enum.