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:
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:
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:
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:
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:
>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
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).