Dane testowe
We wszystkich przykładach będę się odwoływał do poniższego drzewa:
(jeśli poniższy graf masz przekoszony użyj czcionki nieproporcjonalnej,
np.courier).
sql
/ \
postgresql oracle-----__
| / | \
linux solaris linux windows
/ \
glibc1 glibc2
Metoda 1
Oddzielne table na każdy poziom zagnieżdżenia danych. W tym przypadku byłoby to:
tree_level_1 (id, name) :
(1,sql);
tree_level_2 (id, parent_id, name) :
(1, 1, postgresql),
(2, 1, oracle);
tree_level_3 (id, parent_id, name) :
(1, 1, linux),
(2, 2, solaris);
(3, 2, linux);
(4, 2, windows);
tree_level_4 (id, parent_id, name) :
(1, 3, glibc1),
(2, 3, glibc2);
Metoda ta wybierana jest najczęściej przez początkujących programistów.
Bardziej doświadczeni bazo-danowcy, odrzucają ją ze względu na
koniecznośc modyfikowania *struktury bazy danych* przy zmianie danych!!!
Praktycznie rzecz biorąc nie powinna być nigdy stosowana.
Cechy:
+ trywialne w implementacji
+ dosyć szybkie tworzenie pełnej nazwy (z zastrzeżeniem o znajdywaniu danych konkretnego (początkowego) ID)
- skomplikowane wyszukiwanie danych na podstawie konkretnego "ID"
- ograniczona ilość poziomów zagnieżdżeń
- bardzo wolne znajdowanie np. wszystkich książek w kategorii "informatyka" i podkategoriach informatyki (dowolnie głęboko)
- wolne wyszukiwanie podkategorii niebezpośrednich.
Metoda 2
Tabela typu:
create table kategorie (
id serial,
parent_id int8,
name text not null default '',
primary key (id)
);
create unique index ui_kategorie_pin on kategorie (parent_id, name);
alter table kategorie add foreign key (parent_id) references kategorie (id);
Cechy:
+ trywialne w implementacji
+ nieograniczona ilość poziomów zagnieżdżeń
+ błyskawiczne wyszukiwanie podkategoriii danej kategorii
- wolne tworzenie pełnej nazwy (chyba, że przechowujesz ją w polu name, ale to marnotrawstwo miejsca)
- bardzo wolne znajdowanie np. wszystkich książek w kategorii "informatyka" i podkategoriach informatyki (dowolnie głęboko)
- wolne wyszukiwanie podkategorii niebezpośrednich.
Metoda 3
Układ typu nested sets (vide książka "SQL - zaawansowane programowanie", autor:
Joe Celko).
Tabela plus minus jak wyżej, ale zamiast parent_id jest left_mark i right_mark.
Left_mark i right_mark są wyliczane.
Przykład (w nawiasach przy nazwie odpowiednio: left_mark, right_mark).
| (1, 18) | sql |
| (2, 5) | sql/postgresql |
| (6, 17) | sql/oracle |
| (3, 4) | sql/postgresql/linux |
| (7, 8) | sql/oracle/solaris |
| (9, 14) | sql/oracle/linux |
| (15, 16) | sql/oracle/windows |
| (10, 11) | sql/oracle/linux/glibc1 |
| (12, 13) | sql/oracle/linux/glibc2 |
Wartości left/right mark są nadawane w następujący sposób: zaczynając od
konkretnego miejsca w drzewie, nadajemy mu kolejny numer (np. 1), i znajdujemy
pierwsze "dziecko". "Pierwsze" definiujemy w dowolny sposób - tu akurat użyłem
odwzorowania graficznego.
Jeśli dany element nie posiada "dzieci", zwiekszam licznik o jeden, ustawiam
right-mark oraz wraz z numerowaniem jeden poziom w górę.
Przykład:
Zaczynam od "sql". Ustawiam mu left-mark na 1, znajduję pierwsze "dziecko" -
czyli postgresql, ustawiam mu left-mark na 2, znajduję kolejne pierwsze "dziecko"
czyli "linux", ustawiam mu left-mark na 3.
Ponieważ "linux" nie ma "dzieci", ustawiam mu right-mark na 4, po czym wracam
poziom wyżej.
"postgresql" nie ma innych dzieci, więc dostaje right-mark 5 i idę do kolejnego
"dziecka" sql -> czyli "oracle".
Proces powtarzam, aż wrócę do "sql" i nadam mu right-marka.
Cechy:
+ niesamowicie szybkie wyszukiwanie w dół drzewa od określonego elementu (zakładając wyszukiwanie bez limitu głębokości)
+ nieograniczona ilość poziomów zagnieżdżeń
- nietrywialne w implementacji
- dużo więcej pracy przy wstawianiu i usuwaniu elementów
- utrudnione wyszukiwanie bezpośrednich podkategorii danej kategorii.
Metoda 4
Metoda 1 + metoda 2, czyli wykorzystanie i parent_id i left/right mark-ów.
Opisu nie będę robił, bo jest oczywisty.
Cechy:
+ nieograniczona ilość poziomów zagnieżdżeń
+ błyskawiczne wyszukiwanie podkategoriii danej kategorii
+ niesamowicie szybkie wyszukiwanie w dół drzewa od określonego elementu (zakładając wyszukiwanie bez limitu głębokości)
- sporo pracy przy wstawianiu i usuwaniu elementów
- nietrywialne w implementacji
- nadmiarowość informacji (choć w bazach danych to raczej standard)
Metoda 5
Wymyśliliśmy ją z współpracownikami w trakcie pracy nad jednym z wspólnych projektów.
2 tabele:
create table kategorie (
id serial,
name text,
primary key (id)
);
-- ważne: name nie jest unique !!!!
create table powiazania (
first_id int8,
second_id int8,
depth int8,
primary key (first_id, second_id)
);
alter table powiazania add foreign key (first_id) references kategorie (id);
alter table powiazania add foreign key (second_id) references kategorie (id);
Pole depth oznacza, o ile poziomów "głębiej" jest kategoria second od first.
Np. dla sytuacji z metody 2:
kategorie:
id | name
----+------------
1 | sql
2 | postgresql
3 | oracle
4 | linux
5 | solaris
6 | linux
7 | windows
8 | glibc1
9 | glibc2
powiazania:
first_id | second_id | depth
----------+-----------+-------
1 | 2 | 1
1 | 3 | 1
1 | 4 | 2
1 | 5 | 2
1 | 6 | 2
1 | 7 | 2
1 | 8 | 3
1 | 9 | 3
2 | 4 | 1
3 | 5 | 1
3 | 6 | 1
3 | 7 | 1
3 | 8 | 2
3 | 9 | 2
6 | 8 | 1
6 | 9 | 1
Ze względów wydajnościowych oraz ułatwiajacych programowanie polecam dopisywanie
dodatkowo powiazań z głębokością 0, czyli w naszym przypadku 9 rekordów:
first_id | second_id | depth
----------+-----------+-------
1 | 1 | 0
2 | 2 | 0
3 | 3 | 0
4 | 4 | 0
5 | 5 | 0
6 | 6 | 0
7 | 7 | 0
8 | 8 | 0
9 | 9 | 0
Może nie wydaje się to bardzo potrzebne, ale wiele razy okazało się, że taka
dodatkowa ilość danych bardzo ułatwia późniejsze oprogramowywanie.
Zwrócić należy uwagę, że ilość dodatkowych danych jakie trzeba przechowywać
jest zależna od maksymalnej głębokości zagnieżdżenia drzewa.
W skrajnym przypadku ilość danych które trzeba zapisać jest zbliżona do
(n^2)/2 * wielkość rekordu w tablicy powiązania.
W praktyce jednak zazwyczaj nie przekracza się wartości 2n do 3n, co oznacza,
że do zapisania drzewa ze 100 elementami potrzebujemy (zazwyczaj) około
200-300 rekordów w tablicy powiązania. A dzięki temu, że dane tam są proste
(3 pola typu INT), wielkość pojedyńczego rekordu wynosi 12 (lub 24 dla INT8)
bajtów - co nie jest wielką wartością.
Cechy:
+ relatywnie proste w implementacji
+ nieograniczona ilość poziomów zagnieżdżeń
+ błyskawiczne wyszukiwanie podkategoriii danej kategorii
+ niesamowicie szybkie wyszukiwanie w dół rzewa od określonego elementu
(niezależnie od tego, czy z limitem, czy bez limitu głębokości)
+ proste wstawianie i usuwanie rekordów
+ szybkie (dużo szybsze niż w jakiejkolwiek innej implementacji) tworzenie pełnych nazw
+ szybkie wyszukiwanie kategorii niebezpośrednich (np. znajdź wszystkie podkategorie
podkategorii "informatyki". czyli np. informatyka/podręczniki/sql tak, ale informatyka/sql już nie)
- nadmiarowość informacji (choć w bazach danych to raczej standard).
Więcej o drzewach w SQL:
|