July 2nd, 2007 by depesz | Tags: | 12 comments »
Did it help? If yes - maybe you can help me?

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.

  1. 12 comments

  2. # Acid
    Jul 3, 2007

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

  3. Jul 3, 2007

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

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

    depesz

  4. # Acid
    Jul 10, 2007

    ok wina chyba po mojej genialnyej funkcji do przenoszenia drzewka ;]

    pisalem to jak zaczynalem sie bawic postgresem i wyglada to tak:

    http://phpfi.com/248681

    ale dziala

  5. Jul 10, 2007

    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.

  6. Dec 2, 2008

    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?

  7. Dec 2, 2008

    @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ł.

  8. # trawka
    May 22, 2009

    tak, tylko jak uzyskac odpowienio posortowany wynik z bazy?

  9. May 22, 2009

    @trawka
    https://www.depesz.com/2008/04/11/my-take-on-trees-in-sql/

  10. Jul 20, 2009

    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 😀

  11. Jul 20, 2009

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

  12. # Lukis
    Sep 2, 2009

    wersja mysql:
    http://diabl0.gazeta.ie/2009/03/drzewo-depesza-w-mysql/

  13. # Krzysiek
    Jan 20, 2011

    Wersja w MySQL: http://4programmers.net/Z_pogranicza/Zaawansowane_drzewa_w_MySQL

Leave a comment