GoldenLine
Zaloguj się
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Witam,

Na początku zaznaczę że identyczny temat założyłem w grupie Bazy danych, jednak z racji tego iż nie każdy jest zapisany do obu, pozwolę sobie zamieścić tutaj kopię. Jako że PHP łączy się najczęściej z MySQL/PostgreSQL myślę że macie w tym temacie całkiem spore doświadczenie :-)

Interesuje mnie w jaki sposób organizujecie w swoich projektach przechowywanie hierarchicznych struktur danych w bazie?
Przyjmijmy że jako hierarchiczną strukturę rozumiem tutaj zwykłe drzewo z dowolną liczbą dzieci, nieograniczone na wysokość.

Czego używacie do przechowywania takiego drzewa? Nested Sets, "drzewka IP", coś innego?
Jeśli macie własne rozwiązania, jak takie struktury zachowują się u was przy dużej ilości rekordów (duża >> 100 000) ?
Link do wypowiedziLink
Michał C.

Michał C. Deputy Head of
Software Development

Temat: Hierarchiczne struktury w relacyjnych bazach danych

http://www.depesz.com/various/various-sqltrees-impleme...
To jest przedstawiona implementacja dla postgresql. Ja zrobiłem odpowiednik dla mysql. Nawet mam gdzies wtyczke w postaci klasy w php do modyfikowania struktury takiego drzewa :)
IMO Najlepsze rozwiązanie ze wszystkich mi znanych..
Link do wypowiedziLink
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Ciekawe, ciekawe...
Zastanawia mnie tylko jak zachowuje się funkcja generująca ścieżkę createpath(id) dla dużej ilości danych... Ona wywołuje rekurencyjnie zapytanie SELECT w zależności od głębokości szukanego węzła.
Jak to wygląda od strony praktycznej?:-)
Link do wypowiedziLink

konto usunięte

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Teoretycznie
http://dev.mysql.com/tech-resources/articles/hierarchi...

Php + propel
http://trac.symfony-project.com/wiki/sfPropelActAsNest...

A praktycznie to DBMonster + Test Unit i będziesz wiedział co i jak
Link do wypowiedziLink
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

To co podałeś to właśnie Nested Sets - znamy, znamy i lubimy :-)
Prosta struktura, ładny, niezależny od systemu BD, zgodny ze standardami, SQL.

Na grupie Bazy Danych Robert Kubalski zarzucił takim linkiem:
http://www.wss.pl/SQLServer/Articles/9641.aspx (na samym dole).
Microsoft wprowadził w swoich bazach nowy typ danych "HierarchicalData".

Czy znacie jeszcze jakieś inne (oprócz już wymienionych) struktury, implementacje do przechowywania danych tego typu?

Do tej pory mamy:
1. Nested Sets
2. "Drzewka IP" aka "model zmaterializowanej ścieżki" i jej implementacja w T-SQL (MsSQL): http://www.wss.pl/SQLServer/Articles/9641.aspx
3. "Drzewka Depesza" - zapodane przez Michała Czerwińskiego.

Kto da więcej?:-)
Link do wypowiedziLink
Wojciech Sznapka

Wojciech Sznapka CTO @ STS Zakłady
Bukmacherskie

Temat: Hierarchiczne struktury w relacyjnych bazach danych

XML i pole typu XML w DB2 ;-) Ale to tylko dla tego środowiska. Warto jednak zapoznać się z tematem, bo jest nad wyraz ciekawy :-)
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Osobiście bardzo mi się podobają Nested Sets.
Zalety:
- nie wymagają dodatkowych tabel
- ścieżka do węzła pobierana jedną łatwą i szybką kwerendą
- przeszukiwanie poddrzewa bardzo łatwe i szybkie (zwłaszcza jeżeli mamy indeks na pola left i right)
- węzły są naturalnie uporządkowane (nie trzeba wprowadzać dodatkowych pól do przechowywania kolejności)

Wady:
- trudno zaprogramować operacje na drzewie (przepinanie, zmiana kolejności) tak żeby nie wymagały przeliczania left i right za każdym razem
- nawet optymalnie napisane operacje przy dodawaniu nowych węzłów, usuwaniu i przepinaniu istniejących zmieniają bardzo wiele rekordów

Czyli nie dla ludzi o słabym sercu i szybko rozrastających się drzew.
Link do wypowiedziLink
Tomasz Struczyński

Tomasz Struczyński TeamLeader PHP i
analityk

Temat: Hierarchiczne struktury w relacyjnych bazach danych

To jeszcze apropos depesza:

Znalazłem kiedyś w sieci jego opracowanie drzewek z porównaniem kilku metod (i między innymi ta rozbudowaną w poprzednich komentarzach):

