Z notatnika webmasterki

08 Lis, 2009

Struktura drzewiasta w bazie danych Odc. 3 Nested set – odczytywanie struktury drzewa

Zamieszczony przez: Joanna w: PHP|SQL

Skoro już wyjaśniłam na czym polega konstrukcja drzewa typu nested set, pora pokazać w jaki sposób, za pomocą niezbyt skomplikowanych zapytań, można wyciągnąć różne informacje. Na początek zajmiemy się zapytaniami, które pozwolą nam wczytać strukturę drzewa.

Wczytanie drzewa

Żeby wczytać całe drzewo nie trzeba wielkiej filozofii, wystarczy wykonać jedno zapytanie. To zagadnienie jest jednak trywialne bez względu na to w jaki sposób zaimplementujemy nasze drzewo w bazie danych.

SELECT title,lft FROM tree ORDER BY lft

Klauzula ‚ORDER BY lft’ w powyższym zapytaniu zapewnia wczytanie w odpowiedniej kolejności elementów podrzędnych względem nadrzędnych oraz elementów podrzędnych względem siebie. jak widać na poniższym rysunku, elementy ‚Word’, ‚Excel’ i ‚PowerPoint’ następują po nadrzędnym ‚Office’ i w dodatku w odpowiedniej kolejności.

wynik zapytania Do pełni szczęścia brakuje jedynie wcięć lub innych ‚znaczków’ pokazujących strukturę drzewa. Tomasz ‚Zyx’ Jędrzejewski w swoim blogu pokazuje dość pokrętny, ale być może atrakcyjny dla niektórych sposób prezentacji tak wczytanego drzewa. Nie szczególnie mi się on podoba, ale dla porządku przytaczam, bo może on kogoś zainteresuje. Osobiście jednak wolę nieco inne metody. W końcu metodą Nested set zainteresowałam się dlatego że chciałam ograniczyć późniejszą obróbkę danych w skrypcie.

Poziom zagłębienia

Żeby odtworzyć strukturę drzewa, jak już napisałam przydałyby się jakieś wcięcia, albo inne znaki pokazujące poziom zagłębienia. Tylko skąd wziąć informację o tym poziomie? Na początek, żeby łatwiej było zrozumieć przypomnę rysunek z poprzedniego artykułu, uzupełniony o informację na temat poziomów zagłębienia.
Nested set

Spojrzenie na to samo drzewo, ale z trochę innej, bardziej płaskiej perspektywy pozwoli zrozumieć, że informację o poziomie zagłębienia dowolnego elementu można bardzo łatwo uzyskać odpowiednim zapytaniem.
Nested set

Popatrzmy na element ‚Word’. Rzut oka na strukturę drzewa wystarczy, żeby stwierdzić, że jest on na trzecim poziomie zagłębienia (przyjmując, że ‚root’ jest na poziomie zero). Teraz popatrzmy na rysunek pokazujący drzewo spłaszczone drzewo. Jak widać ramka, w której jest element ‚Word’ jest otoczona ramkami trzech elementów nadrzędnych. Wszystkie te ramki mają pewną wspólną własność. Ich parametr ‚lft’ jest mniejszy a parametr ‚rgt’ jest większy niż w przypadku elementu ‚Word’. Jeśli znamy wartości ‚lft’ i ‚rgt’ interesującego nas elementu, bez trudu odczytamy jego poziom zagłębienia za pomocą zapytania:

SELECT count(id) AS depth FROM tree WHERE lft < 4 AND rgt > 5

Powyższy warunek można zapisać inaczej. Z pozoru może wyglądać bezsensownie, ale przyda się w zrozumieniu późniejszych zapytań.

SELECT count(id)-1 AS depth FROM tree WHERE 4 BETWEEN lft AND rgt

Ten zapis oznacza dokładnie tyle, że zliczamy te elementy, dla których wartość parametru ‚lft’ jest mniejsza lub równa a ‚rgt’ większa lub równa od wartości parametru ‚lft’ elementu ‚Word’. Musimy odjąć jeden, gdyż klauzula BETWEEN to nierówność nieostra, więc policzy nam również element dla którego lft = 4, a umówiliśmy się, że poziom zagłębienia będziemy numerować od zera.

No tak, ale wygląda na to, że wpierw powinniśmy wykonać zapytanie, które zwróci nam wartość ‚lft’ i ‚rgt’ wskazanego elementu i tak dla każdego elementu osobno. Trochę bez sensu, bo miało być łatwiej, mniej zapytań, mniej obliczeń, a wychodzi na to, że jest odwrotnie.

Metoda przez złączenie

Na szczęście nie trzeba wykonywać aż tak skomplikowanych zabiegów. Wystarczy jedno zapytanie, które da nam to czego potrzebujemy:

SELECT child.title, count(parent.id)-1 AS depth
FROM tree AS child,
tree AS parent
WHERE child.lft BETWEEN parent.lft AND parent.rgt
GROUP BY child.id
ORDER BY child.lft

poziom zagłębienia Dwa słowa w celu wyjaśnienia, jak właściwie działa to zapytanie. Najpierw robimy złączenie tabeli z samą sobą nadając dwóm jej instancjom aliasy ‚parent’ i ‚child’. Jest to złączenie każdy z każdym, co stanowi pewien problem, ale o tym później. Po wykonaniu złączenia wybieramy z niego rekordy dla których zachodzi warunek określony wcześniej. Jest on nieco nieco inaczej zapisany, ale w gruncie rzeczy ma to samo znaczenie. Po odrzuceniu rekordów, które nie spełniają warunku, pozostałe grupujemy względem ‚child.id’. Wszystko po to, żeby można je było policzyć za pomocą funkcji ‚count’, od wartości zwróconej przez tę funkcję należy odjąć jeden, bo umówiliśmy się, że poziomy liczymy od zera. Jeśli ktoś nie czuje tego i nie rozumie do końca co tu zaszło to proponuję wykonać serię zapytań, która pokaże krok po kroku jak to wygląda

