Komentáře k článku

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.

Zpět na článek

23 komentářů k článku Ukládáme hierarchická data v databázi – I:

  1. Marek

    Hĺbka stromu

    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á.

  2. HerBeer

    Záleží také na DB

    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;

        1. logik

          Re: Záleží také na DB

          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.

    1. František Kučera

      Re: Popis MPTT pro nedočkavce

      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)

        1. František Kučera

          Re: Popis MPTT pro nedočkavce

          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.

          1. Pavel PtáčekAutor příspěvku

            Re: Popis MPTT pro nedočkavce

            Na tohle si prosím dejte velký, velký pozor. V CMS jsme si prapůvodně MPTT implementovali tak, že to „neobtěžovalo programátora“ — tedy bylo MPTT transparentně v modelech. Implementace přímo do databáze (což jsem svého času také na postgres měl) je ještě horší řešení.

            Představte si takový mass import a aktualizaci lft & rtg při každém jednotlivém insertu mass importu produktů… Databáze a sysadminé vás budou nesnášet, i když to hodíte do transakce.

            Ale o tom až ve třetím díle :)

            1. František Kučera

              migrace/importy vs. běžný provoz

              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.

              1. libor

                Re: migrace/importy vs. běžný provoz

                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.

    2. Pavel PtáčekAutor příspěvku

      Re: Popis MPTT pro nedočkavce

      tak tak.. a ve třetím díle budou mé osobní zkušenosti z implementací nad 1.000.000+ položkami :-)

      1. Oldis

        Re: Popis MPTT pro nedočkavce

        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.

        1. Pavel PtáčekAutor příspěvku

          Re: Popis MPTT pro nedočkavce

          Ano, až ve třetí.. Každopádně bych doporučil z databáze tahat jen data, která potřebujete. Skládat dohromady masivní (100.000+) strom je nesmyslně náročné na pamět serveru – i když budou (jsou?) zdrojáky, které mptt flat-tree přestaví do hierarchické struktury bez rekurze (bude/je součástí příkladů a ano, jsem na to hodně pyšný :-))

          1. Oldis

            Re: Popis MPTT pro nedočkavce

            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.

  3. PCHe

    mimozni pristup

    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

    1. Mennion

      Re: mimozni pristup

      „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.

      1. Pavel PtáčekAutor příspěvku

        Re: mimozni pristup

        Pokud potřebuji zobrazit _celý_ strom, pak je n+1 samozřejmě špatně. Pro zjednodušení jsem to v článku neřešil.
        mnohdy ale nepotřebujeme tahat celý strom na to, abychom ho v php postavili zase zpátky.

        Nehledě na to, že rekurze jde velmi jednoduše obejít v 90% případů, bufferem a pointery.

        Select n+1 jsem už mnohokrát viděl – nicméně to byly stromové struktury 1-3 level deep. Ve chvíli, kdy budu řešit např. alzu, pak bych si osobně udělal mptt – už jen kvůli výkonu rekurzivních selectů / náročnosti na dtb. SELECT PLAIN SIMPLE je prostě rychlejší.

        Nebo není?

        1. Mennion

          Re: mimozni pristup

          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.

  4. Jakub Vrána

    Počet komunikací s databází může být jen L+1

    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}
  5. Radim Bača

    reprezentace stromu

    Ř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.

Napsat komentář

Tato diskuse je již příliš stará, pravděpodobně již vám nikdo neodpoví. Pokud se chcete na něco zeptat, použijte diskusní server Devel.cz

Zdroj: https://www.zdrojak.cz/?p=3613