Z notatnika webmasterki

17 Maj, 2010

Struktura drzewiasta w bazie danych Odc. 5 Nested set – dodawanie rekordu

Zamieszczony przez: Joanna w: SQL

Skoro pokazałam już jak wygląda struktura drzewa nested set oraz jak wczytać całe drzewo a także jak pobrać wybraną gałąź, pora zająć się dodawaniem rekordów do omawianej struktury.

W przypadku najprostszej implementacji struktury drzewiastej w bazie, jaką opisałam w pierwszym artykule tej serii, dodanie kolejnego rekordu jest proste i wymaga wykonania jednego zapytania. Wystarczy tylko aby w rekordzie była odpowiednia informacja i numerze ID rodzica by rekord znalazł się w odpowiednim miejscu struktury drzewa. Struktura typu nested set wymaga przeprowadzenia większej ilości operacji. Ponieważ jednak struktury drzewiaste częściej się wczytuje niż modyfikuje warto ponieść ten koszt, pamiętając, że ten sposób implementacji ułatwia późniejsze odczytywanie drzewa.

Trochę teorii

Przyjrzyjmy się drzewu omawianemu w poprzednich artykułach. Załóżmy, że chcemy do struktury dodać rekord ‚Windows Media Player’ tak, żeby w strukturze znalazł się między rekordem ‚Office’ a rekordem ‚InternetExplorer’, jak to pokazano na poniższej ilustracji:

Widać, że aby to osiągnąć nasz nowy element musi mieć parametry ‚lft’ i ‚rgt’ o wartościach odpowiednio 11 i 12, a wartości wszystkich parametrów ‚lft’ i ‚rgt’ znajdujących się na prawo od tego miejsca, powinny zostać przeliczone, to znaczy podwyższone o dwa. Oznacza to, że należy wykonać aż trzy zapytanie. Dwa z nich spowodują podwyższenie parametrów ‚lft’ i ‚rgt’, co spowoduje pojawienie się wolnego miejsca, w które za pomocą trzeciego zapytania będzie można wstawić nowy rekord.

Niezbędne zapytania

Ponieważ operacja wstawiania rekordu przebiega wieloetapowo, warto zadbać o to, by inny użytkownik serwisu nie wprowadził zamieszania próbując w tym samym czasie wstawić do drzewa swój rekord. W tym celu należy najpierw zablokować tablicę wykonując zapytanie:

LOCK TABLES tree WRITE

W następnej kolejności trzeba wykonać dwa zapytania w celu przeliczenia wartości parametrów ‚lft’ i ‚rgt’ w odpowiednich rekordach.

UPDATE `tree` SET `lft` = `lft` + 2 WHERE `lft` >= 11
UPDATE `tree` SET `rgt` = `rgt` + 2 WHERE `rgt` >= 12

I w reszcie można wstawić nowy rekord:

INSERT INTO `tree` (`title`,`lft`,`rgt`) 
VALUES ('Windows Media Player',11,12)

Na koniec wystarczy odblokować tabele:

UNLOCK TABLES

I oto wynik:

8 komentarzy na "Struktura drzewiasta w bazie danych Odc. 5 Nested set – dodawanie rekordu"

1 | Mad Max

24. czerwca 2010 o 11:13 am

Avatar

Do UPDATE `tree` SET `rgt` = `rgt` + 2 WHERE `rgt` >= 12 należy dodać jeszcze jeden warunek, np. WHERE id = 0 (id roota)
W przeciwnym wypadku jeśli w drzewie mamy jedynie roota lub chcemy dodać element na samym końcu drzewa i wykonamy zapytanie jak w przykładzie powyżej, to kolumna rgt nie zostanie zaktualizowana.

2 | Mad Max

24. czerwca 2010 o 11:20 am

Avatar

EDIT:
Zapytanie do powyższego przykładu powinno wyglądać mniej więcej tak:
UPDATE `tree` SET `rgt` = `rgt` + 2 WHERE `rgt` >= 12 OR id = 1

3 | Joanna

29. czerwca 2010 o 11:12 pm

Avatar

Jesteś w błędzie. Elementów nie dodajemy na końcu drzewa, tylko zawsze wewnątrz jakiegoś istniejącego już elementu drzewa.

Jeśli jest tylko root to lft=1 rgt=2 a zapytanie będzie wyglądać następująco:
UPDATE `tree` SET `rgt` = `rgt` + 2 WHERE `rgt` >= 2

Żaden dodatkowy warunek nie jest potrzebny. Przemyśl to jeszcze raz. To nie jest trudne, tylko trzeba się przyzwyczaić :)

4 | Mad Max

30. czerwca 2010 o 12:46 pm

Avatar

Ja wiem, że tak można zrobić i się z tym zgadzam :).
Tylko teraz załóżmy taki przypadek.
ROOT ma wartość rgt = 20 (jak w przykładzie wyżej)
Czyli ostatnia gałąź wychodząca z roota (Mac OS) ma wartość rgt = 19
Tera chcemy aby z ROOTa wychodziła jeszcze jedna gałąź, czyli musimy dać jej lft > 19. Czyli dla nowej gałęzi wartość lft = 20, a dla rgt 21.

