MatheW’s blog

Drzewa kategorii w relacyjnych bazach danych to ciekawy temat. Różnych implementacji takich drzew jest wiele, ale żadna nie jest idealna – istotna jest łatwość w modyfikacji drzewa, szybkość pobierania danej gałęzi do wyświetlania, czy zliczania podkategorii w gałęzi.

Jak wspomniałem implementacji jest wiele – poczynając od podstawowego lecz nieoptymalnego rozwiązania z polem identyfikacyjnym rodzica, po nested sets czy metodę depesza. Część z nich opisanych jest tutaj.

Mi jednak spodobał się jeszcze inny sposób - Materialized Path AKA drzewka ip.

Drzewka IP

Metoda ta opiera się na takim założeniu, że każdy rekord ma pole o nazwie np. ip składające się z numerów identyfikacyjnych kolejnych kategorii nadrzędnych rozdzielonych kropką np. 1.12.45 – podobnie jak adresy IP. To pole mówi nam, że rekord o id 45 jest podkategorią elementu o id 12, którego rodzicem jest kategoria o id 1. W zasadzie pole to wystarczyłoby nam ale ułatwimy sobie przyszłe działania na drzewie dodając pole depth oznaczające głębokość elementu w drzewie a także parentID, pozwalające na łatwe otrzymanie kategorii rodzica, bez czasochłonnego rozbijania klucza ip.

Przykład

Aby utworzyć odpowiednią tabelę wykonujemy taki kod SQL:

CREATE TABLE `kategorie` (
`id` INT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY ,
`name` VARCHAR( 255 ) NOT NULL ,
`ip` VARCHAR( 255 ) NOT NULL ,
`parentID` INT UNSIGNED NOT NULL ,
`depth` INT UNSIGNED NOT NULL
)

W takiej tabeli rekordy są reprezentowane tak:

Teraz nalezy przedstawić sposoby najczestszych operacji na drzewie. Dla uproszczenia przykładów korzystam z nieobiektowego interfejsu MySQL, bez dbania o bezpieczeństwo zapytań.

Dodawanie elementu drzewa

$parent=array('id'=>3, 'name'=>'Linux', 'ip'=>'1.3', 'parentID'=>1, 'depth'=>2);
$cat=array('name'=>'Ubuntu');

mysql_query('INSERT INTO kategorie SET name="'.$cat['name'].'", parentID="'.$parent['id'].'", depth="'.($parent['depth']+1).'"');
$id=mysql_insert_id(); #pobranie id nowo powstałego elementu

mysql_query('UPDATE kategorie SET ip="'.$parent['ip'].'.'.$id.'" WHERE id="'.$id.'"');

Potrzebne są tu dwa zapytania, gdyż do ip niezbędny nam jest id nowego elementu, który pobieramy za pomocą mysql_insert_id(). Warto przed dodaniem elementu zablokować zapis w bazie danych, by inny skrypt nam w niej nie pomieszał, za pomocą polecenia

LOCK TABLES kategorie WRITE

a po całej operacji

UNLOCK TABLES

Pobieranie i wyświetlanie drzewa

Pobrać drzewo możemy poprzez szukanie takich rekordów, których ip zawiera ip rodzica:

$q=mysql_query('SELECT * FROM kategorie WHERE ip LIKE CONCAT("'.$cat['ip'].'.%")');
$categories=array();
while($r=mysql_fetch_assoc($q)){
	$categories[$r['parentID']][$r['id']]=$r;
}

W celu łatwiejszego wyświetlenia drzewa, jego elementy umieszczamy w takiej tablicy (nazwy kategorii to odpowiednie rekordy bazy zrzucone do tablicy):

Aby wyświetlić takie drzewo musimy stworzyć specjalną funkcję rekurencyjną, która w każdym przebiegu wyświetli wszystkie elementy podrzędne z danego elementu.

/**
 * Wyswietla galaz drzewa
 *
 * @param int $parentID id kategorii nadrzednej ktorej dzieci chcemy wyswietlic
 * @param array $tab tablica z kategoriami
 */
function display($parentID, $tab) {
	if (!is_array($tab[$parentID])) return; #czy kategoria ma podkategorie?
	echo '<ul>';
	foreach ($tab[$parentID] as $element) { #iteracja podkategorii
		echo '<li>'.$element['name'];
		display($element['id'], &$tab); #wyswietlenie podkategorii
		echo '</li>';
	}
	echo '</ul>';

}

Przypuśćmy, że pobraliśmy wszystkie elementy – zaczynamy od kategorii o id równym 0. Wywołujemy funkcję z parametrem 0 jako parentID czyli display(0, $tab). Funkcja przeszukuje tablicę $tab[0] i wyświetla zawierające się w niej elementy, dodatkowo dla każdego elementu wywołuje siebie samą, z tym, że zmienia parametr parentID na id danego elementu – przy wyświetlaniu elementu Windows przekazuje parametr 2 i przechodzi do tablicy $par[2]. Poprzez to iteruje i wyświetla każdą kategorię.

