Temat: Struktury Drzewiaste

Piotrze, to ty w końcu odpowiedziałeś na post Radosław Kropiwieca? Bo on zadał konkretne pytanie.

Temat: Struktury Drzewiaste

Alan B.:
Piotrze, to ty w końcu odpowiedziałeś na post Radosław Kropiwieca? Bo on zadał konkretne pytanie.

Wydawalo mi sie ze caly czas o tym dyskutujemy, ale po Twoim pytaniu nie jestem juz tego taki pewien...

Temat: Struktury Drzewiaste

o_O zwracam honor... dopiero teraz doczytałemw twojej wiadomości odwołanie do tego linku w eioba.
Przepraszam za zamieszanie.

Pomimo tego, że uważam, że tekst o pracy domowej był nazbyt protekcjonalny, czuję się teraz zobowiazany do odpowiedzi:

Algorytmu nie będę pisał, wystarczy informacja, że każde dziecko posiada pełną ścieżkę rodziców i to właśnie z niej można zapełnić lukę.

Temat: Struktury Drzewiaste

Alan B.:
o_O zwracam honor... dopiero teraz doczytałemw twojej wiadomości odwołanie do tego linku w eioba.
Przepraszam za zamieszanie.

Pomimo tego, że uważam, że tekst o pracy domowej był nazbyt protekcjonalny, czuję się teraz zobowiazany do odpowiedzi:

"Praca domowa" - bo to cos, co jest oczywiste (dzieki prostocie struktury) i dlatego malo interesujace...

Pozdrawiam!

Temat: Struktury Drzewiaste

Generalnie takie coś kto proponował ktoś wyżej czyli zapisywanie relacji jako

id | parent_id

to porażka.
Przy wyświetlaniu struktury rekurencyjne wywoływanie zapytań to samobójstwo na starcie.
Ja używam do tego celu struktury, która nosi nazwę Nested Tree.
Bardzo dobrze się sprawdza. Pozwala pobrać całość lub fragment struktury jednym zapytaniem, pozwala pobrać jednym zapytaniem ścieżkę od korzenia (lub innego poziomu) do określonego elementu struktury etc.
Jeszcze nie spotkałem się w swojej praktyce z problemem, którego nie dało by się w tej strukturze rozwiązać jednym selectem :-).

W strukturze chodzi o to, że dla każdego rekordu utrzymujemy następujące pola:

id | parent_id | level | left | right

Parent_id nie jest używane dla normalnego pobierania danych. Wykorzystuje się je do obliczania wartości pól level, left i right, które służą do pobierania danych.

Wyznaczanie wartości dla tych kolumn jest nieco skomplikowane.

level - pole oznacza głębokość węzła w drzewie.

left - to wartość liczbowa, która jest o jeden mniejsza niż najmniejsza wartość left w podwęzłach.

right - wartość o jeden większa od największej wartości right w podwęzłach.

dla każdego węzła right jest zawsze większe od left

Przykładowa struktura może wyglądać tak:

Węzeł 1, level: 1, left: 1, right: 10
-- Węzeł 1.1, level: 2, left: 2, right: 3
-- Węzeł 1.2, level: 2, left: 4, right: 7
---- Węzeł 2.2.1, level: 3, left: 5, right: 6
-- Węzeł 1.3, level: 2, left: 8, right: 9
Węzeł 2, level: 1, left: 11, right: 14
--Węzeł 2.1, level: 2, left: 12, right: 13

Oczywiście oprócz walet są też zady ;-)
Po pierwsze przy modyfikacji drzewa (nowy element, usunięcie etc.) rekonstrukcja struktury jest wymagająca obliczeniowo. Jest to o tyle mniej istotne, że jak wiadomo (w typowych zastosowaniach) modyfikacje drzewa będą operacjami marginalnymi wobec ich odczytu.

Druga wada to to, że czasem chcemy aby w zależności od potrzeb sortować węzły w poszczególnych gałęziach w różny sposób (według kolejności, daty, nazwy itd.). Normalna struktura Nested Tree pozwala sorotwać tylko według jednego pola ponieważ sortowanie jest z góry zaszyte w polach nadmiarowych struktury (według któreych następuje efektywne sortowanie).
Da się to rozwiązać aczkolwiek jest to kłopotliwe. Trzeba powiem dla każdego sposobu sortowania mieć odrębne pola Left i Right struktury.

Temat: Struktury Drzewiaste

Wojciech Małota:
Generalnie takie coś kto proponował ktoś wyżej czyli zapisywanie relacji jako

id | parent_id

to porażka.
Przy wyświetlaniu struktury rekurencyjne wywoływanie zapytań to samobójstwo na starcie.

i jeszcze pytanie Wojciecha Sznapki:

Jak jednym (o ile się da) zapytaniem pobrać ścieżkę parentów mając
id liścia? Np
folder1
--folder2
----folder3
------liść

Na przyklad w Oracle jest taka konstrukcja selecta ktora pozwala jednym zapytaniem wyciagnac wszystkie elementy drzewa poczawszy od zadanego korzenia (w dol) lub od liscia w gore do korzenia.

Przyklad:
PK, , FK)
tabela (tbl_id, tbl_name, tbl_tbl_id)

Od korzenia (dowolnego w drzewie) w dol z wszystkimi elementami:
select tbl_id from tabela
connect by prior tbl_id = tbl_tbl_id
start with tbl_id = :id_korzenia

Od liscia w gore do korzenia:
select tbl_id from tabela
connect by prior tbl_tbl_id = tbl_id
start with tbl_id = :id_liscia

Ogolnie konstrukcja id, parent_id z kluczem obcym (ochrona przed skasowanie pewnego poziomu drzewa) + indeksy bardzo ladnie dziala i to dla duzych drzew i jest bardzo prosta (przepinanie rodzicow/lisci, usuwanie, itp).

PozdrawiamTomasz Żak edytował(a) ten post dnia 30.07.08 o godzinie 11:01

Temat: Struktury Drzewiaste

Jak jednym (o ile się da) zapytaniem pobrać ścieżkę parentów mając
id liścia? Np
folder1
--folder2
----folder3
------liść

W MySQLu itp. jednym się nie da potrzebne są dwa.

1. Najpierw pobieramy wartość NestedLeft i NestedRight dla liścia:

select @NestedLeft := NestedLeft, @NestedRight := NestedRight from Table where Id = @ChildId;

Edit: Da się jednym zapytaniem ale wtedy ono będzie zawierało dodatkowo dwa zapytania zagnieżdżone co będzie mniej efektywne.

2. Drugim zapytaniem ściągamy ścieżkę:

select * from Table where NestedLeft <= @NestedLeft and NestedRight >= @NestedRight order by NestedLeft;Wojciech Małota edytował(a) ten post dnia 30.07.08 o godzinie 11:11