Obsługa drzew w SQL - część 1
Komentarze (3) Praktycznie w każdym projekcie informatycznym (a w e-commerce w szczególności) pojawiają sie jakieś struktury drzewiaste. Ich zapisywanie do bazy danych stanowi problem, ponieważ tabele baz danych są przystosowane do zapisu ‘liniowego’ a nie drzewiastego.
Załóżmy, że mam taką strukturę drzewa (cyferki oznaczają identyfikatory węzłów):
Najczęściej używaną strukturą jest wstawianie do rekordu potomnego klucza obcego wskazującego na rekord-rodzic bieżącego rekordu. Tabela tree będzie zawierała następujące dane:
id parent_id data 1 NULL … 2 1 … 3 1 … 4 2 … 5 4 … 6 4 … 7 2 … itd
Sens tych wartości jest oczywisty: każdy rekord zawiera referencję na rekord ‘nadrzędny’ (rodzica). Rekord od id = 1 nie ma rodzica - w związku z tym parent_id = NULL.
Co daje taki model? Na pewno bardzo proste wstawianie nowych rekordów. Równie proste jest przesuwanie - jednym zapytaniem można przesunąć całą gałąź do innego węzła. Z usuwaniem sprawa nie jest już taka prosta, ale można skorzystać z kaskady (ON DELETE CASCADE), która bardzo ładnie usunie całą gałąź poniżej usuwanego elementu.
Problem w tym, że wstawianie, usuwanie i przesuwanie to nie są operacje najczęściej wykonywane na drzewie. Typowe operacje to: “pobierz wszystkie węzły potomne oddalone o mniej niż 2 od wskazanego węzła“, albo “pobierz wszystkie węzły macierzyste wskazanego węzła“. W praktycznych zastosowaniach pierwsza operacja odpowiada np. budowaniu nawigacji na podstawie drzewa kategorii, druga zaś - tworzenia ścieżki dostępu (tzw. breadcrumbs) od bieżącej kategorii do strony głównej serwisu.
SQL nie zawiera wydajnych narzędzi czytania drzew zdefiniowanych tak, jak w powyższym przykładzie. W efekcie każda próba odczytania dowolnego fragmentu drzewa wymaga wielokrotnych zapytań do bazy danych - po jednym dla każdego poziomu przy czytaniu “w górę”, i co najmniej po jednym na każdy poziom przy czytaniu w dół. Przy serwisach z bardziej złożonym układem kategorii narzut związany z budowaniem nawigacji może być bardzo znaczący. Oczywiście, można użyć jednej z wielu technik cachowania, ale cache tylko maskuje prawdziwy problem.
Na szczęscie jest metoda pozwalająca na odczytanie dowolnego fragmentu drzewa pojedynczym zapytaniem - kosztem bardziej złożonej procedury dodawania i modyfikacji drzewa. Ale o tym w następnym wpisie.