Hierarchiczna struktura
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.
//$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)).'<br/>';
if(count($right) - 1 > 0)
echo str_repeat('| ',count($right) - 1).'+- '.$item->name.'<br/>';
else
echo '+- '.$item->name.'<br/>';
$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 Categoriesbędzię czytał tabelę o tej samej nazwie. Ponadto rozszerzy funkcjonalność drzewa o dwie dodatkowe metody: prepareArray, prepareJson.
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.
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).
<?= isset($text)?$text:""; ?>
<?php
function htmlFromTree($tree,$step=0)
{
if ($step==0)
echo '<ul id="adoptme">';
if ($tree['leaf']==0)
{
echo '<li>'.$tree['text'].' ('.$tree['left'].','.$tree['right'].')';
echo '<ul>';
foreach ($tree['children'] as $item)
{
$step++;
htmlFromTree($item,$step);
$step--;
}
echo '</ul></li>';
}
else
echo '<li>'.$tree['text'].' ('.$tree['left'].','.$tree['right'].')';
if ($step==0)
echo '</ul>';
}
if (isset($tree))
htmlFromTree($tree[0]);
?>
Załączniki
Tree.php
Drzewo – Kohana
