drzewa w sql’u – metoda pełnych ścieżek (metoda nr. 5 w/g starego tekstu)

oj. od ostatniego tekstu nt. drzew już trochę czasu minęło. czas więc dokończyć tę serię 🙂

metodę tę wymyśliliśmy ze znajomymi z firmy w której kiedyś pracowałem.
jest mocno prawdopodobne, że ktoś jeszcze wpadł na taki pomysł, natomiast wiem, że gdy ją wymyślaliśmy – nie korzystaliśmy z niczyich prac.

na czym ona polega? w skrócie na tym, że baza zna wszystkie powiązania między wszystkimi elementami drzewa które są ze sobą powiązaną na zasadzie “ojciec, ojciec ojca, ojciec ojca ojca, …".

w tym celu używamy 2 tabel – pierwszej aby przechowywać informacje o elementach drzewa, a w drugiej – o powiązaniach między nimi.

przykładowo, oryginalne, testowe drzewo:

tabelki:

# create table nodes_5 (
id int4 primary key,
name text
);
# create table tree_5 (
id int4 primary key,
parent_id int4 not null references nodes_5(id),
child_id int4 not null references nodes_5(id),
depth int4
);

wstawianie elementów polega na tym, że wstawiamy rekord do nodes_5, po czym dodajemy do tree_5 rekord którego child_id będzie takie jak aktualnego elementu, depth będzie równy 1, a parent_id będzie wskazywał na element nadrzędny.

następnie w tree_5 należy wstawić rekord którego depth będzie 0, a parent_id i child_id będą ustawione na id nowo wstawionego elementu.

na koniec należy skopiować wszystkie elementy gdzie child_id było takie jak aktualnie parent_id, podbijając depth o 1 i zmieniając child_id na id wstawionego elementu.

uff. skomplikowane?

tak się tylko wydaje. tabelki po wstawieniu danych wyglądają tak – prześledźcie je to zobaczycie, że sprawa jest prosta.

tabelka nodes_5:

id name
1 sql
2 postgresql
3 oracle
4 linux
5 solaris
6 linux
7 windows
8 glibc1
9 glibc2

tabelka tree_5:
# select * from tree_5;

id parent_id child_id depth
1 1 1 0
2 1 2 1
3 2 2 0
4 1 3 1
5 3 3 0
6 2 4 1
7 4 4 0
8 1 4 2
9 3 5 1
10 5 5 0
11 1 5 2
12 3 6 1
13 6 6 0
14 1 6 2
15 3 7 1
16 7 7 0
17 1 7 2
18 6 8 1
19 8 8 0
20 3 8 2
21 1 8 3
22 6 9 1
23 9 9 0
24 3 9 2
25 1 9 3

mam nadzieję, że teraz wygląda to bardziej oczywiście 🙂

ok. jak się pyta taką bazę?

1. pobranie listy elementów głównych (top-levelowych)

SELECT n.* from nodes_5 n left outer join tree_5 t on (n.id = t.child_id and t.depth = 1) where t.id is null

2. pobranie elementu bezpośrednio “nad" podanym elementem:

dane wejściowe:

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.depth = 1 and t.child_id = [ID];

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 n.* from nodes_5 n join tree_5 t on n.id = t.child_id where t.depth = 1 and t.parent_id = [ID];

4. pobranie listy wszystkich elementów “nad" danym elementem (wylosowanym)

dane wejściowe:

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.child_id = [ID];

5. pobranie listy wszystkich elementów “pod" danym elementem (wylosowanym)

dane wejściowe:

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.child_id where t.parent_id = [ID];

6. sprawdzenie czy dany element jest “liściem" (czy ma pod-elementy)

dane wejściowe:

  • ID : id elementu
select count(*) from tree_5 where depth = 1 and parent_id = [ID]

jeśli zwróci 0 – to jest to liść. w innym przypadku zwróci ilość bezpośrednich “dzieci".

7. pobranie głównego elementu w tej gałęzi drzewa w której znajduje się dany (wylosowany) element

  • ID : id elementu
select n.* from nodes_5 n join tree_5 t on n.id = t.parent_id where t.child_id = [ID] order by depth desc limit 1;

podstawową zaletą tego rozwiązania jest to, że praktycznie wszystkie operacje można uzyskać prostym “where" po jednej tabeli (tree_5) – join do nodes_5 służy tylko do tego by móc zwrócić coś poza samym id.

wady – nieoczywiste przenoszenie elementów. pewna nadmiarowość informacji.

co do przenoszenia elementów – kiedyś o tym pisałem, ale aby było wszystko w jednym miejscu:

zakładając, że mamy drzewo i w nim element o id X przenosimy tak aby był bezpośrednio pod Y, zapytania które to zrealizują wyglądają tak:

DELETE FROM tree_5 WHERE id IN (
                SELECT r2.id FROM tree_5 r1 JOIN tree_5 r2 ON r1.child_id = r2.child_id
                WHERE r1.parent_id = X AND r2.depth > r1.depth
                );
INSERT INTO tree_5 (parent_id, child_id, depth)
        SELECT r1.parent_id, r2.child_id, r1.depth + r2.depth + 1
        FROM
                tree_5 r1,
                tree_5 r2
        WHERE
                r1.child_id = Y AND
                r2.parent_id = X;

aha. oczywiście trzeba sprawdzić czy przenosiny elementu nie wygenerują pętli.

12 thoughts on “drzewa w sql’u – metoda pełnych ścieżek (metoda nr. 5 w/g starego tekstu)”

  1. rozwazanie fajne, ale przy duuze ilosci poziomow, i lisci drzewka, baza ma lekkie problemy z przenoszeniem elementow… konkretnie baza okolo 3500 userow, max depth okolo 9 ..

  2. dziwne. nie powinno być z tym problemów.

    możesz podać jakiś test-case? tabelkę powiązań i przenoszenie które wykonujesz?

    depesz

  3. oj. przepisz to może na takie przenoszenie jak podałem w poście. to trowje wygląda na strasznie skomplikowane i błędo-genne.

  4. Ta metoda bardzo dobrze się sprawdza np. do generowania menu liniowego w stylu breadcrumbs.
    Gorzej jeśli drzewko się chce wyświetlić w postaci zagnieżdżonych list (ul).
    W takim przypadku najlepiej wyświetlać rekurencyjnie.

    W jaki sposób uniknąć wielokrotnych zapytań?
    Jak dostać drzewko w postaci zagnieżdżonych tablic?

  5. @typografia:
    bezstresowo z tej metody możesz zrobić drzewgo na zagnieżdżeniach list.

    wystarczy:

    1. otwierać nowe (ul) jeśli poziom zagnieżdżenia elementu jest większy niż poziom poprzedniego

    2. zamykać (ul) gdy poziom nowego elementu jest mniejszy niż poprzedniego – tu jest o tyle trudniej, że trzeba zamknąć kilka (ul) – tyle o ile poziomów się różnią elementy.

    i to wszystko.

    trywiał.

  6. Skrypt super, szkoda tylko, że nie w mysql :/
    można się spodziewać kiedyś takiej wersji ?
    a już klasa php do obsługi wszystkiego to by był kosmos 😀

  7. @mosh:
    jak ktoś napisze to pewnie tak. ja raczej się za to nie zabiorę. nie używam mysqla ani nie piszę w php.

Comments are closed.