Temat: Hierarchiczne struktury w relacyjnych bazach danych

Kamil Szot:
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.

Ciekawe..
Jakie sytuacje masz na myśli?

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Nikodem Kler:

Kamil Szot:
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.

Ciekawe..
Jakie sytuacje masz na myśli?

Drzewo zawiera 100 mln węzłów i chcesz do niego dodawać nowy węzeł co sekundę.

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Kamil Szot:

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?

Proszę bardzo :-)

Chcemy pobrać wszystkich potomków dla zaznaczonego wiersza:





Polecenie SQL:
SELECT *
FROM nested_set
WHERE lft
BETWEEN 1.4814814814815
AND 1.5185185185185
ORDER BY `nested_set`.`parent_id` ASC

Wyniki:





Zaznaczony wiersz to nasz korzeń dla poddrzewa. Zwróćcie uwagę na jeden wiersz ponad i poniżej zaznaczonego. Ich w ogóle tu nie powinno być! (hint: parent_id)

Powinien być jeden wiersz z parent_id = 2, pozostałe mogą mieć parent_id jedynie większe - tutaj pobraliśmy dwa węzły które nie należą do poddrzewa.

Powodem jest zazębianie się przedziałów. Dla węzłów 783 i 159 left "wskakuje" do przedziału naszego korzenia (węzeł o ID = 3).
Nie analizowałem przykładu szczegółowo, możliwe że na większym poziomie zagłębienia pojawiłyby się węzły które mają przedziały całkowicie zanurzone w naszym wyszukiwanym zakresie co fałszowałoby wyniki.

Pierwsze przekłamanie (zachodzenie przedziałów) można naprawić poprzez ograniczanie węzła w left i right, a nie tylko w left jak ja to zrobiłem.
Drugie przekłamanie (jeden przedział zanurzony w drugim) byłoby nie do naprawienia za pomocą SELECT - trzebaby zrenormalizować strukturę.

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

Nie sądzę, po prostu konkretne wartości zależą od kolejności wstawiania węzłów.

I właśnie to jest niedeterministyczne.
Skąd wiesz w jaki sposób na produkcji będą dodawane węzły? Jaką masz gwarancję że będzie to porządek DFS czy BFS, a może całkowicie losowo? Tutaj właśnie mamy niedeterminizm.

Z pozostałymi postulatami się zgadzam ;-)

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Chcemy pobrać wszystkich potomków dla zaznaczonego wiersza:





Polecenie SQL:
SELECT *
FROM nested_set
WHERE lft
BETWEEN 1.4814814814815
AND 1.5185185185185
ORDER BY `nested_set`.`parent_id` ASC

Wyniki:





Zaznaczony wiersz to nasz korzeń dla poddrzewa. Zwróćcie uwagę na jeden wiersz ponad i poniżej zaznaczonego. Ich w ogóle tu nie powinno być! (hint: parent_id)

Powinien być jeden wiersz z parent_id = 2, pozostałe mogą mieć parent_id jedynie większe - tutaj pobraliśmy dwa węzły które nie należą do poddrzewa.

Powodem jest zazębianie się przedziałów. Dla węzłów 783 i 159 left "wskakuje" do przedziału naszego korzenia (węzeł o ID = 3).

Wygląda na to, że masz jakiś błąd w implementacji. W tej metodzie tak samo jak w Nested Sets przedziały związane z dziećmi tego samego rodzica są rozłączne. (węzły 3 i 159 u Ciebie mają najwyraźniej źle wyliczone lft i rgt)

Nie analizowałem przykładu szczegółowo, możliwe że na większym poziomie zagłębienia pojawiłyby się węzły które mają przedziały całkowicie zanurzone w naszym wyszukiwanym zakresie co fałszowałoby wyniki.

Pierwsze przekłamanie (zachodzenie przedziałów) można naprawić poprzez ograniczanie węzła w left i right, a nie tylko w left jak ja to zrobiłem.
Drugie przekłamanie (jeden przedział zanurzony w drugim) byłoby nie do naprawienia za pomocą SELECT - trzebaby zrenormalizować strukturę.

Lepiej nie naprawiać jeżeli nie zna się przyczyn błędu. To jak łykanie środka przeciwbólowego zanim stwierdzi się jaka jest przyczyna bólu.

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

Nie sądzę, po prostu konkretne wartości zależą od kolejności wstawiania węzłów.

I właśnie to jest niedeterministyczne.
Skąd wiesz w jaki sposób na produkcji będą dodawane węzły? Jaką masz gwarancję że będzie to porządek DFS czy BFS, a może całkowicie losowo? Tutaj właśnie mamy niedeterminizm.

