Generowanie drzewa listy

Witam, mam pewien problem z logicznym rozwiązaniem sprawy generowania drzewa listy. Bazę danych odpytuję takim zapytaniem:

SELECT `id`,`txt`,`parent_id` FROM `baza`;

id - unikalne ID wpisu/rekordu z listy
parent_id - ID wpisu z jednego poziomu powyżej

Chciałbym wygenerować listę, która mogłaby wyglądać w ten przykładowy sposób:

• tekst 1
• tekst 2
• tekst 3
  -- tekst 3,1
  -- tekst 3,2
  --- tekst 3,2,1
  --- tekst 3,2,2
  -- tekst 3,3
  --- tekst 3,3,1
  --- tekst 3,3,2
• tekst 4
• tekst 5

itd... mam nadzieję, że w miarę zrozumiale to przedstawiłem, w razie czego użyję innego schematu. Cyfry dodałem tylko dla lepszego zobrazowania sprawy.

Problem w tym, że nie wiem jak zapytania z bazy posegregować i na początek utworzyć z nich tablicę, która przedstawi np. przy pomocy print_r takowy schemat (nie chodzi o konkretny zapis graficzny).

Zawartość bazy:

1|tekst|0
2|tekst|0
3|tekst|0
4|tekst|0
5|tekst|0
6|tekst|3
7|tekst|3
8|tekst|3
9|tekst|7
10|tekst|7
11|tekst|8
12|tekst|8

Właściwie nie chodzi mi o żaden gotowy kod, ale o samą wskazówkę jak logicznie tą sprawę rozwiązać... myślałem o tablicach, potem o odczycie tablic przez while+list+each, ale kompletnie nie potrafię tego ogarnąć, bardzo więc proszę o pomoc.

Pozdrawiam.

Żeby całość była bardziej graficznie zrozumiała to przedstawię to w taki sposób:

- owoce
- warzywa
- mięso
  -- wołowina
  -- drób
    --- skrzydełka
    --- udka
  -- wieprzowina
    --- karczek
    --- golonka
- nabiał
- napoje

i teraz zawartość bazy:

1|owoce|0
2|warzywa|0
3|mięso|0
4|nabiał|0
5|napoje|0
6|wołowina|3
7|drób|3
8|wieprzowina|3
9|skrzydełka|7
10|udka|7
11|karczek|8
12|golonka|8

Pozdrawiam.

Problem jaki napotkałeś z rysowaniem drzewa wynika głównie ze struktury bazy. Przechowujesz w tabeli parent_id - dzięki niemu można zbudować całe drzewo, ale jest to trudne - trzeba korzystać z rekurencji, a bazy danych nie mają mechanizmu rekurnecyjnych zapytań.

Trzeba zatem przechować w tabeli jakąś dodatkową informację na temat drzewa.
Są dwa najbardziej popularne rozwiązania:

1. Drzewa IP
   Do swojej tabeli baza dodajesz pole ip VARCHAR(100) NOT NULL. W tej kolumnie będzie przechowywana cała "ścieżka" (gałąź) do danego elementu hierarchii. Przykładowo dla elementu "skrzydełka" byłoby to 3.7.9 - czyli po kolei ID wszystkich elementów wyżej w hierarchii.
   Przydatne będzie też pole depth TINYINT UNSIGNED informujące o tym jak głęboko w hierarchii znajduje się dany element
   Wyświetlenie całego drzewa jak i jego fragmentu można wtedy zrealizować za pomocą jednego zapytania:

SELECT
    *
FROM
    baza
ORDER BY
    RPAD(ip, 70, '0')

A do zrobienia wcięć można się posłużyć polem depth.
Więcej na ten temat tutaj: http://blog.mwojcik.pl/2008/02/17/drzewa-kategorii-w-sql-i-php-metoda-ip/

RPAD w zapytaniu jest po to, żeby sortować wg IP, ale "jak po liczbach" a nie "jak po stringach" - długość IP nie ma znaczenia bo wszystkie stringi do sortowania mają tę samą długość

Minusem tej metody jest nieefektywne wyszukiwanie w górę hierarchii.

2. Znaczniki Left i Right
   Do swojej tabeli baza dodajesz 2 pola - left TINYINT UNSIGNED i right TINYINT UNSIGNED. W tym podejściu każdą gałąź drzewa można rozpatrywać jako worek na elementy drzewa. Liczby left i right to granice tego worka. Wszystkie elementy jakie znajdują się w worku (są niżej w hierarchii) mają swoje liczby left i right z zakresu między liczbą left elementu wyżej w hierarchii a liczbą right elementu wyżej w hierarchii.

Łatwiej będzie to zrozumieć tutaj: http://www.eioba.pl/a/3m/drzewa-w-php-i-mysql.

Wyświetlenie całego drzewa można zrealizować podobnym zapytaniem:

SELECT
    *
FROM
    baza
ORDER BY
   `left`

Myślę, że dodbrym pomysłem jet też trzymanie w tabeli pola depth - będzie łatwiej zrobić wcięcia.

Minusem tej metody jest konieczność UPDATEowania dużych ilości wierszy przy zmianie hierarchii - przy dużej tabeli może być powolne.

[Adam]

Dziękuję Adamie za garść przydanych informacji. Teraz mniej więcej wiem jak się za to zabrać, choć nie wiem jeszcze z której metody skorzystam.

Mam jeszcze takie pytanie, bo w Twojej podpowiedzi nakreśliłeś mi sytuację jak tą sprawę rozwiązać przy użyciu odpowiednich zapytań. Gdyby jednak sprawa wyglądała w ten sposób, że pierw jest wykonywane zapytanie, które wszystkie dane pobrane z tabeli są zapisywane w jakiejś tablicy już po stronie PHP i również po stronie PHP z tych danych będących w tablicy tworzone jest drzewo, to podejście do tematu się zmienia - być może są inne metody, czy mimo wszystko warto z Twojej rady/rad skorzystać?

Pozdrawiam, Matt.

W obu wariantach, które opisałem jako wynik zapytania otrzymałbyś posortowaną hierarchicznie tabelę, w której każdy wiersz zawierałby wartość depth, dzięki której wiedziałbyś jak głębokie wcięcia zrobić. W PHP zatem trzeba byłoby poiterować po całej tej tablicy i w zależności od pola depth zrobić odpowiednio głębokie wcięcia.

Gdybyś chciał narysować drzewo korzystając tylko z parent_id (bez zmieniania struktury) to wówczas nawet zakładając, że załadowałeś całą tabelę baza do pamięci, zadanie mocno się komplikuje. Trzeba by było zbudować w PHP wielowymiarową tablicę na podstawie parent_id. Jedyny sposób, jaki mi przychodzi do głowy, to utworzenie nowej (pustej) zmiennej, która będzie przechowywała ustrukturyzowaną hierarchię. Następnie wziąć pierwszy element tablicy pierwotnej, przenieść go do nowej i wyszukać w pierwotnej wszystkie jego dzieci. Każde dziecko przenieść (usunąć) z tablicy pierwotnej do nowej. W analogiczny sposób postąpić dla wszystkich elementów w tablicy, aż będzie pusta.

Reasumując: odradzam tę metodę, jest czasochłonna (dla PHP) i trudna od strony programisty - łatwo zrobić buga.

[Adam]