http://www.dbf.pl/faq/tresc.html?rozdzial=1#o1_9
Link do wypowiedziLink
Marcin Domański

Marcin Domański Programista

Temat: Hierarchiczne struktury w relacyjnych bazach danych

W CakPHP Access Controll Lists są zaimplementowane jako drzewo Modified Preorder Tree Traversal (MPTT) (jest też TreeBehavior coś jak act_as_tree)

http://www.sitepoint.com/print/hierarchical-data-database
http://iamcam.wordpress.com/2006/03/17/storing-hierarc...
Link do wypowiedziLink

konto usunięte

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Drzewka "nested sets" (wiersze z kolumnamy "left" "right" - coś na wzór "kolorowania pre-order") są bardzo wydajne jeśli chcemy listować gałąź ścieżkę itd.

Zabawa zaczyna się jednak jeśli chcemy przenieść całą "gałąź" w inne miejsce, i to wymaga już więcej uwagi..

Problem jest też gdy utracimy "spójność" struktury, dlatego dobrym rozwiązaniem jest połączenie klasycznego podejścia po "parent ID" i kolorowania "lewy", "prawy", co jednak komplikuje implementację.

Dla baz nie wspierających struktur hierarchicznych nie znam lepszego rozwiązania..
Link do wypowiedziLink
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Część informacji jest wtórna, przykładowo MPTT (Modified Preorder Tree Traversal) = Nested Sets.
Postaram się zrobić krótkie podsumowanie na zakończenie, może komuś się przyda na przyszłość, ale to później...

Tymczasem może macie coś jeszcze co nie pojawiło się tutaj?:-)
Ciekawe są też informacje o tym jeśli jakieś frameworki mają wbudowane modele do przechowywania tego typu danych.

Podsumowanie za kilka dni :-)
Link do wypowiedziLink
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Nikodem:
Właśnie ja też do tej pory używałem jak na razie dwóch sposobów przechowywania danych: Nested Sets (+parent_id) oraz przechowywanie ścieżki do korzenia (aka "zmaterializowana ścieżka", "persistent path").

Ale zawsze warto nauczyć się czegoś więcej :-)
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Przemek Szalko:
Nikodem:
Właśnie ja też do tej pory używałem jak na razie dwóch sposobów przechowywania danych: Nested Sets (+parent_id) oraz przechowywanie ścieżki do korzenia (aka "zmaterializowana ścieżka", "persistent path").

Ale zawsze warto nauczyć się czegoś więcej :-)
Interesującym pomysłem mogą być nested sety (+parent_id +level) ale z wartościami left i right typu float. To by znacznie przyspieszało wstawianie i usuwanie węzłów względem wersji z integerami. Przepinanie fragmentu drzewa w inne miejsce też dużo szybsze. Nie testowałem tego ale na pierwszy rzut oka wygląda atrakcyjnie.
Link do wypowiedziLink
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

A dlaczego z wartościami left i right jako float?
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Przemek Szalko:
A dlaczego z wartościami left i right jako float?
Po to żeby nie trzeba było wykonywać updatu na wszystkich rekordach leżących na prawo od pozycji w której wstawiamy nowy lub z której usuwamy istniejący węzeł. Między dwoma floatami zawsze jest miejsce (o ile nie przekroczymy zakresu na wykładnik), nie trzeba go robić rozpychając pozostałe węzły.

Wstawienie polega na sprawdzeniu jaki jest right węzła po którym wstawiamy (albo left rodzica jeżeli wstawiany węzeł ma być pierwszym dzieckiem) i left węzła przed którym wstawiamy (albo right rodzica jeżeli wstawiany węzeł ma być ostatnim dzieckiem). Te dwie liczby to krańce przedziału. Left nowo wstawianego węzła umieszczamy w 1/3 tego przedziału a right w 2/3 i gotowe. Żadnych updatów. Z kolei żeby usunąć węzeł wystarczy usunąć odpowiadający mu rekord.

Daj znać czy nie widzisz może jakiejś luki w moim rozumowaniu, bo może piszę jakieś herezje, wpadłem na ten pomysł dziś.Kamil Szot edytował(a) ten post dnia 15.04.08 o godzinie 19:16
Link do wypowiedziLink
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Pomijając tutaj ograniczoność zakresu w zapisie liczb na komputerach oraz to że dodawanie i odejmowanie to działania źle uwarunkowane (szczególnie przy gęstszej strukturze wyszłoby to na jaw!) wydaje mi się że jest jeden podstawowy problem który dyskwalifikuje to rozwiązanie.

