Komentáře k článku
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.
Jiný způsob
Zdravím,
tento systém mi přijde poněkud zbytečně komplikovaný...Osobně to u svého systému řeším trochu jednodušeji. Mám v jedné tabulce uloženy záznamy s jejich pořadím a hloubkou vzhledem ke kořeni. V druhé tabulce je ID záznamu, ID jeho rodiče a hloubka vzhledem k tomuto rodiči. Tím pádem mohu jednoduše s použitím vnitřního spojení získat všechny potomky jakéhokoli záznamu na jakékoli hloubce. A navíc zpětně mohu získat také všechny rodiče jakéhokoli záznamu.
Pořadí a zanoření záznamů je určeno sloupci pořadí a hloubky v tabulce se záznamy.
Při vložení nového záznamu na určité místo stačí jen posunout pořadí všech následujících záznamů, vložit s požadovaným pořadím a aktualizovat tabulku spojení. S použitím indexů by měla být efektivita výběru prvků velmi dobrá.
Formátování článku
Zdarec.
Nešlo by přidat k výpisům dat nějaké rozumné formátování?
A také zvýrazňování SQL syntaxe?
Bylo by to fajn :-)
Nested Intervals
Tomuhle se říká „Nested Intevals“. Je to velice chytrý, celkem a jednoduchý a při malém množství změn i velmi rychlý způsob, jak udržet strom v SQL databázi.
Rozhodně doporučuju nespoléhat jen na sloupce Left a Right, ale udržovat si i Parent, protože když se to povede rozbít (což se během vývoje může lehce stát), tak se to nedá jinak opravit.
Btw, pro MySQL existuje pěkný návod tu: http://web.archive.org/web/20110606032941/http://dev.mysql.com/tech-resources/articles/hierarchical-data.html (originál nějak zmizel z http://dev.mysql.com/tech-resources/articles/hierarchical-data.html)
Re: Nested Intervals
Úplně ideální je ukládat si jak parent, tak level (např. vypsat celý strom, ale max. do třetí úrovně – do menu – zbytek bude jen v breadcrumbs) a využívat to při selectech.
A pokud probíhají časté úpravy do DB a DB neni moc velká, tak je jednodušší než dělat updaty nad MPTT upravit jen parent/level a pak přepočítat celý strom rekurzivně.
Používám to ve svém projektu na eshopu s přibližně 100 kategoriemi a funguje to v pohodě. Celé přegenerování trvá nějakých slabých 250ms. Což je docela dost, ale při jednorázové akci, jakou změna v kategoriích je to není takový problém.
Re: Nested Intervals
Díky, dlouho jsem hledal ten původní článek, který byl najednou 404.
uložení stromu
Na diskuzi je vidět jeden podstatný nedostatek celého článku: není příliš zřejmé, jaké operace chceme nad stromem provádět. Každá reprezentace bude mít svoje výhody pro podporu určitých operací. Například pro vypsání stromu je intervalové hodnocení skutečně zbytečné (te to vidět i na tom, že algoritmus display_tree používá pouze left hodnotu).
Jak jsem psal už u minulého dílu: je to jako by jste řešili jaký bude nejlepší dům, ale jaksi zapoměli zmínit k čemu bude sloužit.
Re: uložení stromu
Souhlas – a taky záleží na počtu uzlů, alespoň orientačně – je dost velký rozdíl, jestli jich máme 100 (např. kategorie zboží v obchodě) nebo milion. V prvním případě není žádný problém držet v RAM sestavený strom (třeba jako XML DOM) a z databáze číst jen při změnách (jak často přibývají kategorie v obchodě?). S rostoucím počtem uzlů a frekvencí změn to problém začíná být a je potřeba hledat jiné řešení.
Další věc je nějaké vnitřní členění stromu – zatím se tu píše o obecných stromech a univerzálních řešeních, ale může to být tak, že některé části stromu patří k sobě a pak se vyplatí dělat něco jako „partitioning“. Např. u diskusních příspěvků nás bude zajímat obvykle jedna diskuse jako celek – ne všechny příspěvky z celého serveru jako jeden strom a ne jedno podvlákno (to jen výjimečně). Proto může být rozumné držet si u všech příspěvků vedle jejich předka i odkaz na článek (diskusi), ke kterému patří, protože obvykle budeme provádět operace nad příspěvky z této skupiny. (denormalizovaná databáze)
Re: uložení stromu
No vidite a to jste jeste zapomel treba mutace, a dalsi moznosti jak charakterizovat pripadne podmnoziny stromů. Asi nema smysl to vsechno rozepisovat ne?
MPTT
Osobně jestě volím navíc artibut tree_id. Ten mu umožnuje držet více stromů vedle sebe, v jedné tabulce, s více root elementy.
Zasvědcení jistě budou znát aplikace django-mptt, která vše zmíněné obsahuje.
Ještě je dobrá dát si pozor při přesouvání (patrně obsah příštího článku) na „kauzální“ problémy – přesun rodiče pod svého potomka…
Re: MPTT
Ještě doplním link:
https://github.com/django-mptt/django-mptt
Učel
musím tedy souhlasit s různými příspěvky v nichž padlo a nebo z nich vyplíva ze implementace je urcena vetsinou pozadavky. A nebo delame neco robusnejsiho, vsestranejsiho, to by pak melo obsahovat vetsi miru abstrakce.
Nested Set
http://blog.voracek.net/databaze/closure-table-stromy-v-mysql-trochu-jinak/
úprava
nenacitaji se obrazky. Upravit pravopis . Zvyraznovat kod