I spróbuj na swoim zapytaniu dodać taką gałąź. Nie da się.
Jeśli wiemy jakie wartości mają być w nowej gałęzi w polach lft i rgt, a zakładam, że wiemy, to przy zapytaniu:

UPDATE `tree` SET `rgt` = `rgt` + 2 WHERE `rgt` >= 21

pole rgt w ROOT nie zostanie zmienione.

5 | Joanna

30. czerwca 2010 o 11:23 pm

Avatar

Wychodzisz ze złego założenia. Skoro chcesz coś wstawić między 19 a 20 to (bez względu na to czy lft=19 a rgt=20 czy odwrotnie) zapytania musi być:
UPDATE `tree` SET `rgt` = `rgt` + 2 WHERE `rgt` >= 20
UPDATE `tree` SET `lft` = `lft` + 2 WHERE `lft` >= 20

I guzik Cię obchodzi, czy to root, czy inny element. Nie obchodzi Cie też w jakim stopniu już jest rozbudowane drzewo ani jaką ma konstrukcję. Naprawdę musisz jeszcze trochę przemyśleć ideę drzewa nested set :)

6 | Mad Max

30. czerwca 2010 o 11:45 pm

Avatar

Ok,
Może inaczej :) Masz rację. Można zapytanie napisać w taki sposób w jaki podałaś wyżej. Sposób jest poprawny. Jednak moja metoda też działa i też jest poprawna. Wiem bo sprawdzałem :) . Obie mają wady i zalety.
W mojej jest do sprawdzenia dodatkowy warunek w klauzuli WHERE co wpływa na wydajność zapytania (nieznacznie ale jednak).
Jednak ma jedną zasadniczą zaletę.

Wykonując takie zapytanie:
UPDATE `tree` SET `rgt` = `rgt` + 2 WHERE `rgt` >= 21 OR id = 1
Nie musimy znać wartości rgt. elementu nadrzędnego (w tym przypadku roota), bo nawet jeśli wartość elem. nadrzędnego jest większa od wartości rgt wstawianego elementu to elem. nadrzędny zostanie powiększony o 2 tak czy inaczej. Wystarczy, że znamy jego ID.

W twoim zapytaniu:
UPDATE `tree` SET `rgt` = `rgt` + 2 WHERE `rgt` >= 20 musimy wiedzieć jaka jest wartość rgt elem. nadrzędnego, którą to musimy pobrać innym zapytaniem, np. SELECT MAX(rgt) FROM `tree`

Celem moich komentarzy nie jest udowodnienie, że metoda przez ciebie zastosowana jest zła. Jest po prostu inna od mojej, którą w dodatku sprawdziłem i która działa. Wbrew pozorom rozumiem ideę Nested Trees bo ją stosuję w swoich aplikacjach. Po prostu przedstawiłem swój punkt widzenia :)
Pozdrawiam,

7 | Joanna

1. lipca 2010 o 12:20 am

Avatar

Ale my wcale nie musimy znać wartości rgt elementu nadrzędnego. Po stronie skryptu php jest sprawdzenie między jakimi wartościami rgt i lft chcemy wstawić rekord i więcej nic nas nie obchodzi. W związku z tym Twoja metoda nie ma zalet, bo polega na uwzględnianiu czegoś co nas nie obchodzi a w dodatku kosztem zupełnie zbędnego warunku. A że działa? No cóż. Zdarza się :)

Ty zdaje się wychodzisz z błędnego założenia. Po pierwsze wartość rgt elementu nadrzędnego nie może być mniejsza niż wartości rgt i lft elementu wstawianego, zawsze jest większa (oczywiście po przeliczeniu), więc Twoje dywagacje nie mają żadnego sensu.

Jeszcze raz powtarzam. Nie obchodzi nas wartość lft i rgl elementu nadrzędnego. Obchodzą nas jedynie te parametry między które chcemy się wepchnąć z nowym elementem. To mogą być lft i rgt elementów równorzędnych jak w przykładzie opisanym w tym artykule. I na tym polega uniwersalność tych zapytań.

Celem zaś moich komentarzy jest nakłonienie Cię do dokładniejszego przestudiowania zagadnienia, bo nie do końca rozumiesz ideę. Być może jest w trochę mojej winy. Może zbyt pochopnie założyłam, że wystarczy „rozpłaszczyć drzewo, żeby zrozumieć genialną prostotę tej konstrukcji.

8 | Joanna

1. lipca 2010 o 12:30 am

Avatar

Zagadnienie jest proste. Nowy element będzie miał lft i rgt określonej wartości. Wszystkie lft i rgt które są większe od wartości lft nowego elementu lub jej równe mają być podwyższone o 2 bez sprawdzania żadnych dodatkowych warunków. Koniec pieśni. Nie ma sensu komplikować sobie tak prostego zagadnienia :P

Formularz komentarza

Wrzesień 2017
P W Ś C P S N
« Lip    
 123
45678910
11121314151617
18192021222324
252627282930  

Archiwa

About

Moje notatki z pracy

Subskrypcja

Wprowadź swój adres email aby zaprenumerować ten blog i otrzymywać powiadomienia o nowych wpisach przez email.

Dołącz do 24 pozostałych subskrybentów

Tematy