uwaga – ta metoda jest tylko i wyłącznie dla postgresql'a, gdyż wykorzystuje niestandarodwy typ danych obecny (jako moduł w contribie) jedynie w postgresie.

jak ltree działa nie będę opisywał bo od tego jest manual do ltree.

baza do ltree jest trywialna, przykładowo, oryginalne, testowe drzewo:

zapisujemy tak:

# create table tree_ltree (

id int4 primary key,

path ltree

);

po wstawieniu naszego testowego drzewa uzyskujemy taką zawartość tabelki:

ok. jak się pyta taką bazę?

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

select * from tree_ltree where path ~ '*{1}'

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

dane wejściowe:

• ID : id elementu

select  p.* from tree_ltree c join tree_ltree p on c.path <@ p.path where c.id = [ID] and c.path ~ cast(p.path::text || '.*{1}' as lquery)

zwracam uwagę, na to iż mając daną ścieżkę do elementu można mu po prostu wyciąć ostatni element (od kropki do końca) i w ten sposób uzyskać od razu ścieżkę do elementu nadrzędnego.

3. pobranie listy elementów bezpośrednio “pod" podanym elementem

dane wejściowe:

• ID : id elementu

select c.* from tree_ltree c join tree_ltree p on c.path <@ p.path where p.id = [ID] and c.path ~ cast(p.path::text || '.*{1}' as lquery);

zwracam uwagę, na to iż mając daną ścieżkę do elementu można mu po prostu dokleić do niej .*{1} i wykonać zapytanie:

select * from tree_ltree where path ~ [ZMODYFIKOWANA_SCIEZKA_PARENTA]

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

dane wejściowe:

• ID : id elementu

select  p.* from tree_ltree c join tree_ltree p on c.path <@ p.path where c.id = [ID] AND p.id <> [ID]

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

dane wejściowe:

• ID : id elementu

select c.* from tree_ltree c join tree_ltree p on c.path <@ p.path where p.id = [ID] AND c.id <> [ID]

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

dane wejściowe:

• ID : id elementu

select count(*) from tree_ltree c join tree_ltree p on c.path <@ p.path where p.id = [ID] AND c.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  p.* from tree_ltree c join tree_ltree p on c.path <@ p.path where c.id = [ID] and p.path ~ '*{1}'

jeśli chodzi o zalety – najważniejszą jest szybkość pisania, intuicyjność zapytań, możliwości (indeksowane wyszukiwanie np. elementów 2 poziomy poniżej dowolnego elementu którego nazwa zaczyna się od “dep") i czytelność danych.

wada jest zasadniczo tylko jedna – przenośność. jeśli kiedykolwiek w przyszłości będziecie przenosić bazę na coś innego niż postgres, to macie problem. no tak. tylko po co przenosić bazę na coś innego niż postgres?

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:

tabelka tree_5:
# select * from tree_5;

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.