Obsługa drzew w SQL - część 2 - Model ścieżki zmaterializowanej
Komentarze (0) W poprzednim wpisie pokazałem typowe podejście do zagadnienia drzew w SQL (notabene: nazywa się on modelem sąsiedztwa), omówiłem też jego podstawowe wady (i zalety) i obiecałem opisać inne podejście - pozbawione wad modelu sąsiedztwa.
Jeśli przyjrzysz się przykładowemu drzewu, który chcemy zapisać w bazie danych, można zauważyć, że położenie w drzewie można także opisać jako listę wszystkich węzłów nadrzęnych danego węzła. Taka lista nosi nazwę “ścieżki”, i zapisuje się ją licząc od najstarszego rodzica aż po bieżący węzeł. Przykładowo, ścieżka dla węzła “4″ ma postać: “1,2,4″, a dla węzła “11″ - “1,3,10,11″. Dodatkowo, przyda się kolumna informująca, na jakim poziomie znajduje się dany węzeł względem początku drzewa (teoretycznie można tą informację wyciągnąć z długości ścieżki - ale takie zadanie jest, niestety, nierelacyjne, a co za tym idzie - bardzo obciążające dla bazy)
W bazie danych może to wyglądać tak:
table tree_mpath: id mpath level data 1 1 0 ... 2 1,2 1 ... 3 1,3 1 ... 4 1,2,4 2 ... 5 1,2,4,5 3 ... 6 1,2,4,6 3 ... 7 1,2,7 2 ... itd.
Co daje taki zapis? Przede wszystkim, pozwala z łatwością, pojedynczym zapytaniem, pobieramy fragmenty drzewa:
-
SELECT id, mpath, level, DATA FROM tree_mpath
-
WHERE FIND_IN_SET(id, (SELECT mpath FROM tree_mpath WHERE id = 4))
-
ORDER BY level;
zwróci:
id mpath level data 1 1 0 ... 2 1,2 1 ... 4 1,2,4 2 ...
czyli wszystkie elementy nadrzędne węzła 4 (wraz z tym węzłem, co akurat łatwo wyfiltrować).
Do pobierania elementów podrzędnych węzła możemy użyć zapytania:
-
SELECT id, mpath, level, DATA FROM tree_mpath
-
WHERE mpath LIKE (SELECT CONCAT(mpath, '%') FROM tree_mpath WHERE id = 4)
-
ORDER BY level
które w wyniku da nam:
id mpath level data 4 1,2,4 2 ... 5 1,2,4,5 3 ... 6 1,2,4,6 3 ...
Pobieranie fragmentu drzewa też nie jest trudne: powiedzmy, że chcemy pobrać tylko bezpośrednich potomków węzła o id = 2:
-
SELECT id, mpath, level, DATA FROM tree_mpath
-
WHERE mpath LIKE (SELECT CONCAT(mpath, '%') FROM tree_mpath WHERE id = 2)
-
AND level = (SELECT level+1 FROM tree_mpath WHERE id = 2)
i w efekcie dostaniemy:
id mpath level data 4 1,2,4 2 ... 7 1,2,7 2 ...
Jak widać - zalety tego modelu są znaczne. Praktycznie dowolny fragment drzewa można czytać pojedynczym zapytaniem, zarówno “w górę” jak i “w dół” od wskazanego węzła. Oczywiście, dla sprawnego działania na taką tabelę należy nałożyć odpowiednie indeksy: na pole id (to chyba oczywiste), mpath oraz level.
Jakie są wady tego modelu?
1. Wysoki koszt aktualizacji. O ile dodanie nowego rekordu jest całkiem znośne, usunięcie również jest całkiem szybkie (choć wymaga dość złożonych warunków, podobnych do tych używanych w zapytaniach SELECT), to przesuwanie węzła w inne miejsce w drzewie jest drogą przez mękę: nie dość, że trzeba zaktualizować przesuwany rekord, to należy też zmodyfikować wszystkie jego węzły potomne. Biorąc pod uwagę, że aktualizacji podlegają indeksy, narzut czasowy jest poważny.
2. Spójność danych. Konstrukcja tabeli nie pozwala na używanie kaskad przy usuwaniu rekordu. W efekcie błąd może doprowadzić do powstania węzłów-zombie, nie powiązanych z pozostałą strukturą drzewa.
3. Ograniczenia wielkości. Jeśli pole mpath będzie polem typu VARCHAR, trzeba pamiętać, że maksymalna długość tego pola to 255 bajtów. Jeżeli identyfikatory kategorii będą 3-znakowe (100-999), to każdy poziom zagłębienia będzie zabierał 4 bajty (identyfikator + przecinek), co daje maksymalny poziom zagłębienia ok. 60. Przy identyfikatorach 4 znakowych (1000-9999), maksymalny poziom zagłębienia to ok. 50. Przy dłuższych identyfikatorach (np. 36-bajtowy uu_id z MS SQL Server) maksymalna wielkość drzewa drastycznie spada (6 poziomów dla uu_id).
Zmiana typu mpath na TEXT rozwiązuje ten problem, ale może się pojawić problem z indeksowaniem takiego pola - np. MySQL nie pozwala na zakładanie indeksów na pole TEXT w InnoDB.
4. Normalizacja. Konstrukcja pola mpath łamie postać normalną tabeli. Zawartość pola level jest wprost powiązany z zawartością pola mpath (level ma wartość “długość ścieżki - 1″), i teoretycznie mógłaby zostać pominięta.
Istnieje rozwiązanie problemów 2-4 - nazywa się znormalizowanym modelem ścieżki zmaterializowanej. Ale o tym innym razem…
