Drzewo kategorii i wyciąganie danych Opcje

[zaksmok]

Witam serdecznie. Stoję przed ciężkim problemem jakim jest drzewo kategorii.
Aktualnie korzystam z nested sets + parent_id

Jaki problem?

Mając następującą strukturę:

[PHP] pobierz, plaintext 
- Kategoria 1
	- Sub 1.1
		- SubSub 1.1.1
		- SubSub 1.1.2
			- SubSubSub 1.1.2.1
			- SubSubSub 1.1.2.2
			- SubSubSub 1.1.2.3
	- Sub 1.2
		- SubSub 1.2.1
		- SubSub 1.2.2
	- Sub 1.3
- Kategoria 2
	- Sub 2.1
		- SubSub 2.1.1
		- SubSub 2.1.2
	- Sub 2.2
	- Sub 2.3
- Kategoria 3
	- Sub 3.1
	- Sub 3.2
	- Sub 3.3
- Kategoria 4
- Kategoria 5
[PHP] pobierz, plaintext 

będąc w kategorii Sub 1.2 powinienen widzieć:

[PHP] pobierz, plaintext 
- Kategoria 1
	- Sub 1.1
	- Sub 1.2
		- SubSub 1.2.1
		- SubSub 1.2.2
	- Sub 1.3
- Kategoria 2
- Kategoria 3
- Kategoria 4
- Kategoria 5
[PHP] pobierz, plaintext 

a będąc w kategorii SubSubSub 1.1.2.2

[PHP] pobierz, plaintext 
- Kategoria 1
	- Sub 1.1
		- SubSub 1.1.1
		- SubSub 1.1.2
			- SubSubSub 1.1.2.1
			- SubSubSub 1.1.2.2
			- SubSubSub 1.1.2.3
	- Sub 1.2
	- Sub 1.3
- Kategoria 2
- Kategoria 3
- Kategoria 4
- Kategoria 5
[PHP] pobierz, plaintext 

Próby skończyły się na następującym zapytaniu:

[SQL] pobierz, plaintext 
SELECT * FROM categories WHERE parent_id IN(NULL, 1) OR lft BETWEEN 3 AND 7)
[SQL] pobierz, plaintext 

Przy takim zapytaniu muszę znać:
1. ID głównej gałęzi w nested sets (null lub id = 1, w zależności od struktury nested sets)
2. ID najwyższego rodzica otwartej kategorii (w moim zapytaniu id=1)
3. LFT i RGT najwyższego rodzica kategorii.

Dla struktury

[PHP] pobierz, plaintext 
- Kategoria 1
	- Sub 1.1
		- SubSub 1.1.1
			- SubSubSub 1.1.1.1
			- SubSubSub 1.1.1.2
			- SubSubSub 1.1.1.3
		- SubSub 1.1.2
			- SubSubSub 1.1.2.1
			- SubSubSub 1.1.2.2
			- SubSubSub 1.1.2.3
	- Sub 1.2
		- SubSub 1.2.1
		- SubSub 1.2.2
	- Sub 1.3
- Kategoria 2
	- Sub 2.1
		- SubSub 2.1.1
		- SubSub 2.1.2
	- Sub 2.2
	- Sub 2.3
- Kategoria 3
	- Sub 3.1
	- Sub 3.2
	- Sub 3.3
- Kategoria 4
- Kategoria 5
[PHP] pobierz, plaintext 

bedąc w SubSubSub 1.1.2.1 powinienen otrzymać

[PHP] pobierz, plaintext 
- Kategoria 1
	- Sub 1.1
		- SubSub 1.1.1
		- SubSub 1.1.2
			- SubSubSub 1.1.2.1
			- SubSubSub 1.1.2.2
			- SubSubSub 1.1.2.3
- Kategoria 2
- Kategoria 3
- Kategoria 4
- Kategoria 5
[PHP] pobierz, plaintext 

[SQL] pobierz, plaintext 
SELECT * FROM categories WHERE parent_id IN (NULL, 1, 2) OR lft BETWEEN 7 AND 10
[SQL] pobierz, plaintext 

czyli muszę znać:
1. ID każdego rodzica
2. LFT i RGT najniższego rodzica

i to już mnie przerasta... Może znacie jakiś sprytny sposób na to?

Ten post edytował zaksmok 25.02.2010, 09:37:44

[wiiir]

a jakie masz tabele?

jedna tabela z 4 kolumnami, gdzie kazda kolumna odpowiada za poziom?

Ja jestem zwolennikiem ze nie trzeba sie bac towrzenia i wizania ze soba tabel, wiec zrobil bym 4 table bo mamy 4 kategorie
daje mi to przejrzystosc tabel, zapytan i kodu, wkoncu dlatego bazy nazywaja sie relacyjnymi

