metodę zagnieżdżonych zbiorów poznałem po raz pierwszy po przeczytaniu którejś z książek joe celko. chyba tej: Advanced SQL Programming, ale na 100% nie jestem pewien.
zagnieżdżone zbiory (nested sets) polegają w duzym skrócie na tym, że każdy element drzewa jest opisany nie jednym id, ale parą liczb. są to w miarę dowolne liczby, z założeniem jedynie takim, że "lewa" jest mniejsza od "prawej", oraz, że obie liczby (lewa i prawa) wszystkich elementów drzewa poniżej danego muszą się mieścić w zakresie (lewa, prawa) swoich rodziców.
skomplikowane? też nie zrozumiałem.
przypomnijmy sobie nasze oryginalne, testowe drzewo:
teraz.
tworzymy sobie taką tabelkę:
# create table nested_sets ( id_left int4 primary key, id_right int4 not null check (id_left < id_right), name text);
jako primary key wybrałem sobie id_left, ale mogłem wybrać też right. w szczególności – wartości w polach id_left i id_right muszą być unikatowe. czyli jeśli w którymś elemencie w polu id_left jest wartość 5, to nie może się ona powtórzyć ani w id_left ani w id_right.
ok. jak nadać numerki?
proste. zaczynamy od elementu głównego, i przyznajemy mu id_left = 1. potem idziemy do jego pierwszego dziecka. jego id_left dajemy kolejny numer. jeśli ten element ma podelementy, to powtarzamy zejście w dół z przyznawaniem kolejnych id_left. jeśli dany element nie ma "dzieci", to nadajemy mu id_right równy kolejnej liczbie. i wracamy piętro wyżej.
mało jasne? pewnie nie umiem za dobrze opisać. więc lecimy w krokach:
- elementowi sql, przypisujemy id_left = 1, i schodzimy w dół do "postgresql".
- elementowi postgresql, przypisujemy id_left = 2, i ponieważ ma jakieś dzieci, schodzimy w dół – do "linux"
- elementowi linux przypisujemy id_left = 3
- ponieważ linux nie ma "dzieci", przypisujemy mu id_right = 4 i wracamy wyżej
- ponieważ postgresql nie ma "dzieci", przypisujemy mu kolejne id_right. czyli id_right = 5. i wracamy wyżej.
- jesteśmy z powrotem w sql. wchodzimy w kolejne dziecko – oracle
- elementowi oracle przypisujemy id_left = 6.
- itd. aż dojdziemy do ustawienia dla elementu sql, id_right = 18
zwracam uwagę na to, że w tej numeracji widać od razu, że ilość elementów jest równo połową największego id_right. co jest poniekąd logiczne.
cała tabelka wygląda tak:
| id_left | id_right | name |
| 1 | 18 | sql |
| 2 | 5 | postgresql |
| 3 | 4 | linux |
| 6 | 17 | oracle |
| 7 | 8 | solaris |
| 9 | 14 | linux |
| 10 | 11 | glibc1 |
| 12 | 13 | glibc2 |
| 15 | 16 | windows |
ok. jak się pyta taką bazę?
tu uwaga – ten model znam najsłabiej. głównie dlatego, że go osobiście nie lubię. jeśli znajdziecie błąd w tym co poniżej napiszę – proszę o informację. nie jestem nieomylny, a jak już mówiłem – tego modelu drzew nie lubię i nie bawiłem się nim w ogóle.
1. pobranie listy elementów głównych (top-levelowych)
SELECT
ns1.*
FROM
nested_sets ns1
LEFT OUTER JOIN nested_sets ns2 ON (ns1.id_left > ns2.id_left AND ns1.id_right < ns2.id_right)
WHERE
ns2.id_left IS NULL
;
zwrócić należy uwagę na fakt iż jeśli nasze drzewo ma tylko i wyłącznie 1 element top-levelowy to zapytanie można uprościć do:
# SELECT * FROM nested_sets WHERE id_left = 1;
jeśli stosujemy numerację od 1, lub
# SELECT * FROM nested_sets ORDER BY id_left ASC LIMIT 1;
jeśli numeracja startuje od nieznanej liczby.
2. pobranie elementu bezpośrednio “nad” podanym elementem:
dane wejściowe:
- ID : id_left elementu
SELECT
ns.*
FROM
nested_sets ns
WHERE
[ID] BETWEEN ns.id_left + 1 AND ns.id_right
ORDER BY ns.id_left DESC LIMIT 1
jeśli zapytanie nic nie zwróci – znaczy to, że dany element był “top-levelowy”.
3. pobranie listy elementów bezpośrednio “pod” podanym elementem
dane wejściowe:
- ID : id elementu
SELECT
nsc.*
FROM
nested_sets nsp
JOIN nested_sets nsc ON (nsc.id_left BETWEEN nsp.id_left + 1 AND nsp.id_right)
WHERE
nsp.id_left = [ID]
AND NOT EXISTS (
SELECT *
FROM nested_sets ns
WHERE
( ns.id_left BETWEEN nsp.id_left + 1 AND nsp.id_right )
AND
( nsc.id_left BETWEEN ns.id_left + 1 AND ns.id_right )
)
4. pobranie listy wszystkich elementów “nad” danym elementem (wylosowanym)
dane wejściowe:
- ID : id elementu
SELECT
ns.*
FROM
nested_sets ns
WHERE
[ID] BETWEEN ns.id_left + 1 AND ns.id_right
5. pobranie listy wszystkich elementów “pod” danym elementem (wylosowanym)
dane wejściowe:
- ID : id elementu
SELECT
nsc.*
FROM
nested_sets nsp
JOIN nested_sets nsc ON nsc.id_left BETWEEN nsp.id_left + 1 AND nsp.id_right
WHERE
nsp.id_left = 6
6. sprawdzenie czy dany element jest “liściem” (czy ma pod-elementy)
dane wejściowe:
- ID : id elementu
>SELECT true from nested_sets WHERE id_left = [ID] AND id_right = [ID] + 1;
jeśli zwróci true – to jest liść. jeśli nic nie zwróci – to nie jest liściem.
7. pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element
- ID : id elementu
SELECT
ns.*
FROM
nested_sets ns
WHERE
[ID] BETWEEN ns.id_left + 1 AND ns.id_right
ORDER BY
ns.id_left ASC LIMIT 1
podstawową zaletą tego rozwiązania jest to, że bardzo szybko zwraca listę wszystkiego "nad", "pod" czy listę liści.
wadami jest mała intuicyjność, skomplikowane przenoszenie elementów (gdybym miał to zaimplementować, to najprawdopodobniej po prostu po każdym przeniesieniu od nowa bym numerował id_left/id_right.
dodatkowo – część zapytań wymaga albo "order by xxx limit 1", albo subselectów co raczej nie wróży dobrze wydajności. a order by limit 1 nie zawsze można użyć (np. użycie tego w joinach jest już mocno problematyczne).
Odnośnie:
skomplikowane przenoszenie elementów (gdybym miał to zaimplementować, to najprawdopodobniej po prostu po każdym przeniesieniu od nowa bym numerował id_left/id_right.
W takim razie pozwól pomogę 😉
Co rozumiemy poprzez przeniesienie elementu?
Przenoszenie dowolnego elementu wraz z potomstwem w inne miejsce?
Jeśli tak, to rozwiązanie jest proste a co więcej algorytmicznie jest równoważne usunięciu i wstawieniu pojedyńczego liścia.
Dlaczego? Bo:
1) jak gdzieś wstawimy jakiś element (nowy liść), to musimy zwiększyć odpowiednie id_right oraz id_left o 2.
2) jak usuwamy liść to (aby zachować ciągłość numeracji) musimy zmniejszyć odpowiednie id_right oraz id_left o 2
3) jak wstawiamy N elementów to musimy zwiększyć odpowiednie id_right oraz id_left o 2N.
4) usuwamy N elementów – zmniejszamy o 2N.
5) jak usuwamy jakieś poddrzewo (którego korzeniem jest element o id_left=X oraz id_right=Y) to najpierw usuwamy poddrzewo a potem zmniejszamy odpowiednie wartości o Y-X+1 (aby zachować ciągłość numeracji)
6) jak wstawiamy gdzieś poddrzewo to musimy zwiększyć odpowiednie wartości o Y-X+1. A potem wstawić drzewo.
Jeśli chcemy podpiąć jakiś element w dowolne miejsce to możliwe mamy 2 warianty:
1) chcemy podpiąć ten element jako ostatniego potomka (jeśli nie ma jeszcze żadnych potomków to pierwszy będzie też ostatnim) jakiegoś elementu
2) chcemy podpiąć element po lewej od jakiegoś elementu (bo albo będzie po lewej od jakiegoś potomka, albo będzie ostatnim potomkiem rodzica prawda?)
Jak mi się wydaje (myśląc na szybko), oba punkty można zrealizować jedną operacją.
1) jak ostatni potomek, to podajemy na wejściu id_right rodzica
2) jak po lewej od czegoś, to dajemy id_left tego czegoś
Innymi słowy, zawsze podajemy najmniejszą wartość spośród tych które będziemy zmieniać.
Tak więc wstawianie jednego elementu (X to najmniejsza zmieniana wartość) wygląda tak:
update nested_sets set id_left = id_left + 2 where id_left >= X;
update nested_sets set id_right = id_right + 2 where id_right >= X;
insert into nested_sets values (X, X+1,’treść’);
Usuwanie liścia o id_left=Z:
delete from nested_sets where id_left=Z;
update nested_sets set id_left = id_left – 2 where id_left >= Z;
update nested_sets set id_right = id_right – 2 where id_right >= Z;
Teraz usuwanie pojedyńczego elementu (niekoniecznie liścia) o id_left=A oraz id_right=B:
delete from nested_sets where id_left=A;
— tu zmieniamy potomków usuwanego elementu
update nested_sets set id_left = id_left – 1, id_right = id_right – 1 where id_left > A and id_right B;
update nested_sets set id_left = id_left – 2 where id_left > B;
Należy zauważyć, że wszystkie elementy poniżej usuniętego elementu będą teraz podpięte do jego rodzica (czyli poszły w hierarchii o jeden poziom w górę).
A teraz jak przenieść poddrzewo?
Przenosimy element o id_left=A oraz id_right=B wraz z całym potomstwem w miejsce X (jak wcześniej, X jest najmniejszą z wartości jakie będziemy zmieniać) Zakładamy ponadto, że X B
1) tworzymy tabelkę z buforem, można by się obyć bez niej, ale byłoby to bardziej skomplikowane
create table nested_sets_buffer (
id_left int4 primary key,
id_right int4 not null check (id_left =A and id_right=A and id_right=X and id_righr =X and id_left B to zmieniamy tylko zakres od B do X
update nested_sets set id_right = id_right – (B-A+1) where id_right>B and id_rightB and id_left
Drobna poprawka (wcześniej znaczki większe/mniejsze zostały odczytane jako znaczniki)
Odnośnie:
skomplikowane przenoszenie elementów (gdybym miał to zaimplementować, to najprawdopodobniej po prostu po każdym przeniesieniu od nowa bym numerował id_left/id_right.
W takim razie pozwól pomogę 😉
Co rozumiemy poprzez przeniesienie elementu?
Przenoszenie dowolnego elementu wraz z potomstwem w inne miejsce?
Jeśli tak, to rozwiązanie jest proste a co więcej algorytmicznie jest równoważne usunięciu i wstawieniu pojedyńczego liścia.
Dlaczego? Bo:
1) jak gdzieś wstawimy jakiś element (nowy liść), to musimy zwiększyć odpowiednie id_right oraz id_left o 2.
2) jak usuwamy liść to (aby zachować ciągłość numeracji) musimy zmniejszyć odpowiednie id_right oraz id_left o 2
3) jak wstawiamy N elementów to musimy zwiększyć odpowiednie id_right oraz id_left o 2N.
4) usuwamy N elementów – zmniejszamy o 2N.
5) jak usuwamy jakieś poddrzewo (którego korzeniem jest element o id_left=X oraz id_right=Y) to najpierw usuwamy poddrzewo a potem zmniejszamy odpowiednie wartości o Y-X+1 (aby zachować ciągłość numeracji)
6) jak wstawiamy gdzieś poddrzewo to musimy zwiększyć odpowiednie wartości o Y-X+1. A potem wstawić drzewo.
Jeśli chcemy podpiąć jakiś element w dowolne miejsce to możliwe mamy 2 warianty:
1) chcemy podpiąć ten element jako ostatniego potomka (jeśli nie ma jeszcze żadnych potomków to pierwszy będzie też ostatnim) jakiegoś elementu
2) chcemy podpiąć element po lewej od jakiegoś elementu (bo albo będzie po lewej od jakiegoś potomka, albo będzie ostatnim potomkiem rodzica prawda?)
Jak mi się wydaje (myśląc na szybko), oba punkty można zrealizować jedną operacją.
1) jak ostatni potomek, to podajemy na wejściu id_right rodzica
2) jak po lewej od czegoś, to dajemy id_left tego czegoś
Innymi słowy, zawsze podajemy najmniejszą wartość spośród tych które będziemy zmieniać.
Tak więc wstawianie jednego elementu (X to najmniejsza zmieniana wartość) wygląda tak:
update nested_sets set id_left = id_left + 2 where id_left >= X;
update nested_sets set id_right = id_right + 2 where id_right >= X;
insert into nested_sets values (X, X+1,’treść’);
Usuwanie liścia o id_left=Z:
delete from nested_sets where id_left=Z;
update nested_sets set id_left = id_left – 2 where id_left >= Z;
update nested_sets set id_right = id_right – 2 where id_right >= Z;
Teraz usuwanie pojedyńczego elementu (niekoniecznie liścia) o id_left=A oraz id_right=B:
delete from nested_sets where id_left=A;
— tu zmieniamy potomków usuwanego elementu
update nested_sets set id_left = id_left – 1, id_right = id_right – 1 where id_left > A and id_right < B;
— a tutaj operacja analogiczna do usuwania liścia
update nested_sets set id_right = id_right – 2 where id_right > B;
update nested_sets set id_left = id_left – 2 where id_left > B;
Należy zauważyć, że wszystkie elementy poniżej usuniętego elementu będą teraz podpięte do jego rodzica (czyli poszły w hierarchii o jeden poziom w górę).
A teraz jak przenieść poddrzewo?
Przenosimy element o id_left=A oraz id_right=B wraz z całym potomstwem w miejsce X (jak wcześniej, X jest najmniejszą z wartości jakie będziemy zmieniać) Zakładamy ponadto, że X < A lub X > B
1) tworzymy tabelkę z buforem, można by się obyć bez niej, ale byłoby to bardziej skomplikowane
create table nested_sets_buffer (
id_left int4 primary key,
id_right int4 not null check (id_left < id_right),
name text
);
2) przenosimy poddrzewo do bufora
insert into nested_sets_buffer select * from nested_sets where id_left>=A and id_right<=B
3) usuwamy poddrzewo
delete from nested_sets where id_left>=A and id_right<=B
4) wykonujemy stosowne update-y, (poniższe operacje są zoptymalizowane do update-owania minimalnej ilości elementów, mogą być przez to mało oczywiste)
jeśli X < A to zmieniamy tylko zakres od X do A, operacje będzie analogiczna do przeniesienia wszystkiego powyżej usuniętego poddrzewa “w dół” (o wartość B-A+1) a następnie przeniesienia wszystkiego powyżej X “w górę” (o wartość B-A+1) w celu zrobienia miejsca na poddrzewo:
update nested_sets set id_right = id_right + (B-A+1) where id_right>=X and id_righr <A;
update nested_sets set id_left = id_left + (B-A+1) where id_left>=X and id_left <A;
— mamy już miejsce w drzewie, teraz czas na update bufora
update nested_sets_buffer set id_left=id_left-A+X, id_right=id_right-A+X
jeśli X > B to zmieniamy tylko zakres od B do X
update nested_sets set id_right = id_right – (B-A+1) where id_right>B and id_right<X
update nested_sets set id_left = id_left – (B-A+1) where id_left>B and id_left<X
— update bufora
update nested_sets_buffer set id_left=id_left + (X-B-1), id_right=id_right + (X-B-1);
5) uff.. finalnie insert do nested_sets
insert into nested_sets select * from nested_sets_buffer
GOTOWE!
Możliwe, że są błędy, rozwiązanie wymyślone na poczekaniu 😉
Na koniec jeszcze jedna myśl, można by nie używać tabeli bufora, tylko zmienić wartości przenoszonego poddrzewa tak, aby stanowiło ono osobne drzewo. Np. wykonać update:
update nested_sets set id_left=-id_left, id_right=-id_right (tu zakładam, że nadawane standardowo wartości są zawsze dodatnie). Potem odpowiednio odwrócić znak operacji na buforach i na koniec zamiast inserta ten sam update 🙂
No i oczywiście można powiedzieć, że rozwiązanie zakłada wyłączność na update w tabeli, ale czy numeracja id_left/id_right od nowa nie niesie w sobie tych samych założeń?
dzięki za info. komentarze ciekawe – sam nested sets raczej nie będę używał (chyba, że na testach wydajnościowych wyjdą super), ale może ktoś się skusi.