Z notatnika webmasterki

23 Paź, 2009

Struktura drzewiasta w bazie danych Odc. 2 Konstrukcja drzewa typu nested set

Zamieszczony przez: Joanna w: SQL

Jak pisałam w poprzednim odcinku dotyczącym drzewek w bazie danych bardzo mi się spodobała idea drzewka typu Nested set, choć niektórzy namawiali mnie do zainteresowania się drzewami Depesza. Może kiedyś. Tymczasem porządkując swoją świeżo nabytą wiedzę i przemyślenia napiszę kilka słów o idei i typu Nested set.

Jak każde rozwiązanie to ma zarówno wady i zalety. Niewątpliwą zaletą jest to, że wszystkie niezbędne informacje mieszczą się w jednej tabeli. Drugą zaletą jest niezwykła łatwość z jaką można wyciągnąć strukturę dowolnie wybranej gałęzi nie martwiąc się o poziom zagłębienia, gdyż nie istnieje tu żaden limit. Przy czym danych wczytanych z bazy nie trzeba już w jakiś szczególny sposób obrabiać na poziomie php. Niewątpliwą wadą jest stopień skomplikowania zapytań, oraz to, że proste operacje jak dodawania, usuwanie i przesuwanie gałęzi wymagają wykonania większej ilości operacji na bazie danych niż w innych metodach.

Zanim się więc podejmie decyzję o zastosowaniu tej metody implementacji struktury drzewiastej trzeba się dobrze zastanowić, czy te wady są aż tak istotne. Jednym słowem trzeba się zastanowić jak będziemy używać tego drzewa. Jeśli przeważa odczytywanie drzewa lub poszczególnych gałęzi, to na pewno warto, bo można to zrobić jednym zapytaniem i minimalną ilością kodu php, a w dodatku można używać cache do przechowywania wyników zapytań co daje dodatkowe korzyści. Jeśli w grę wchodzi częste dodawanie, usuwanie i przesuwanie gałęzi to po pierwsze trzeba się będzie namęczyć przy konstrukcji zapytań, a po drugie będzie ich więcej. Jeśli więc połączenie z bazą danych nie jest szybkie i zapytania nie wykonują się błyskawicznie to może nie warto.

Ja postanowiłam zaimplementować u siebie ten model wprowadzając tylko niewielką modyfikację, z kilku powodów. Po pierwsze lubię się uczyć nowych rzeczy, więc traktuję to trochę jak rozrywkę intelektualną. Po drugie doszłam do wniosku, że u mnie drzewo będzie głównie odczytywana a rzadko modyfikowane, więc liczę na zysk w wydajności.

Pora więc przejść do przedstawienia idei modelu nested set. Posłużę się tym samym drzewem, które posłużyło jako przykład w poprzednim odcinku. Wyobraźmy sobie, że przemierzamy drzewo od lewej do prawej wzdłuż gałęzi tak jak to pokazuje poniższy rysunek. Mijając kolejne węzły numerujemy je kolejnymi liczbami całkowitymi póki nie przejdziemy całego drzewa, tak jak to zostało przedstawione na rysunku poniżej.
drzewo nested set

Tabela w bazie danych wygląda wtedy jak na rysunku poniżej i zawiera absolutnie wszystkie informacje niezbędne do obsługi tej struktury. Dla ułatwienia parametry ‚left’ i ‚right’ nazwałam odpowiednio ‚lft’ i ‚rgt’, żeby uniknąć konfliktu ze słowami kluczowymi LEFT i RGIHT zastrzeżonymi w SQL (jak wiadomo SQL nie rozróżnia wielkich i małych liter).
tabela drzewa nested set