Pole depth jest przydatne gdy np. chcemy wyświetlić kategorie o ograniczonej głębokości, chociażby jedynie bezpośrednie podkategorie.

mysql_query('SELECT * FROM kategorie WHERE ip LIKE CONCAT("'.$cat['ip'].'.%") AND depth="'.($cat['depth']+1).'" ORDER BY ip');

Jego przydatność można docenić także przy wyświetlaniu kategorii – powiedzmy, że chcemy by kategorie były wyświetlane w taki sposób:

Unix
   Linux
      Ubuntu
      Slackware
   BSD
Windows
   Windows XP
   Windows 98

Wykonamy to dzięki takiemu kodowi:

function display($parentID, $tab) {
	if (!is_array($tab[$parentID])) return; #czy kategoria ma podkategorie?
	foreach ($tab[$parentID] as $element) { #iteracja podkategorii
		echo '<option value="'.$element['id'].'">'.str_repeat('&nbsp;&nbsp;&nbsp;', $element['depth']).$element['name'].'</option>';
		display($element['id'], &$tab); #wyswietlenie podkategorii
	}
}

Przenoszenie kategorii

$newparent=array('id'=>3, 'name'=>'Linux', 'ip'=>'1.3', 'parentID'=>1, 'depth'=>2);
$cat=array('id'=>2, 'name'=>'Windows', 'ip'=>'2', 'parentID'=>0, 'depth'=>1);

if ($cat['depth'] > $newparent['depth'])
                $set_depth= 'depth-' . ($cat['depth'] - $newparent['depth'] - 1); # o tyle ma sie zmieniac depth
            else if($cat['depth'] == $newparent['depth'])
                $set_depth= 'depth+1';
            else $set_depth= 'depth+' . ($newparent['depth'] - $cat['depth'] + 1); # o tyle ma sie zmieniac depth

mysql_query('UPDATE kategorie SET ip="'.$newparrent['ip'].'.'.$cat['id'].'", depth=' . $set_depth . ', parentID="'.$newparent['id'].'" WHERE id="'.$cat['id'].'"');
mysql_query('UPDATE kategorie SET ip=REPLACE(ip, "' . $cat['ip'] . '.", "' . $newparrent['ip'].'.'.$cat['id'] . '."), depth=' . $set_depth . ' WHERE ip LIKE("' .  $cat['ip'] . '.%")');

Niezbędne jest podmienienie wszystkim elementom danej gałęzi pola ip, depth (jego wyliczenie może wygląda skomplikowanie – więc trzeba pomyśleć, bądź przyjąć moje rozwiązanie za pewnik ), a także parentID jedynie dla kategorii-matki danej gałęzi.

Przy przenoszeniu kategorii powinniśmy specjalnie objąć warunek, w którym przenosimy kategorię do kategorii głównej (parentID to 0, a ip rozpoczynać się winno bez kropki, depth obliczamy poprzez $set_depth= 'depth-' . $cat['depth'];). Poprzez uproszczenie nie zawarłem tego przypadku w kodzie.

Liczba podkategorii

Tu filozofii wielkiej nie ma:

$cat=array('id'=>1, 'name'=>'Unix', 'ip'=>'1', 'parentID'=>0, 'depth'=>1);
$q=mysql_query('SELECT COUNT(*) FROM kategorie WHERE ip LIKE("' .  $cat['ip'] . '.%")');
$r=mysql_fetch_row($q);
echo 'Ilość: '.$r[0];

Usuwanie kategorii:

mysql_query('DELETE FROM kategorie WHERE ip REGEXP "^'.$cat['ip'].'(\.(.+))?$"');

Proste wyrażenie regularne i jednym zapytaniem usuwamy wszystko

Podsumowanie

Jak widzimy wykorzystanie drzewek IP zmusza troszeczkę do wykorzystania szarych komórek, lecz znacznie optymalizuje działania na kategoriach. W przypadku standardowej implementacji – a więc samego pola parentID, aby wyświetlić drzewo musimy wykonać albo wiele zapytań, albo dużo iterować w php, wyświetlenie liczby podkategorii to zabójstwo dla bazy danych, podobnie jak usunięcie kategorii wraz z jej podkategoriami.

Żeby to w jeszcze prostszy sposób użytkować niedługo zamieszczę na blogu własną bibliotekę do obsługi drzewa, oczywiście Open Source

Podobne wpisy

• Import bazy danych z pliku kopii zapasowej w PHP
• MySQL : Indeksy i klucze obce
• Sun zakupiony przez Oracle – co dalej z MySQL?
• Synchronizacja plików PHP w Eclipse część 2 – SVN w Subclipse
• Dostęp do tablic poprzez magiczną metodę __get() w PHP5