Jest to metoda żywcem ściagnięta z rozwiązania gościa, który nazywa się Joe Celko. Opisał on w swojej książce SQL - zaawansowane programowanie rozwiązanie, któe jakże bardzo mi się nie podoba, ale dla zasady je wymienię.
Wygląda to tak, że w tabeli tree zamiast pola tree_id pojawiają się left_mark i right_mark. Wartości tych pól są wyliczne w sposób następujący:
(1,22) Kategoria główna
(2,3) Kategoria główna/Kat 3
(4,15) Kategoria główna/Kat 2
(5,6) Kategoria główna/Kat 2.3
(7,8) Kategoria główna/Kat 2.2
(9,14) Kategoria główna/Kat 2.1
(10,11) Kategoria główna/Kat 2.1.2
(12,13) Kategoria główna/Kat 2.1.1
(16,21) Kategoria główna/Kat 1
(17,18) Kategoria główna/Kat 1.2
(19,20) Kategoria główna/Kat 1.1
Jak te
wartości wyliczyłem? Na początku dodam, że moje drzewo jest narysowane
w taki sposób, który nie jest może najlepszy dla tej metody. Ale w celu
uproszczenia przykłady postanowiłem zacząć od tyłu albo od lewej strony.
Na początku ustalmy sobie licznik którego wartoś początkowa będzie równa 1.
Dla kategorii głównej w left_mark wstawiamy wartość tego licznika zwiększając go o jeden (counter++).
Następnie idąc wokół drzewa (mając je po lewej swojej stronie)
napotykamy element Kat 3 któremu również wstawiamy laft_mark równy counter++ czyli 2. Skoro po Kat 3 nie dziedziczy, żaden element to ustawiamy mu rónież right_mark równą counter++ (3). Idziemy dalej i napotykamy Kat 2 ustawiając jej kolejną wartość licznika w polu left_mark=4. Widząc że ta ma dzieci, przechodzimy do nich i kolejno ustawiamy w Kat 2.3 left_mark=counter++ (5) i skoro ta nie ma już elementów dziedzicznych to ustawiamy jej również right_mark=counter++ (6). Idąc tak dalej po drzewie wracamy do kategorii głównej i ustawiamy jej wartość right_mark=22.
Jak widzimy algorytm numerowania poszczególnych elementów jest dosyć skomplikowany w implementacji. Wstawienie kolejnego elementu do struktury wymaga przeliczenie wszyskich wartości right_mark i left mark alementów występujących po prawej lub po lewej stronie naszego nowego elementu.
Pzykładowo gdybyśmy chcieli dodać nową kategorię np.: Kat 2.4 to musimy wykonać następująca procedurę. Zanim to zrobimy, zauważmy że chcemy wstawić nasz nowy element obok Kat 2.3 (left_mark=5, right_mark=6).
INSERT INTO tree (left_mark, right_mark, nazwa) VALUES (5,6,'Kat 2.4');
Przy kilku rekordach tabeli różnicy w działaniu nie zauważymy, ale w przypadku gdy będziemy mieli do czynienia ze zbiorem danych co najmniej 10tyś rekordów każde takie UPDATE może okazać się dość kosztowne. To co jest dobre w tej metodzie to to, że możemy bardzo łatwo wyszukiwać elementy powiązane z tego typu strukturą. Kwestia poziomu zagnieżdżenia - oczywiście podobnie jak w metodzie I nie ma tutaj ograniczenia. Jednak sama implementacja procedur do obsługi takiej struktury danych nie jest banalna :-(. Kolejny problem jaki możemy napotkać podczas implementacji to odszukanie elementów umieszczonych poziom niżej, albo poziom wyżej.
Rozwiązaniem pomocnym dla tego typu struktury będzie dodanie pola tree_id, w któym będziemy przechowywać id rodzica. W takim przypdaku mamy sytuację w któej bez problemu możemy wyszukiwać w poszczególnych dowolnie zagnieżdżonych kategoriach i odwoływać się do umieszczonych bezpośrednio rodziców i dzieci. Pozostaje jednak nadal nierozwiązany problem budowania ścieżki dla poszczególnych elementów. Jednym słowem mówiąc tworzymy metodę III na bazie metody I i II.