[SQL] pobierz, plaintext 
1 petla
    warunek
    2 petla
       wrunek
       3 petla
          warunek
          4 petla
[SQL] pobierz, plaintext 

moze ktos powiedziec boze ile zapytan po co itd.. ja wiem z doswiadczenia (oracle+ bardzo duza baza) ze takie zapytania beda wykonywac sie szybiej niz jedno wielkie ktore moze zapchac serwer jak jest zle napisane, w tym ukladnie mozna dodawac odpowiednie warunki kiedy jaki poziom sie wyswietla i dla kogo.. + wile innych plusow

[zaksmok]

gałęzie nie będą aż tak duże, maks 500 rekordów. Wszystko jest w jednej tabeli, struktura nested sets.

[VegetaSSJ]

Ja jestem zwolennikiem ze nie trzeba sie bac towrzenia i wizania ze soba tabel, wiec zrobil bym 4 table bo mamy 4 kategorie
daje mi to przejrzystosc tabel, zapytan i kodu, wkoncu dlatego bazy nazywaja sie relacyjnymi

OMG

Może to ci pomoże:

http://www.phpclasses.org/browse/package/1374.html
http://articles.sitepoint.com/article/hier...l-data-database
http://www.edutech.ch/contribution/nstrees/index.php

Poza tym na moje oko wszystkie kategorie powinny być opakowane jeszcze w nadrzędny element, np root.

[ayeo]

Witam!

@wiiir, to co proponujesz to jakiś absurd. Dobrych implementacji drzewek jak kilka. Można wybrać coś dla siebie w zależności od potrzeb i trudności. Jak w Twoim pomyśle będziesz realizował przeszukiwanie gałęzi lub przenoszenie? BTW relacją nie jest trzymanie danych tego samego rodzaju w 15 tabelkach.

Co do tematu wątku, mogę polecić jeszcze tzw Drzewka Depesza. Bez trudu znajdziesz w Google materiały. Jest to modyfikacja drzewek IP (taka bardziej zmiana optymalizacyjna). W drzewkach IP chodzi o to, że oprócz id rodzica trzymasz całą ścieżkę jeszcze (np 1.23.345.1224, parent to 1224, kategoria główna to 1). Drzewek LEFT-RIGHT nie mogłem nigdy zrozumieć. Tzn ich fenomenu.

Pozdrawiam!

[Methestel]

Problem ciekawy ale rozwiązanie jest dość proste.

Pola przykładowej tablicy 'tbl_tree'
- id
- parent_id
- n_left
- n_right
- level (liczba naturalna informująca o poziomie elementu w drzewie)

Kolumna "level" jest opcjonalna ale zawsze ją dodaję bo znacznie ułatwia wiele operacji na tablicy.



Zapytanie które wyciąga Ci id-ki wszystkich potomków elementu o id = :id już znasz i dla mojej przykładowej tabeli wygląda tak:

[SQL] pobierz, plaintext 
SELECT    *
  FROM       tbl_tree
  WHERE     (n_left > (SELECT n_left FROM tbl_tree WHERE id = :id)
    AND         n_right < (SELECT n_right FROM tbl_tree WHERE id = :id))
[SQL] pobierz, plaintext 

Zapytanie które wyciągnie Ci id-ki wszystkich rodziców elementu o id = :id wygląda identycznie z dwiema drobnymi różnicami (znaki '>' i '<' zamieniły się miejscami):

[SQL] pobierz, plaintext 
SELECT    *
FROM       tbl_tree
WHERE     (n_left < (SELECT n_left FROM tbl_tree WHERE id = :id)
  AND         n_right > (SELECT n_right FROM tbl_tree WHERE id = :id))
[SQL] pobierz, plaintext 

Żeby wyciągnąć n_left i n_right (u Ciebie LFT i RGT) najniższego rodzica przeszukujesz wynik poprzedniego zapytania w poszukiwaniu wiersza o najwyższej wartości 'level' lub robisz nowe zapytanie do bazy danych:

[SQL] pobierz, plaintext 
SELECT    n_left, n_right 
  FROM       tbl_tree
  WHERE     (n_left < (SELECT n_left FROM tbl_tree WHERE id = :id)
    AND         n_right > (SELECT n_right FROM tbl_tree WHERE id = :id))
ORDER BY level DESC
LIMIT       1
[SQL] pobierz, plaintext 

[Crozin]

Drzewek LEFT-RIGHT nie mogłem nigdy zrozumieć. Tzn ich fenomenu.

Cały ich fenomen polega na tym, że część operacji wykonuje się na nich o wiele łatwiej - część oczywiście trudniej. Jest to po prostu kolejna implementacja tego samego mająca swoje wady i zalety.

[cudny]

A ja bym to rozwiązał rekurencyjnie:
http://forum.php.pl/index.php?showtopic=133135&hl=

pzdr
Cudny