SELECT child.title AS child, parent.title AS parent, 
child.lft AS childL, parent.lft,parent.rgt
FROM tree AS child,
tree AS parent
ORDER BY child.lft

SELECT child.title AS child, parent.title AS parent, 
child.lft AS childL, parent.lft,parent.rgt
FROM tree AS child,
tree AS parent
WHERE child.lft BETWEEN parent.lft AND parent.rgt
ORDER BY child.lft

Spróbujmy więc teraz wykorzystać fakt, że potrafimy wyciągnąć z bazy informację o poziomie zagłębienia dowolnego elementu i odtwórzmy wreszcie naszą strukturę drzewa. Oto niezbędne zapytanie:

SELECT 
concat( repeat('-', COUNT(parent.id) - 1),child.title) 
AS title,
child.id
FROM tree AS child,
tree AS parent
WHERE child.lft BETWEEN parent.lft AND parent.rgt
GROUP BY child.id
ORDER BY child.lft

drzewo No i otrzymaliśmy to o co nam chodziło. Jednym zgrabnym zapytaniem, bez żadnych dodatkowych machinacji wykonywanych w skrypcie, choć czasem lepiej mieć wartość poziomu zagłębienia podaną tak jak to było w poprzednim zapytaniu.

Jak już wspomniałam w omawianym powyżej zapytaniu występuje złączenie typu każdy z każdym. Operacja na takich złączeniach jest dość obciążająca dla bazy, bo takie złączenie ma bardzo dużo rekordów (jest to liczba rekordów tabeli podniesiona do kwadratu), z których dopiero później eliminowane są te niespełniające warunku. Jeśli więc drzewo będzie bardzo rozbudowane lepiej spróbować innych metod.

Metoda z podzapytaniem

Jeśli więc drzewo ma być bardzo rozbudowane a tego typu zapytania mają być często wykonywane, to może warto spróbować innej metody. Zamiast złączenia można wykorzystać podzapytanie:

SELECT title, 
 (SELECT count(parent.id)-1 
  FROM tree AS parent
  WHERE node.lft BETWEEN parent.lft AND parent.rgt)
 AS depth
FROM tree AS node
ORDER BY node.lft

Nie trzeba tu chyba za dużo tłumaczyć. Podzapytanie w klauzuli SELECT jest dokładnie takie jak omawiane na samym początku tego artykułu. Jeśli chcemy mieć ładne wcięcia, lub myślniki obrazujące strukturę drzewa to trzeba podzapytanie wykorzystać trochę inaczej (wygląda dość paskudnie, więc wiersze zawierające podzapytanie podświetliłam):

SELECT 
concat( repeat('-', 
    (SELECT count(parent.id)-1
     FROM tree AS parent
     WHERE node.lft BETWEEN parent.lft AND parent.rgt)
),node.title) AS title,
node.id
FROM tree AS node
ORDER BY node.lft

Już przy tabeli zawierającej 10 rekordów widać różnicę na korzyść metody z podzapytaniem. Można więc zaryzykować stwierdzenie, że jest ona wprawdzie mniej elegancka, ale jednak szybsza. Przy dużych tabelach warto ją rozważyć.

Metoda z dodatkowym polem

Jest jeszcze jedna metoda. Moim zdaniem najmniej elegancka. Na pozór wydaje się ułatwiać pracę, ale w późniejszych artykułach pokażę, że może ją skutecznie utrudnić i skomplikować wszelkie działania. Kiedy patrzy się na powyższe zapytania rodzi się pokusa dodania do tabeli dodatkowego pola ‚depth’ i przechowywania tam odpowiedniej wartości. Na pozór nie ma problemu. Dodając element wystarczy jednorazowo policzyć jego poziom zagłębienia prostym zapytaniem pokazanym na początku i po sprawie. Pokażę jednak w przyszłości, że problemy są, a właściwie mogą być i to spore. Zainteresowanych zapraszam wkrótce, do lektury kolejnych artykułów z tej serii.

2 komentarze na "Struktura drzewiasta w bazie danych Odc. 3 Nested set – odczytywanie struktury drzewa"

1 | jachu

24. maja 2010 o 10:23 am

Avatar

Wszystkie ładnie opisane, dzięki ;)

2 | Belial

1. stycznia 2012 o 5:58 pm

Avatar

Witam,

Gratuluję świetnego artykułu – mam tylko jedno pytanie: w jaki sposób mogę wyświetlić rekordy znajdujące się na tym samym poziomie? Czyli opierając się na Pani przykładzie, chciałbym aby zostały wyświetlone tylko rekordy na poziomie 1, tj. Windows, Linux, MacOS albo tylko te z poziomu 2, ale z informacją do jakiego rodzica należ poszczególne rekordy (próbuję jakoś sensownie wykorzystać wiedzę przekazaną przez Panią do implementacji takiego drzewa w PHP, ale póki co zatrzymałem się właśnie na takim problemie…).

Z góry dziękuję i pozdrawiam!

Formularz komentarza

Listopad 2017
P W Ś C P S N
« Lip    
 12345
6789101112
13141516171819
20212223242526
27282930  

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 25 pozostałych subskrybentów

Tematy