Wyobraźmy sobie taką strukturę:
- jeden węzeł korzenia o left i right (1,2)
- następnie dodajemy do niego trójkę dzieci: a, b, c.
Jakie współrzędne left i right będą miały te dzieci? Zakładamy że dziecko dodajemy zawsze na koniec.

Odpowiem sobie sam ;-)
a = (4/3, 7/3)
b = (16/9, 7/3)
c = (43/27, 7/3)

Problem jest taki, że right dla dziecka obliczamy zawsze na podstawie tej samej wartości - wartości right jego rodzica.
To dyskwalifikuje rozwiązanie "bez updatowania".

Teraz załóżmy że mamy dwa węzły:
A = (1,2)
B = (3,4)

Do węzła A będziemy dodawać dzieci a,b,c tak samo jak w przypadku powyżej.

Załóżmy też że dokładamy update dla rodzica, czyli po dodaniu każdego dziecka rodzicowi nadajemy wartość right.. Pytanie tylko jaką?
1. Dodajemy do right rodzica tyle co wyliczyliśmy dla wstawianego dziecka:
A (1,13/3)
.... a (4/3, 7/3)
B (3,4)

2. Dodajemy do right rodzica dokładnie 1:
A (1,3)
.... a(4/3, 7,3)

Już po dodaniu jednego dziecka widać problem: wskakujemy do przedziału B (3,4) w obu przypadkach!
Trzeba updatować sąsiada, a za nim jego potomków, a później następnego sąsiada.... Czyli dokładnie to co w Nested Sets dla wartości całkowitych.

Dodatkowo przychodzą tutaj błędy wynikające z przekroczenia zakresu - którego normalnie, dla left i right całkowitych, nie osiągnelibyśmy tak szybko jak przy dzieleniu :-)
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Przemek Szalko:
Pomijając tutaj ograniczoność zakresu w zapisie liczb na komputerach oraz to że dodawanie i odejmowanie to działania źle uwarunkowane (szczególnie przy gęstszej strukturze wyszłoby to na jaw!) wydaje mi się że jest jeden podstawowy problem który dyskwalifikuje to rozwiązanie.

Wyobraźmy sobie taką strukturę:
- jeden węzeł korzenia o left i right (1,2)
- następnie dodajemy do niego trójkę dzieci: a, b, c.
Jakie współrzędne left i right będą miały te dzieci? Zakładamy że dziecko dodajemy zawsze na koniec.

Odpowiem sobie sam ;-)
a = (4/3, 7/3)
b = (16/9, 7/3)
c = (43/27, 7/3)

raczej:

a = (1+1/3, 2-1/3)
b = ((2-1/3)+1/9, 2-1/9)
c = ((2-1/9)+1/27, 2-1/27)
Problem jest taki, że right dla dziecka obliczamy zawsze na podstawie tej samej wartości - wartości right jego rodzica.
obliczamy na podstawie wartości right jego rodzica, a nie kopiujemy z wartości right jego rodzica
Dodatkowo przychodzą tutaj błędy wynikające z przekroczenia zakresu - którego normalnie, dla left i right całkowitych, nie osiągnelibyśmy tak szybko jak przy dzieleniu :-)
właśnie jestem ciekaw jak szybko wystąpiłby problem zakresu, bo co jakiś czas trzeba by na pewno robić renormalizację drzewa (nadawać węzłom wartości left i right jak w standardowych nested sets) .... właśnie mi przyszło do głowy że dość często bo floaty mają rewelacyją rozdzielczość tylko naokoło zera a w przedziale (10000005, 10000006) znacznie niższą

Można by zrobić szybki teścik praktyczny i sprawdzić ile węzłów zmieści się jako dzieci węzła o l,r = (10000005, 10000006) zanim wyliczone nl i nr nowododanego dziecka przestaną spełniać zależność pr < nl < nr < r gdzie pr to right poprzednio dodanego dziecka.
Link do wypowiedziLink
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Trochę Cię nie zrozumiałem wcześniej.. ;-)
Może później zrobię jakieś testy to zobaczymy.Przemek Szalko edytował(a) ten post dnia 17.04.08 o godzinie 10:43
Link do wypowiedziLink
Przemek Szalko

Przemek Szalko iOS Developer + Full
Stack Developer

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Ok, zrobiłem mały test.

Kod PHP: http://pastebin.com/f3037ab23
Struktura bazy: http://pastebin.com/f6d5f2f

Dodajemy tutaj 20 węzłów na poziomie 1.
Dla każdego następnego węzła dodajemy rekurencyjnie 5 dzieci, dodatkowo ograniczenie na wysokość drzewka też 5.

Dla typu float (jak w przykładzie) już po dodaniu 7 751 węzłów pojawia się zduplikowana wartość "left". Dla double dodałem ponad 77 000 rekordów i się zmieściło ;-)