CREATE TABLE IF NOT EXISTS `tree` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` varchar(100) NOT NULL,
  `lft` int(11) NOT NULL,
  `rgt` int(11) NOT NULL,
  PRIMARY KEY (`id`)
) ENGINE=MyISAM;
INSERT INTO `tree` 
(`id`, `title`, `lft`, `rgt`) 
VALUES
(1, 'root', 1, 20),
(2, 'Windows', 2, 13),
(3, 'Linux', 14, 17),
(4, 'MacOS', 18, 19),
(5, 'Office', 3, 10),
(6, 'InternetExplorer', 11, 12),
(7, 'Iceweasel', 15, 16),
(8, 'Word', 4, 5),
(9, 'Excel', 6, 7),
(10, 'PowerPoint', 8, 9);

Jeśli ktoś nie wierzy to wystarczy poczekać na następny odcinek. Pokażę jak można wykonać wszystkie niezbędne operacje na tak zaimplementowanym drzewie. Postaram się pokazać oryginalne metody jak również różne wygodne modyfikacje.

10 komentarzy na "Struktura drzewiasta w bazie danych Odc. 2 Konstrukcja drzewa typu nested set"

1 | Rasgan

23. października 2009 o 12:32 pm

Avatar

Z niecierpliwością czekam na dalsze artykuły związane z drzewkami. Sam nie mam czasu się tym zająć ani poczytać dogłebnie, więc twoje informacje są dla mnie przydatne. Tym bardziej że piszesz do rzeczy i na temat.

3 | Joanna

23. października 2009 o 8:40 pm

Avatar

Psujesz mi suspens :)

A tak na poważnie. Jeszcze lepszym jest ten link:
http://dev.mysql.com/tech-resources/articles/hierarchical-data.html

Wszystkie jednak mają poważną wadę. Nie są opatrzone moim komentarzem wynikającym z moich przemyśleń i doświadczeń :P

4 | Mitchell

4. listopada 2009 o 11:51 pm

Avatar

Osobiście uważam, że powyższe rozwiązanie to koszmar. No… Chyba, że operujemy na 5-10 elementowym drzewku, którego nie chcemy w zasadzie wcale modyfikować. Dużo sensowniejszym rozwiązaniem jest struktura typu:
ID, parentID, order, name

Dla powyższego przykładu:
1, 0, 10, root
2, 1, 10, Windows
3, 1, 20, Linux
4, 1, 30, MacOS
5, 2, 10, Office
6, 2, 20, InternetExplorer
7, 3, 10, Iceweasel
8, 5, 10, Word
9, 5, 20, Excel
10, 5, 30, PowerPoint

Zalety – w zasadzie wszystkie z Nested Set + prostota zapytań oraz obsługi. Wyświetlanie – prosta rekurencja… Dodając do bazy pole logiczne hasChildren można zmniejszyć ilość zapytań w rekurencji. Kolejność inkrementowana o 10 daje swobodną możliwość roszad w strukturze.

5 | Joanna

5. listopada 2009 o 10:02 am

Avatar

Każda metoda implementacji drzewa ma swoje wady i zalety. Będę o nich, a także o możliwych modyfikacjach tej metody, pisać w następnych artykułach.

A tak z ciekawości. Jaki algorytm zastosujesz chcąc wyciągnąć z bazy gałąź zaczynającą się od węzła ‚Windows’? Zaręczam Ci, że w zalecanej przez Ciebie metodzie to jest koszmar :)

6 | Er

13. listopada 2009 o 2:16 pm

Avatar

Coz Joanna, Mitchell ma poniekad racje z tym ze w jego przykladzie bedzie mozna zastosowac 2 rodzaje odczytu danych:
1. wczytanie wszystkich rekordow z drzewa i ‚zgrupowanie’ ich w tablicy, na koncu ‚wyluskanie’ interesujacej nas galezi np:

print_r($moje_drzewo[ 2 ]); // dla nazwy ‚windows’

2. druga metoda to rekurencja czyli odwolywanie sie do tej samej metody.

Oczywiscie, jak pierwsza moze byc szybsza niz druga (tylko 1 zapytanie do SQL) tak wiaze sie z wieksza ‚zabawa’ w pozniejzej obrobce danych.

Najlepszym rozwiazaniem przy zlozonych drzewach zawierajacych rekordy powyzej 10tys. jest wprowadzenie ‚hierarchi’ do przykladu Mitchell’a.

Hierarchia w prostych slowach to zapisanie ‚sciezki galezi’ przy kazdym rekordzie.

Zalety to super szybkie wyszukiwanie w porownaniu do innych metod, wady natomiast (nie ma rozy bez kolcow) jesli postanowimy przeniesc kategorie pod inna galaz to bedziemy musieli ‚odswierzyc’ ‚sciezke galzi’ w kazdym ‚dziecku’ nalezacym do tej kategorii oraz tabelach kozystajacych z naszej tabeli kategorii. Co wydaje sie niewiele znaczacym problemem (dla dobrze napisanego algorytmu oraz metod praktycznie nie jest to problem)

Pozdrawiam
Robert

7 | Joanna

14. listopada 2009 o 3:21 pm

Avatar

Ależ ja dostrzegam zarówno wady jak i zalety innych metod. Ta jednak przypadła mi do gustu i postanowiłam ją zgłębić, przestudiować. Może przy okazji innego projektu zainteresuję się inną metodą. Dajcie mi szansę i przejrzyjcie dalsze części serii :)

Co do trzymania ‚ścieżki gałęzi’ w bazie, to takie metody napawają mnie wstrętem. Po prostu nie znoszę redundancji danych w bazie :)

8 | Diabl0

22. maja 2010 o 1:13 am

Avatar

Miejsce dyskowe jest znacznie tańsze od mocy obliczeniowej, stąd też taka redundancja bardzo często ma znacznie więcej zalet niż wad.

A jak kogoś interesują drzewka to bardzo polecam zapoznać się także z „drzewem Depesza” – http://www.depesz.com/various/various-sqltrees.php i http://www.depesz.com/index.php/2007/07/02/drzewa-w-sqlu-metoda-pelnych-sciezek-metoda-nr-5-wg-starego-tekstu/

9 | jachu

23. maja 2010 o 1:56 pm

Avatar

Szkoda, że poradnika nie można ściągnąć w pdf ;) Wolę analizować na papierze ..

10 | Joanna

23. maja 2010 o 5:57 pm

Avatar

Kliknij na podgląd wydruku. Nie wygląda najgorzej :)

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