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 [/code] 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. [code='sql'] UPDATE tree SET `lft` = `lft` + 6 WHERE `id` IN(5,8,9,10) UPDATE tree SET `rgt` = `rgt` + 6 WHERE `id` IN(5,8,9,10) [/code] 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ę: [code='sql'] UNLOCK TABLES [/code]
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.
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
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ę.
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
Jaką metodę drzewa polecasz do komentarzy? Coś na zasadzie zagnieżdżonych komentarzy jak w WP?
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.
Niestety czasem zajdzie potrzeba edycji/usunięcia komentarzy, lecz będzie to raczej rzadkie zjawisko:)
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ę …
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 :)
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.
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.
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.
hmmm … a czy ktoś to sprawdzał w praktyce ?
1) w przykładzie odc6 używasz dwóch różnych tabel tree i main_tree dlaczego ?
2) skopiowałem zapytanie (insert) z odc2 i dodałem dane do swojej bazy – wszystko ok.
3) podane w odc6 zapytania na przeniesienie gałęzi nie działają poprawnie: owszem przeniosło gałąź, ale jakoś inaczej, a mianowicie gałąź “Office” pojawiła się na “roocie” w dodatku “połknęła” gałąź “InternetExplorer”. W gałęzi “Linux” czyli tam gdzie powinna pojawić się cała gałąź “Office” pojawiło się jedynie “PowerPoint” i to na początku a nie na końcu gałęzi.
wszystko skopiowałem (ctr+C/ctr+V) więc błąd chyba jest po stronie zapytań.
Ad.1 bo się pomyliłam kopiując ze skryptu. Dziękuję za wskazanie błędu.
Ad.3 A czy jesteś pewien, że wszystko zrobiłeś jak należy i że u Ciebie elementy mają takie Id jak u mnie. Bo u mnie te zapytanie robią to co należy :)
na pewno “obsługa tego algorytmu od strony php” by się przydała :-) i pokazanie jakie kroki trzeba wykonać przy przenoszeniu węzłów
Ha ha ha… komuś się gotowce marzą :) To trochę nie w moim stylu.
Gratuluję dobrego artykułu. Przyznaję że dał mi trochę do myślenia.
Mam tymczasem drobną sugestię. Czy nie wygodniej zamiast dwóch zapytań:
UPDATE tree SET lft = lft – 8 WHERE lft >= 11 AND lft <= 16
UPDATE tree SET lft = lft + 6 WHERE id IN(5,8,9,10)
użyć jednego:
UPDATE tree SET lft = CASE
WHEN lft BETWEEN 11 AND 16 THEN lft-8
WHEN lft BETWEEN 3 AND 10 THEN lft+6
END
WHERE lft BETWEEN 3 AND 16
W ten sam sposób możnaby skrócić dwa zapytania dotyczące zmiany pola rgt.
Unikniemy wtedy wskazywania na pole id. Rozwiązałoby to problem, o którym raczył niegdyś tutaj wspomnieć Krzysiek.
Pozdrawiam serdecznie