drzewa w sql’u – ltree

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:

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

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?

7 thoughts on “drzewa w sql’u – ltree”

  3. Jak np sortować gałęzie w ltree?

    10:12 cojack: i think you will need to sort on subltree(path, 0, nlevel(path)-2), sort;

    Pamiętasz? Prawie działa, ale nie zwraca oczekiwanego rezultatu, mógłbyś przedstawić w jaki prawidłowy sposób posługiwać się ltree w sql? Nigdzie tego nie ma opisanego, dzięki Twojej pomocy z sql mógłbym w końcu napisać implementację tej struktury w php.

    Doszedłem do takiej wersji:

    SELECT id, subpath(path, -1) as title, nlevel(path) as depth, sort FROM tree ORDER BY subltree(path, 0, nlevel(path)) ASC, sort ASC;

    Ale niestety nie uwzględnia drugiej kolumny sortującej, więc nie sortuje mi drzewa w gałęziach tylko po patchu. Naprawdę nie wiem jak sobie z tym poradzić, pisałem do autora, ale w dalszym ciągu zero odpowiedzi z jego strony… Także liczę na Ciebie.

    Pozdrawiam.

  4. @cojack: wrzuc gdzies (na jakiegos pastesite’a) przyklad danych ktore masz, jak ci sie teraz sortuja, i jak chcialbys by sie sortowaly. tak 5-10 rekordow.

  6. Query:

    WITH RECURSIVE rec AS (
    SELECT *, btrim(to_char( sort, '0000000' )) AS ordering FROM tree WHERE nlevel(path) = 1
    UNION ALL
    SELECT t2.*, t1.ordering || '/' || btrim(to_char( t2.sort, '0000000' )) AS ordering FROM rec t1, tree t2 WHERE t1.path @> t2.path AND nlevel(t1.path) + 1 = nlevel(t2.path)
)
SELECT id, subpath(path, -1) AS title, nlevel(path) AS depth, sort FROM rec ORDER BY ordering;

    But I think that it would be *much* better to add ordering column to your table, and fill it using triggers.

Comments are closed.