Drzewo ma dokładnie tą samą strukturę co w nested sets. Wartości lft i rgt mają dokładnie tą samą funkcję i pozostają w dokładnie tej samej zależności z lft i rgt innych węzłów co w Nested Sets. Jedyne co różni te metody to to, że odległość między dwoma sąsiednimi wartościami lft i rgt nie zawsze wynosi 1, że może przyjmować inne, niższe wartości.
Jeżeli odczytasz węzły posortowane po lft to dostanies je w kolejności DFS tak samo jak w metodzie nested sets. To że konkretne wartości lft i rgt zależą od kolejności w jakiej wstawiane są węzły jeszcze nie znaczy że zależą od tego relacje między nimi i tym samym struktura drzewa.

Przeprowadziłem trochę eksperymentów samemu ponieważ pomysł wyglądał dość atrakcyjnie.
Sprawdziłem ile dzieci można dodać do rodzica o lft = 1 i rgt = 2 jeżeli dodaje je się tak jak rozmawialiśmy (szerokość przedziału dziecka to 1/3 szerokości dostępnego miejsca, jest on umieszczany dokładnie pośrodku wolnego miejsca, nowe dziecko jest dodawane za ostatnim istniejącym).

Oto mój kod:
http://pastebin.com/f54897917

Zmieściły mi się ... 23 węzły. :-)
Oto one:
http://pastebin.com/f7a1ab236

Przy okazji zauważyłem, że PHP ma tylko jedną dostępną precyzję liczby zmiennoprzecinowej i rzutowania (float) (double) i (real) robią dokładnie to samo.

Oczywiście nie trzeba końców przedziału nowododanego węzła umieszczać w 1/3 i 2/3 dostępnego miejsca. Można to zrobić np. w 1/100 i 2/100.

W takim przypadku udało mi się dodać już 933 węzły http://pastebin.com/f20c62a45

Można by jeszcze kombinować ze śledzeniem liczebności dzieci w danym węźle. Na tej podstawie w węzłach w których dochodzi dużo dzieci można by używać współczynników bardziej przesuniętych w lewo (takich jak 1/100 1/200) zamiast domyślnej 1/2 - 2/3

Na dodatek okazuje się, że żeby przekształcić drzewo z lft rgt typu float na zwykłe nested sets wystarczą dwie kwerendy dotykające wszystkich węzłów.

Nawet najprostszy przypadek wygląda dość opłacalnie.
Dodanie 23 węzłów w Nested Sets to średnio w sumie 23*n/2 węzłów zmienionych dwudziestoma trzema updatami, a w mojej metodzie to maksimum 2*n zmienionych dwoma.

Problem z tą metodą polega na tym, że ilość węzłów, które można dodać do drzewa bez updatowania istniejących węzłów przy ustalonych współczynnikach zależy liniowo od ilości cyfr znaczących w reprezentacji lft i rgt.

Całe te badania w sumie zniechęciły mnie to nested sets.

Ktoś zna jakieś wady materialised path?

O ile wyszukiwanie typu path LIKE '12312/23123/1312/123/%' jest wolniejsze od wyszukiwania typu lft BETWEEN 123.23123 AND 123.4123123 jeżeli path jest typu TEXT a lft typu DOUBLE PRECISION ?

Zauważyłem, że INDEX na pole typu TEXT może w MySQL-u maksymalnie brać pod uwagę pierwsze 1000 bajtów danych przechowywanych w polu (http://mysql2.mirrors-r-us.net/doc/refman/5.0/en/index... ). Dla materialised path przy bardzo głębokich drzewach może to stanowić problem.Kamil Szot edytował(a) ten post dnia 20.04.08 o godzinie 01:26

Temat: Hierarchiczne struktury w relacyjnych bazach danych

Pobawię się w archeologa :)
Wg mnie najlepszym rozwiązaniem jest implementacja struktury na podstawie ścieżki IP + model podstawowy - czyli zastosowanie id rodzica.
Zalety to bardzo szybkie listowanie drzewka z dowolnego poziomu (stosując like do IP)
Oczywiście przenoszenie gałęzi wymaga odświeżenia IP dla każdego wpisu ale w metodzie nested trzeba zmieniac lt i rt więc z dwojga złego wolę IP ;)

Temat: Hierarchiczne struktury w relacyjnych bazach danych

+1 z przed 5 latTen post został edytowany przez Autora dnia 23.07.13 o godzinie 13:34