Prawdopodobnie nieraz zdarzyło się wam budować drzewiaste struktury danych w bazach danych. Typowa tabela do tego celu wygląda mniej więcej tak:
id | parent_id | name ---+-----------+------------- 1 | 0 | Lorem 2 | 0 | Ipsum 3 | 1 | Dolor 4 | 1 | Sit 5 | 2 | Consectetuer 6 | 4 | Adipiscing 7 | 4 | Elit
Pozwala na dowolnie głębokie zagnieżdżanie danych, zaś obiekty o parent_id równym 0 są elementami najwyższego poziomu hierarchii.
Problem pojawia się, kiedy dane te trzeba zwizualizować w postaci drzewa. Początkujący programiści często używają do tego celu rekursji (właściwie, to używają jej do wszystkiego), jednak ma ona podstawową wadę. O ile w przypadku powyższej tabeli nie ma zasadniczo różnicy, czy dane będą pobierane rekurencyjnie czy liniowo, o tyle przy tysiącu kategorii, gdzie w najwyższym poziomie znajduje się ich kilkaset, liczba zapytań wywoływanych przez skrypt sięga setek na każde wyświetlenie strony.
Jest to problemem zwłaszcza, kiedy serwer SQL znajduje się na innej maszynie i każde zapytanie wymaga przesyłania danych w obie strony połączenia. Wprowadza to dodatkowe opóźnienia, a z czasem staje się nader widoczne.
Rozwiązaniem jest jednorazowe pociągniecie wszystkich potrzebnych danych za pomocą jednego zapytania, a następnie przebudowanie w strukturę drzewiastą po stronie serwera docelowego.
Jako przykład takiego działania posłużyć może poniższy skrypt PHP:
require_once('arraySort.class.php');
/**
* Create a tree structure from an SQL query
*/
class sqlTree
{
var $conn;
function sqlTree(&$conn)
{
$this->conn = & $conn;
}
/**
* Sort an array
* @access private
*/
function _multiSort(&$array, $key, $asc = true)
{
$sorter = & new arraySort($array, $key, $asc);
return $sorter->sortit();
}
/**
* Sort a tree
* @access private
*/
function _treeSort(&$item)
{
reset($item);
foreach($item as $key => $val)
{
if (isset($val['tree']))
$this->_treeSort($item[$key]['tree']);
}
$item = $this->_multiSort($item, 'sort', true);
}
/**
* Build the tree, elements with no known parent are ignored
* @param string SQL query, has to contain fields 'id' and 'parent_id'
* @param int parent_id to be considered root level
* @return array the tree structure
*/
function build($query, $root = 0)
{
$result = mysql_query($query, $this->conn);
$queue = array();
while($item = mysql_fetch_assoc($result))
{
array_push($queue, $item);
}
$queue = $this->_multiSort($queue, 'id', false);
$effect = array();
while($queue)
{
$found = false;
reset($queue);
$nextIter = $queue;
foreach($queue as $key => $item)
{
if ($item['parent_id'] != $root)
{
reset($nextIter);
foreach($nextIter as $keyTarg => $target)
if ($target['id'] == $item['parent_id'])
{
if (!isset($nextIter[$keyTarg]['tree']))
$nextIter[$keyTarg]['tree'] = array();
array_push($nextIter[$keyTarg]['tree'], $item);
unset($nextIter[$key]);
$found = true;
break;
}
if ($found)
break;
// not found
unset($nextIter[$key]);
}
else
{
array_push($effect, $item);
unset($nextIter[$key]);
break;
}
}
$queue = $nextIter;
}
$this->_treeSort($effect);
return $effect;
}
}
Jest to klasa, która jako parametr konstruktora pobiera identyfikator połączenia do bazy danych MySQL i udostępnia funkcję build(), która jako pierwszy parametr przyjmuje zapytanie wybierające dane, zaś jako drugi opcjonalny identyfikator korzenia drzewa.
Wymagania odnośnie zapytania są następujące: musi ono zawierać w wynikach kolumny o nazwach id, parent_id i sort, przy czym ten ostatni decyduje o kolejności pozycji drzewa. Dodatkowym ograniczeniem (powyższej implementacji) jest założenie, że dla każdego elementu zachodzi parent_id < id.
Przykładowe użycie:
$st = & new sqlTree($connection); $tree = $st->build( ' SELECT id, parent_id, name AS sort FROM przykladowa_tabela '); print_r($tree);
Do działania wymagany jest jeszcze plik arraySort.class.php, czyli skrypt sortowania wielowymiarowych tablic autorstwa Oliwiera Ptaka:
/**
* Handles multidimentional array sorting by a key (not recursive)
*
* @author Oliwier Ptak <aleczapka at gmx dot net>
*/
class arraySort
{
var $skey = false;
var $sarray = false;
var $sasc = true;
/**
* Constructor
*
* @access public
* @param mixed $array array to sort
* @param string $key array key to sort by
* @param boolean $asc sort order (ascending or descending)
*/
function arraySort(&$array, $key, $asc = true)
{
$this->sarray = $array;
$this->skey = $key;
$this->sasc = $asc;
}
/**
* Sort method
*
* @access public
* @param boolean $remap if true reindex the array to rewrite indexes
*/
function sortit($remap = true)
{
$array = &$this->sarray;
uksort($array, array(&$this, "_as_cmp"));
if ($remap)
{
$tmp = array();
while (list($id, $data) = each($array))
array_push($tmp, $data);
return $tmp;
}
return $array;
}
/**
* Custom sort function
*
* @access private
* @param mixed $a an array entry
* @param mixed $b an array entry
*/
function _as_cmp($a, $b)
{
//since uksort will pass here only indexes get real values from our array
if (!is_array($a) && !is_array($b))
{
$a = $this->sarray[$a][$this->skey];
$b = $this->sarray[$b][$this->skey];
}
//if string - use string comparision
if (!is_numeric($a) && !is_numeric($b))
{
if ($this->sasc)
return strcasecmp($a, $b);
else
return strcasecmp($b, $a);
}
else
{
if (intval($a) == intval($b))
return 0;
if ($this->sasc)
return (intval($a) > intval($b)) ? 1 : -1;
else
return (intval($a) > intval($b)) ? -1 : 1;
}
}
}
Zapraszam do analizy kodu. Zaproponowana implementacja nie jest oczywiście najdoskonalsza, ale służyć ma jedynie za przykład, że zadanie jest do rozwiązania bez stosowania rekursji w zapytaniach do bazy danych, co jest operacją bardzo kosztowną czasowo.
Wyciąganie wszystkich rekordów też nie jest najlepszym wyjściem, szczególnie gdy jest ich 50 000.
Są lepsze sposoby. Poczytaj najpierw
http://www.sitepoint.com/article/hierarchical-data-database
A potem:
http://fungus.teststation.com/~jon/treehandling/TreeHandling.htm
Pierwszy sposób jest gorszy bo przy dodawaniu nowych rekordów całe drzewo musi zostać uaktualnione.
Drugi sposób jest naprawdę rozsądnym kompromisem pomiędzy prostotą a wydajnością.
Ja mówię o sytuacji, kiedy TRZEBA wyciągnąć WSZYSTKIE rekordy tak czy tak. Cache'owanie też wymaga ich wyjęcia z bazy danych. Nie twierdzę, że powinno się je wyciągać za każdym odświeżeniem serwisu klienta.
Racja. Ale czasem jest też tak, że trzeba wygenerować powiedzmy ścieżkę do dokumentu:
Site.com > Artykuły > Kategoria > Artykuł1
Wtedy przydają się ww. techniki :)
Czasem też można utworzyć tak zapytanie by taką robotę odwalił serwer SQL po swojej stronie.
W mySQLu takie coś raczej nie przejdzie - za małe możliwości :(
Hehehe, właśnie… Dlatego kiedy pisałem zapytanie wyciągające trzypoziomowe menu i odpowiednio zaznaczające wybrane elementy, to musiałem się *nieźle* nagimnastykować - ale się udało :]
Dodam tylko, ze w Oracle bodajze od wersji 8 skladnia selecta jest rozszerzona o CONNECT BY.. PRIOR, ktore sluzy do budowania wyniku przez przechodzenie drzewa. Wygodne jak diabli.
A widzieliście zapytania budujące dokumenty XML w SQL Server? To jest wypas. ;D
A czego w takim przypadku używają nie-początkujacy programiści?
Vrok:
Iteracji, bo są szybsze i mają nieporównywalnie mniejszą złożoność obliczeniową i pamięciową.
No w tym przypadku to akurat pewnie jest możliwe (nie chce mi się w ten kod wgryzać…).
Ale bez rekurencji często jest bardzo ciężko i zamienia się ją na iterację tylko po to, żeby nie rósł stos systemowy (i w sumie algorytm zostaje ten sam, tylko że np. używając sterty jako stosu w jawny sposób). A skoro w PHP wzrostem stosu nie trzeba się przejmować, to chyba nie trzeba wystrzegać się rekurencji aż tak bardzo…
Chociaż nie mam pojęcia, jak ma się czas wywołania funkcji w PHP, więc mogę pleść głupoty.
DarkStar: akurat (de)serializacja do SQL Servera z poziomu XML jest bajecznie prosta, bo juz w wersji 2k mocno to rozbudowali, nie wspominajac o 2005.
>>A skoro w PHP wzrostem stosu nie trzeba się
>>przejmować, to chyba nie trzeba wystrzegać się rekurencji aż tak bardzo…
Jak to nie trzeba się przejmować? PHP nie zużywa pamięci?? To, że język ma automatyczne zarządzanie pamięcią nie znaczy, że programista nie musi dbać o wydajność.
p_ch: Ale jeśli w programie C używam realloc() zamiast niewidzialnie odkładających się zmiennych na stosie wraz z kolejnymi wywołaniami funkcji, to pamięć zużywa się w takich samych ilościach. :)
Tyle, że jak braknie miejsca na stos, to program się wysypie - a realloc po prostu przeniesie dane w inne miejsce.
A oczywiście PHP rekurencji w skryptach nie implementuje przez rekurencję (sprawdziłem! program w C wywalił się po kilkunastu tysiącach "okrążeń" rekurencji, a skrypt w PHP działał aż go nie zabiłem), więc nie trzeba się stosem systemowym przejmować. :)
Implementacja rekursywna to jedno, ale różnica w ilości zapytań do bazy jest kolosalna. Po pomnożeniu tego przez latencję połączenia wychodzi często kilkanaście sekund.
Co po niektórzy jak na mój gust zbuytnio demonizują rekurencję. Rekurencja jest ryzykowna przede wszystkim w kiepskich językach (czyli większości obecnie dominujących). LISP preferuje rekurencję i gardzi iteracją od końca lat 50. XX w. do dziś i nieźle na tym wychodzi.
Co zresztą nie zmienia faktu, że odwoływanie się do bazy danych w tym stylu to bezsens :) Twórcy Prevaylera twierdzą zresztą, że odwoływanie się *w ogóle* do bazy danych to najczęściej bezsens…
Jezuch:
Tylko że w językach typu SML czy LISP liczba przejść rekurencyjnych jest prosta do obliczenia i ma warunek stopu przed upływem całej pamięci :)
To najczęściej i tak zależy od zagadnienia. LISP używa rekurencji zamiast iteracji, w związku z czym liczba takich przypadków jest znacznie większa - w końcu iteracja jest wszędzie.
m: wiem, przecież używam. :) W mojej wypowiedzi nie było ironii.