Drzewa w PHP
Zaimplementowanie drzewiastej struktury z wykorzystaniem baz danych takich jak MySQL czy PostgreSQL nie jest trudnym zadaniem. Już po chwili zastanowienia przychodzi nam na myśl koncepcja, w której każdy element wskazuje na swojego rodzica. W implementacji tego drzewa potrzebujemy tylko dwa dodatkowe pola: id, parent_id. Przy wczytywaniu całości posługujemy się rekurencją. Skoro mamy tak przystępne rozwiązanie problemu czy warto poszukiwać czegoś innego? Jak najbardziej. O tym właśnie sobie pomówimy.
Można szybciej
Tradycyjne podejście ma jedną zasadniczą wadę. Zmusza nas abyśmy wykonali wiele zapytań do systemu bazodanowego. W prostych przypadkach jest to do zaakceptowania ale im większe mamy drzewo tym bardziej odczujemy skutki takiego wyboru. Z prostą reorganizacją zapisu drzewa możemy sytuację radykalnie poprawić.
Na rysunku zaprezentowałem drzewo z dodatkowymi parametrami left i right. Jeśli dany węzeł nie posiada potomka to jego wartość right jest większa od left o 1. Jeśli węzeł jest rodzicem jego parametr right musi być wystarczająco duży by pomieścić potomków. Dzięki takiej strukturze jesteśmy w stanie „poprosić” bazę danych o wszystkich potomków danej gałęzi za sprawą jednego zapytania.
SELECT * FROM `tree` WHERE `left` BETWEEN 1 AND 10 ORDER BY `left` ASC;
W wyniku zapytania otrzymujemy już posortowane dane. Możemy je wykorzystać w celu wyświetlenia drzewa. Poniżej prezentuję przykładowy kod PHP.
<?php
//$result - wynik zapytania
$right = array();//stos
foreach($result as $item)
{
if(count($right) > 0)
while($right[count($right)-1] < $item->right)
array_pop($right);
echo str_repeat('| ',count($right)).'';
if(count($right) - 1 > 0)
echo str_repeat('| ',count($right) - 1).'+- '.$item->name.'';
else
echo '+- '.$item->name.'';
$right[] = $item->right;
}
Nie ma róży bez kolców. Nasze metoda jest bardzo szybka podczas czytania drzewa. Sama modyfikacja (przeniesienie/dodanie/usunięcie elementu) wymaga jednak sporego nakładu pracy. Każdemu z węzłów musimy zaktualizować parametry left i right. Ze swojego doświadczenia mogę zaproponować przechowywanie pomocniczego pola parent_id. Wtedy wszystkie czynności związane z przebudową są dużo prostsze w implementacji. Znając samą idee wierzę że jesteś w stanie napisać w tym celu odpowiednie funkcje samodzielnie.
Klasa Tree
Aby ułatwić sobie życie napisałem klasę upraszczającą korzystanie z drzewa. Zastosowałem w niej opisaną metodę. Zależało mi nie tylko na optymalizacji ale i elastyczności klasy. W wielu miejscach zrezygnowałem z przyśpieszenia kodu na rzecz wygody narzędzia. Klasa jest kompatybilna z Kohaną. Nie obsługuje jednak ORM. Jeśli zależy Ci na tej funkcjonalności polecam inne kompleksowe rozwiązanie.
Klasę dodajemy do naszego projektu wraz z przeniesieniem pliku Tree.php do katalogu/application/libraries/.
Publiczne metody:
- hasDescendants() – sprawdza czy węzeł posiada potomków.
- getChildren() – pobiera listę dzieci.
- getParent() – pobiera rodzica. Jeśli go nie ma zwraca false.
- getRoot() – pobiera korzeń.
- getDepth() – sprawdza jak głęboko znajduje się dany węzeł. Zwraca liczbę całkowitą.
- getPath($reverse=false) – pobiera tablicę elementów prowadzących do danego węzła. Kolejność może zostać odwrócona (domyślnie false).
- getNodeById($id) – odszukuje węzeł o podanym identyfikatorze. Przeszukiwana jest lista potomków danego węzła.
- move($item,$order=0,$parent=-1) – przenosi lub zmienia kolejność węzła. Metodę należy aktywować na korzeniu drzewa (id=parent_id). Argument $item oznacza przenoszoną gałąź. Jeśli parametr $item podamy jako liczbę uprzednio zostanie odszukany węzeł. Argument $order oznacza nową kolejność w danym rodzicu. Ostatni parametr umożliwia zmianę rodzica(domyślnie zasugerowany jest ten sam).
- insertItem($parent=-1) – dodajemy nowy węzeł. Domyślnie w korzeniu. Możemy manipulować miejscem pojawienia się dziecka za sprawą argumentu $parent.
- removeItem($item) – kolejna metoda obok move, insertItem, update, którą uruchamiamy dla korzenia. Parametr $item oznacza usuwany element.
- update($item) – zapisuje zmodyfikowane wartości podanego w argumencie węzła.
Klasa Tree posiada jeszcze jedną bardzo ważną właściwość: protected $table=””;. Jest to zmienna określająca tabelę, z której zostanie wczytane drzewo. Wraz z dziedziczeniem klasy nadpiszemy tą wartość. Wspomnijmy o samej tabeli. Narzuciłem konieczność istnienia pól: id, left, right, parent_id. Co jeśli chcesz mieć dodatkowe wartości? Żaden problem. Po prostu je dodaj klasa sama zadba o ich wczytywanie oraz zapisywanie. Przypominam że wszystkie zmiany na drzewie wykonujemy względem korzenia. Ten cechuje się id=parent_id.
Pora zająć się samym modelem dziedziczącym po naszej klasie Tree. Model Categories będzię czytał tabelę o tej samej nazwie. Ponadto rozszerzy funkcjonalność drzewa o dwie dodatkowe metody: prepareArray, prepareJson.
<?php
class Categories_Model extends Tree
{
protected $table = 'categories';
public function prepareJson()
{
return json_encode($this->prepareArray());
}
public function prepareArray($step=0,$temp=NULL,$childNodes=NULL,$child=NULL)
{
if ($step==0)
{
$child = $this;
$temp = array();
$temp['draggable'] = false;
}
$temp['id'] = $child->id;
$temp['text'] = $child->text;
$temp['left'] = $child->left;
$temp['right'] = $child->right;
$temp['leaf'] = !$child->hasDescendants();
$temp['cls'] = $child->hasDescendants() ? 'folder':'file';
if ($child->hasDescendants())
{
$temp['children'] = array();
$children = $child->getChildren();
foreach ($children as $child)
{
$step++;
$this->prepareArray(&$step,&$temp['children'][],$children,$child);
$step--;
}
}
if ($step==0)
return array($temp);
}
}
Kontroler obsługujący nasz model.
<?php
class Welcome_Controller extends Controller
{
private $categories;
public function __construct()
{
parent::__construct();
$this->template = new View('template');
$this->template->body = new View('welcome');
$this->categories=new Categories_Model();//domyślnie wczytujemy węzeł o id=1
}
public function index()
{
$this->template->body->tree = $this->categories->prepareArray();
$this->template->render(TRUE);
}
public function add($id)
{
$item = $this->categories->insertItem($id);
$item->text = "nowy".$item->id;
$this->categories->update($item);
url::redirect(url::base());
}
public function remove($id)
{
$this->categories->removeItem($id);
url::redirect(url::base());
}
public function up($id)
{
$this->categories->move($id,0);
url::redirect(url::base());
}
}
Widok wyświetlający drzewo (welcome).
<?php
function htmlFromTree($tree,$step=0)
{
if ($step==0)
echo '';
if ($tree['leaf']==0)
{
echo ''.$tree['text'].' ('.$tree['left'].','.$tree['right'].')';
echo '';
foreach ($tree['children'] as $item)
{
$step++;
htmlFromTree($item,$step);
$step--;
}
echo '';
}
else
echo ''.$tree['text'].' ('.$tree['left'].','.$tree['right'].')';
if ($step==0)
echo '';
}
if (isset($tree))
htmlFromTree($tree[0]);
Załączniki
Do następnego razu.
Komentarze
Chcę dodać komentarzlukaskolista26-08-2010
Wlasnie tego szukalem :)
siutek06-11-2013
zaimplementowalem taką strukturę jakiś czas temu na jednej ze swoich stron. jednak ciśnie mi się jedno pytanie na język: – co w sytuacji, gdy chcę wyciągnąć z bazy bezpośrednie dzieci (bez dalszych zagłębień) danego poziomu? nie dany poziom, tylko dzieci tego poziomu? bez kilku zapytań ani rusz! :-)
Marcin Baszczewski08-11-2013
Klasa przedstawiona na tej podstronie ładuje wskazane drzewo/gałąź od razu wraz z potomkami. Większość metod opiera się na już wczytanych danych. Jeśli natomiast dysponujesz własną implementacją tego typu drzewa i pytasz wyłącznie o zapytanie SQL, które załaduje konkretną gałąź ale bez potomków, jak najbardziej jest to możliwe. Polecam Ci uprzednio jednak dodać kolumnę `level` oznaczającą poziom kolejnych zagłębień. Jeśli będziesz nią dysponował w zapytaniu bez problemu wydobędziesz wpisy nawet o wskazanej głębokości (pisane z głowy):
SELECT * FROM `tree` WHERE `left` BETWEEN :OD AND :DO AND `level`<=(:aktualny+:jak_gleboko);