drzewka sqlowe Opcje

[chmolu]

Witam,

Piszę ten temat bo ogarnęła mnie już całkowita niemoc. Próbuję zaimplementować jakiś sensowny algorytm drzewek do mojego CMFa. Nie chcę korzystać z Nested Sets (left, right), bo to kompletnie nie nadaje się do większych drzew.

Znalazłem coś takiego:
http://fungus.teststation.com/%7Ejon/treeh...reeHandling.htm

Metoda bardzo fajna, ale utknąłem na jednej bardzo istotnej rzeczy - wyświetlaniu drzewa. Teoretycznie, zgodnie z tym co piszą w artykule, by pobrać drzewo (lub daną część drzewa) wystarczy użyć zapytania:

Select Id from Path where AncestorId = 2

Przypuśćmy, że drzewo wygląda tak:

Kod

      rośliny (1)
        / \
      /     \
    /         \
  /             \
owoce(2)  warzywa(3)
    /
  /
banan(4)              

(gdzie cyfry w nawiasach to numery ID elementów -- 'banan' został dodany później niż 'warzywa'). W tym wypadku, używając powyższego zapytania dostanę:

Kod

Rośliny
    Owoce
    Warzywa
       Banan

Czy jest jakiś sensowny sposób, by pobrać odpowiednio posortowane drzewo korzystając z powyższego przykładu?

A może znacie jakieś inne efektywne sposoby przechowywania drzew w bazie danych? Zależy mi przede wszystkim na efektywności i elastyczności. Nested Sets odpadają (IMG:http://forum.php.pl/style_emoticons/default/tongue.gif)

[bigZbig]

Nested sets (zbiory zagnieżdżone) to ciekawy mechanizm nastawiony na mozliwie szybki odczyt drzewa. Dodawanie i modyfikowanie niestety wiaze sie z koniecznoscia aktualizacji indeksow przewaznie wiekszosci rekordow w tabeli. Nie objecie takich operacji transakcja grozi utrata spujnosci struktury.

Osobiscie eksperymentujac z ta metoda oprocz indeksow lewy i prawy zachowalem rowniez parent_id w celu ewentualnej rekurencyjnej odbudowy srtuktury. Dodalem tez pole level co ulatwilo mi wyswietlanie ograniczonej liczby zaglebien wybranej galezi. Dodalem tez pole position (mozna by je nazwac order) gdyz jego wartosc wskazuje na miejsce danego liscia lub galezi w ramach swojego poziomu. Dzieki temu wybiegowi zmiana pozycji w ramach poziomu wymaga jedynie aktualizacji wartosci position elementow tej samej galezi i na tym samym poziomie, a nie przebudowy calych indeksow lewy prawy. Poza tym w przypadku wystapienia niespojnosci struktury drzewa, ponowna przebudowa oparta o id, nie powoduje zmiany kolejnosci elementow w ramach poziomu

Na moim drzewie mozna:
- pobierac pojedynczy element, cale galezie,
- pobierac okreslona liczbe poziomow z drzewa lub wybranej galezi,
- pobierac przodkow wybranego elementu,
- pobrac przodkow o wybrana liczbe leweli w gore,
- dodawac nowe elementy,
- usuwac liscie i cale galezie,
- usuwac rodzica zachowujac jego potomkow,
- przesuwac liscie w ramach danego poziomu lub calego drzewa,
- przesuwac cale galezie w gore, dol, w prawo oraz w lewo
- odbudowac strukture drzewa w razie "powiklan"

Pisze artykul na ten temat (jakos nie mam czasu aby go dokonczyc) Jak mi uruchomia PHP5 na serwerze to wrzuce demo do przetestowania i dorzuce wspomniany artykul.

Mysle ze zrobilem fajny mechanizm jednak zdaje sobie sprawe z jego niedoskonalosci wynikajacych glownie ze wspomnianych juz wyzej trudnosci przy dodawaniu elementu lub modyfikacji struktury. Przy budowie np. forum o ograniczonej liczbie zaglebien, czestej aktualizacji tresci wybralbym raczej inne rozwiazanie - Drzewa Depesza, albo IP (tak na marginesie zastanawiam sie w polu jakiego typu w bazie trzymane sa id oraz sciezka danego elementu - w varchar czy raczej text?)
Co do zrzucania struktury drzewa do pliku to ja ograniczylbym sie jedynie (zresta podejrzewam, ze oto wlasnie chodzi) do zrzucenia id i parent_id i na tej podstawie konstruowal zapytanie do bazy danych.