W przypadku najprostszej implementacji struktury drzewiastej w bazie, jaką opisałam w pierwszym artykule tej serii, przeniesienie całej gałęzi do nowej lokalizacji jest zagadnieniem trywialnym. Wystarczy zmienić wartość parametru ‘parentID’ odpowiedniego rekordu i już. Jeśli chodzi o drzewo typu nested set, nie jest to już takie proste. Przeniesienie gałęzi wymaga przeliczenia parametrów ‘lft’ i ‘rgt’ wielu rekordów. Przypomina to trochę znaną zabawę w przesuwane puzzle. Aby przesunąć grupę rekordów stanowiących gałąź do nowej lokalizacji, trzeba dla niej zrobić miejsce przesuwając inną grupę rekordów.
Nieco teorii
Na czym dokładnie ma polegać ta operacja, najłatwiej będzie zrozumieć analizując omawiane już wcześniej drzewo przedstawione za pomocą płaskiej perspektywy. Załóżmy więc, że chcemy przenieść gałąź opartą na elemencie ‘office’ (lft=3 rgt=10) tak, aby stała się elementem podrzędnym dla elementu ‘Linux’, tuż za elementem ‘Iceweasel’, tak jak to pokazano na rysunku poniżej.
Przesuwana gałąź składa się z czterech rekordów, wobec czego rezerwuje dla siebie osiem unikalnych wartości parametrów ‘lft’ i ‘rgt’. Aby ją przesunąć w wyznaczone miejsce należy między parametrami ‘rgt=16′ a ‘rgt=17′ zrobić odpowiednio dużo wolnego miejsca. W tym celu wszystkie parametry ‘lft’ i ‘rgt’ o wartościach od 11 do 16 należy zmniejszyć właśnie o wartość 8. W ten sposób powstanie luka w którą będzie można wstawić naszą gałąź.
Jak widać na powyższym rysunku wymagało to przeliczenia wartości sześciu parametrów ‘lft’ i ‘rgt’ i właśnie o tyle trzeba zwiększyć wartości parametrów ‘lft’ i ‘rgt’ dla wszystkich rekordów przesuwanej gałęzi, aby znalazła się ona w pożądanym miejscu.
Komplet niezbędnych zapytań
Operacja przesunięcia gałęzi wymaga jeszcze większej ilości zapytań niż dodanie rekordu, oznacza to, iż również tym razem należy wpierw zablokować tabelę wykonując zapytanie:
LOCK TABLES tree WRITE
W następnej kolejności należy wykonać zapytanie które pomoże nam uzyskać lukę w odpowiednim miejscu i przesunie część rekordów, tak jak zostało to wcześniej opisane:
UPDATE tree SET `lft` = `lft` - 8 WHERE `lft` >= 11 AND `lft` <=16 UPDATE tree SET `rgt` = `rgt` - 8 WHERE `rgt` >= 11 AND `rgt` <=16
Po przesunięciu części rekordów i zwolnieniu miejsca na przenoszoną gałąź należy wykonać zapytania, które przeliczą parametry ‘lft’ i ‘rgt’ wszystkich elementów gałęzi.
UPDATE main_tree SET `lft` = `lft` + 6 WHERE `id` IN(5,8,9,10) UPDATE main_tree SET `rgt` = `rgt` + 6 WHERE `id` IN(5,8,9,10)
Dociekliwy czytelnik zauważy zapewne, że tym razem warunek, na podstawie którego wybierane są modyfikowane rekordy, nie dotyczy wartości parametrów ‘lft’ i ‘rgt’. Zapobiega to ponownemu, a więc błędnemu przetworzeniu rekordów zmodyfikowanych w poprzednim kroku. Dlatego waśnie w tym kroku należy precyzyjnie wskazać identyfikatory rekordów należących do przesuwanej gałęzi.
W ostatnim kroku wystarczy już tylko odblokować tabelę:
UNLOCK TABLES
Praca domowa
W tym artykule pokazałam tylko ideę algorytmu pozwalającego przesuwać całe gałęzie w obrębie drzewa, oraz zapytania realizujące konkretny wariant tej operacji. Obsługę tego algorytmu od strony php, czyli rozstrzygnięcie jak uzyskać zestaw wartości parametrów ‘id’ wszystkich elementów drzewa, jak określić które rekordy trzeba przeliczyć aby zrobić miejsce dla przesuwanej gałęzi oraz obliczenie o jaką wartość należy zmienić wartości parametrów ‘lft’ i ‘rgt’ w poszczególnych krokach operacji, pozostawiam inwencji twórczej czytelnika, który będzie chciał z przedstawionego tu modelu skorzystać. To tak w ramach pracy domowej.
Podobne artykuły:
- Struktura drzewiasta w bazie danych Odc. 5 Nested set – dodawanie rekordu
- Struktura drzewiasta w bazie danych Odc. 4 Nested set – odczytywanie gałęzi
- Struktura drzewiasta w bazie danych Odc. 3 Nested set – odczytywanie struktury drzewa
- Struktura drzewiasta w bazie danych Odc. 2 Konstrukcja drzewa typu nested set
- Struktura drzewiasta w bazie danych Odc. 1
21 maj 2010 o 21:21
Muszę przyznać, że zrobiłaś kawał dobrej roboty. Śledziłem Twoje wpisy w tej kategorii od początku. Szczerze wątpiłem, że dasz radę pociągnąć taki rozbudowany temat, tak dokładnie go opisać, przedstawić na przykładach.
Gratuluję samozaparcia.
Pozdrawiam
21 maj 2010 o 21:58
Dziękuję za miłe słowa. Temat rozmontowywałam, bo było mi to potrzebne w pracy, a poza tym jest to dość ciekawe zagadnienie. Uznałam, że szkoda by było, nie podzielić się wiedzą.
Można było mieć wątpliwości czy doprowadze temat do konca, bo miałam spora przerwę (macierzyńską). No ale jak widac wracam do pracy.
W sumie to pozostał jeszcze jeden tamat, kasowanie, ale jak ktoś się upora z przesuwaniem gałęzi, to kasowanie będzie dla niego drobnostką.
Oczywiście zagadnienie nie jest wyczerpane. Szczególnie, że nie pokazałam rozwiązań na poziomie PHP. Zrobiłam to celowo, żeby nie zaciemniać i nie komplikować. Jednak, kto wie. Może się kiedyś o to pokuszę.
21 maj 2010 o 21:58
Dziekuję Joanno za 6 odcinkowa lekcję.
Od poł roku przymierzałem się do muśnięcia tego tematu, a Ty podałas go mi na przysłowiowym talerzu.
Krótko , zwięźle i na temat.
Pozdrawiam
Kondor
31 maj 2010 o 11:53
Jaką metodę drzewa polecasz do komentarzy? Coś na zasadzie zagnieżdżonych komentarzy jak w WP?
31 maj 2010 o 12:06
Ponieważ najprawdopodobniej nie będziesz edytował tego drzewa i zmieniał jego struktury a jedynie komentarze będą dodawane i usuwane to tym bardziej skłaniałabym się do metody nested set, ale ja jestem ta metodą zafascynowana
więc mogę być nieobiektywna.
31 maj 2010 o 21:40
Niestety czasem zajdzie potrzeba edycji/usunięcia komentarzy, lecz będzie to raczej rzadkie zjawisko:)
21 gru 2010 o 13:24
Joanno, wielkie ukłony w Twoją stronę za ‘wytłumaczenie’ tego dość trudnego dla początkujących tematu… Kwestie struktury nested set raczej opanowałem, ale nie mogę wpaść na pomysł jak wygenerować sobie ładną zagnieżdżoną nieuporządkowaną listę …
21 gru 2010 o 21:51
Nie bardzo rozumiem, co masz na myśli pisząc o zagnieżdżonej nieuporządkowanej liście? Jeśli chodzi Ci o to, że gałęzie nie muszą mieć ustalonej kolejności, to chyba zostaje Ci dołożenie do każdego rekordu informacji o numerze id rodzica
21 wrz 2011 o 9:10
Polecam wszystkim ksiażkę SQL Receptury (zapytania hierarchiczne)
oraz 100 sposobów na SQL
W obu książkach przedstawiono struktury drzewiaste, niestety nie ma nic o nested set.
28 wrz 2011 o 13:40
Przez wszystkie etapy implementacji przeszedłem gładko, ten zostawiając sobie na koniec. Trochę mi się nie podoba, że wszędzie wystarczyło operować jedynie na parametrach „lft” i „rgt” a tutaj trzeba dodatkowo podać „id” usuwanych rekordów.
Chyba przerobię sobie to w ten sposób, że tymczasowo pomnożę przenoszoną gałąź przez -1. Wtedy w bazie kolumna nie będzie mogła być oznaczona jako „UNSIGNED” ale to bardzo mało istotna wada bo już chyba ustaliliśmy, że nested set ma sens tylko przy stosunkowo małej liczbie rekordów.
28 wrz 2011 o 23:56
No niestety. Takie życie. Mozna jeszcze wysyłać rekordy w kosmos w sensie nadawać im lft i rgt spoza bieżącego zakresu, a potem je wstawiać na miejsce. To tez pozwoli uniknąć nadpisania wartości lft i rgt podczas przenoszenia gałęzi.