Ale pojawia się inny problem - przedziały nachodzą na siebie!
Nie możemy wybierać węzłów za pomocą polecenia BETWEEN, trzeba zastosować porównywanie dla LEFT i RIGHT jednocześnie. Nie jest to wielki problem, ale mimo wszystko widać że coś zaczyna się psuć.

Inna sprawa że to dość niedeterministyczna struktura :-)

Wspomniałeś o "renormalizacji" drzewka - pytanie.. Kiedy wykryjesz że jest taka renormalizacja potrzebna? Trzeba je ostro kontrolować aby nie powstały przekłamania.

Jeśli dodajemy jednocześnie po kilkanaście/kilkadziesiąt węzłów to całkiem niezły pomysł aby tymczasowo indeksować je wartościami float/double. Jednak po operacji hurtowego dodania tych węzłów trzeba by od razu przeprowadzić "normalizację" bazy i później już operować na typach INT.

Dla typowych zastosowań webowych, gdzie ilość węzłów jest dość mała mogłoby się udać :-))
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Przemek Szalko:
Ok, zrobiłem mały test.

Kod PHP: http://pastebin.com/f3037ab23
Struktura bazy: http://pastebin.com/f6d5f2f

Dodajemy tutaj 20 węzłów na poziomie 1.
Dla każdego następnego węzła dodajemy rekurencyjnie 5 dzieci, dodatkowo ograniczenie na wysokość drzewka też 5.

Dla typu float (jak w przykładzie) już po dodaniu 7 751 węzłów pojawia się zduplikowana wartość "left". Dla double dodałem ponad 77 000 rekordów i się zmieściło ;-)
Fajnie. Dla double-a całkiem przyzwoicie. Można by jeszcze jakoś stuningować dodawanie tak żeby w intensywnie rosnących gałęziach drzewa l i r nowododawanego dziecka nie koniecznie lądowało w 1/3 od brzegów przedziału. Tylko troszkę bliżej lewej krawędzi tak żeby "pojemność" rodzica była zużywana wolniej.
Ale pojawia się inny problem - przedziały nachodzą na siebie!
Nie możemy wybierać węzłów za pomocą polecenia BETWEEN, trzeba zastosować porównywanie dla LEFT i RIGHT jednocześnie. Nie jest to wielki problem, ale mimo wszystko widać że coś zaczyna się psuć.
Możesz powiedzieć coś więcej?
Inna sprawa że to dość niedeterministyczna struktura :-)
Nie sądzę, po prostu konkretne wartości zależą od kolejności wstawiania węzłów.
Wspomniałeś o "renormalizacji" drzewka - pytanie.. Kiedy wykryjesz że jest taka renormalizacja potrzebna? Trzeba je ostro
kontrolować aby nie powstały przekłamania.
Chyba wystarczy przy każdym wstawianiu sprawdzać jak się ma nr-nl do nl. Jeżeli jest za małe to jest ryzyko przekroczenia dokładności double-a więc należy sobie ustawić jakąś flagę i na podstawie tej flagi później asynchronicznie "renormalizować" drzewo (albo tylko tą gałąź). Dodatkowo żeby być absolutnie pewnym można by jeżeli nr-nl do nl ma krytycznie małą wartość, wykonywać natychmiastową "renormalizację" (to tak na wszelki wypadek gdyby nadal intensywnie dodawano węzły a asynchroniczna "renormalizacja" nie została jeszcze wykonana).
Jeśli dodajemy jednocześnie po kilkanaście/kilkadziesiąt węzłów to całkiem niezły pomysł aby tymczasowo indeksować je wartościami float/double. Jednak po operacji hurtowego dodaniatych węzłów trzeba by od razu przeprowadzić "normalizację" bazy i później już operować na typach INT.
W przypadku w którym musisz dodać na raz dużo węzłów do tego samego parenta, możesz za wczasu podzielić cały dostępny przedział na tyle kawałków ile węzłów chcesz wstawić. Dzięki temu będziesz zużywał dostepne miejsca znacznie wolniej.
Dla typowych zastosowań webowych, gdzie ilość węzłów jest dość mała mogłoby się udać :-))
Dla małej ilości węzłów to zwykłe nested sets są wystarczające. Mój pomysł miałby zastosowanie raczej w sytuacjach gdzie tykanie updatem średnio połowy węzłów drzewa przy każdym wstawianiu byłoby niedopuszczalne.Kamil Szot edytował(a) ten post dnia 17.04.08 o godzinie 15:25
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

Biblioteka do migracji stru...




Wyślij zaproszenie do
Anuluj