Tym razem nie będzie nic o implementacji pewnej struktury drzewiastej w php. Natomiast zajmiemy się dziś sql. A dokładniej PostgreSQL, od dłuższego czasu nie mogłem ogarnąć modułu w postgresql, który nazywa się ltree, jak sama cząstkowa nazwy wskazuje i łatwo się domyślić że chodzi tutaj o reprezentację i strukturę drzewa. Co najlepsze, przeprowadzone benchmarki przez jego twórców wykazują na największy w śród tymczasowych ogólnie dostępnych wzorców tego typu struktury czas dostępu do danych.

Trochę historii
W 2002 roku, dwóch programistów: Teodor Sigaev oraz Oleg Bartunov, wypuściło na światło dzienne moduł ltree (kiedy zaczęli, brak danych). Podeszli do tego dość ogólnego problemu z wielkim dystansem, za to teraz mamy potężne narzędzie całkowicie za darmo. Następne wydania miały na celu wyeliminowanie błędów zgłoszonych przez użytkowników oraz rozszerzyć możliwości o nowe możliwości w indeksie GIST. Więcej na temat samych wydań jak zwykle w paczce do pobrania z ich strony na dole.

Z czym to się je?
Ltree jak już wyżej wspomniałem jest modułem do PosgreSQL’a mający za zadanie przechowywanie danych w sposób przedstawiający strukturę drzewiastą. Implementacja jak najbardziej wydajna. A więc zacznijmy.

W zależności od dystrybucji z jakiej korzystamy, możemy mieć lub nie dodatkową paczkę dla postgresql’a która powinna się nazywać mniej więcej tak: postgresql-contrib

Po zainstalowaniu tych dodatków mamy masę innych rzeczy, z których nie koniecznie będziemy korzystać. Ale nas interesuje ltree, ścieżka ltree.sql u mnie to:

/usr/share/postgresql/8.4/contrib/

a żeby wyszukać gdzie my to mamy:

locate ltree.sql

po wcześniejszym updatedb.

powinniśmy mieć tam plik ltree.sql, musimy ten plik wrzucić do naszej bazy danych. No to jedziemy:

psql nazwaDB < /usr/share/postgresql/8.4/contrib/ltree.sql

powinniśmy mieć wszystko ładnie wrzucone do bazy danych. Teraz zostało nam już tylko utworzenie tabeli i ogień.

Przykładowa tabela z naszym drzewem.

CREATE TABLE "tree" (
   "id"  SERIAL NOT NULL,
   "path"   LTREE,
   "sort" SMALLINT
);

mamy tutaj tabelę którą nazywamy tree, i teraz nowy typ danych LTREE. Nie ma co tu dużo tłumaczyć zaraz sami zobaczycie jak to działa.

Pozostało nam jeszcze założyć indeksy na kolumny:

CREATE INDEX path_gist_idx ON "tree" USING gist(path);
CREATE INDEX path_idx ON "tree" USING btree(path);

oraz możemy sobie w prosty sposób komentarze na kolumny powrzucać:

COMMENT ON COLUMN "tree"."path" IS 'Scieżka drzewa';

Żeby zobaczyć komentarz w psql należy wykonać polecenie:

\d+ "nazwaTabeli"

A teraz dane przykładowe do drzewa:

INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top', 1);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Science', 1);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Science.Astronomy', 1);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Science.Astronomy.Astrophysics', 1);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Science.Astronomy.Cosmology', 2);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Hobbies', 2);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Hobbies.Amateurs_Astronomy', 2);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Collections', 3);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Collections.Pictures', 1);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Collections.Pictures.Astronomy', 1);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Collections.Pictures.Astronomy.Stars', 1);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Collections.Pictures.Astronomy.Galaxies', 2);
INSERT INTO "tree" ( "path", "sort" ) VALUES ('Top.Collections.Pictures.Astronomy.Astronauts', 3);

Jak zauważyliście, dane w ścieżce drzewa nie mogą posiadać wolnej przestrzeni, więc należy ją zamienić na np „_”, co nie jest żadnym problemem.

Ścieżka rysuje się mniej więcej tak:



Pobierzmy sobie teraz całe drzewko:

ltree=> SELECT * FROM tree;
 id |                     path                      | sort
----+-----------------------------------------------+------
  1 | Top                                           |    1
  2 | Top.Science                                   |    1
  3 | Top.Science.Astronomy                         |    1
  4 | Top.Science.Astronomy.Astrophysics            |    1
  5 | Top.Science.Astronomy.Cosmology               |    2
  6 | Top.Hobbies                                   |    2
  7 | Top.Hobbies.Amateurs_Astronomy                |    2
  8 | Top.Collections                               |    3
  9 | Top.Collections.Pictures                      |    1
 10 | Top.Collections.Pictures.Astronomy            |    1
 11 | Top.Collections.Pictures.Astronomy.Stars      |    1
 12 | Top.Collections.Pictures.Astronomy.Galaxies   |    2
 13 | Top.Collections.Pictures.Astronomy.Astronauts |    3
(13 rows)

I wszystko wygląda fajnie co? Ale tu się zaczynają schody z którymi ja sam nie potrafiłem sobie poradzić. I po raz któryś poprosiłem depesz’a o pomoc. Sprawa ma się tak: Jak pobrać drzewo z posortowanymi gałęziami względem głębokości? No i tutaj był mój pies pogrzebany. Ale z pomocą przyszedł depesz, ale do sedna sprawy. Dodajmy sobie z 3 rekordy do naszej tabeli:

 INSERT INTO tree (path,sort) VALUES ('Top.Science.Programing',2);
 INSERT INTO tree (path,sort) VALUES ('Top.Science.Chemia',3);
 INSERT INTO tree (path,sort) VALUES ('Top.Science.Fizyka',4);

Teraz nasze drzewko będzie wyglądało tak:

 id |                     path                      | sort
----+-----------------------------------------------+------
  1 | Top                                           |    1
  2 | Top.Science                                   |    1
  3 | Top.Science.Astronomy                         |    1
  4 | Top.Science.Astronomy.Astrophysics            |    1
  5 | Top.Science.Astronomy.Cosmology               |    2
  6 | Top.Hobbies                                   |    2
  7 | Top.Hobbies.Amateurs_Astronomy                |    2
  8 | Top.Collections                               |    3
  9 | Top.Collections.Pictures                      |    1
 10 | Top.Collections.Pictures.Astronomy            |    1
 11 | Top.Collections.Pictures.Astronomy.Stars      |    1
 12 | Top.Collections.Pictures.Astronomy.Galaxies   |    2
 13 | Top.Collections.Pictures.Astronomy.Astronauts |    3
 14 | Top.Science.Programing                        |    2
 15 | Top.Science.Chemia                            |    3
 16 | Top.Science.Fizyka                            |    4
(16 rows)

Co nas w ogóle nie zadowala, próbowałem na różne sposoby:

1 by depesz:

10:12 < depesz> cojack: i think you will need to sort on subltree(path, 0, nlevel(path)-2), sort;

No to jedziemy

ltree=> SELECT * FROM tree ORDER BY subltree(path, 0, nlevel(path)-2), sort;
ERROR:  invalid positions

A dziwne bo wcześniej działało ^^

2 moja

SELECT id, subpath(path, -1) AS title, nlevel(path) AS depth, sort FROM tree ORDER BY subltree(path, 0, nlevel(path)) ASC;
 id |       title        | depth | sort
----+--------------------+-------+------
  1 | Top                |     1 |    1
  8 | Collections        |     2 |    3
  9 | Pictures           |     3 |    1
 10 | Astronomy          |     4 |    1
 13 | Astronauts         |     5 |    3
 12 | Galaxies           |     5 |    2
 11 | Stars              |     5 |    1
  6 | Hobbies            |     2 |    2
  7 | Amateurs_Astronomy |     3 |    2
  2 | Science            |     2 |    1
  3 | Astronomy          |     3 |    1
  4 | Astrophysics       |     4 |    1
  5 | Cosmology          |     4 |    2
 15 | Chemia             |     3 |    3
 16 | Fizyka             |     3 |    4
 14 | Programing         |     3 |    2
(16 rows)

I tutaj można zauważyć że mamy już względnie posortowane według kategorii ale wciąż brak posortowania względem sort po prostu, no i trzecia ostateczna (chyba) propozycja wg depesza podejście drugie:

WITH RECURSIVE rec AS (
SELECT *, btrim(to_char( sort, '0000000' )) AS ordering FROM tree WHERE nlevel(path) = 1
UNION ALL
SELECT t2.*, t1.ordering || '/' || btrim(to_char( t2.sort, '0000000' )) AS ordering FROM rec t1, tree t2 WHERE t1.path @> t2.path AND nlevel(t1.path) + 1 = nlevel(t2.path)
)
SELECT id, subpath(path, -1) AS title, nlevel(path) AS depth, sort FROM rec ORDER BY ordering;
 
 id |       title        | depth | sort
----+--------------------+-------+------
  1 | Top                |     1 |    1
  2 | Science            |     2 |    1
  3 | Astronomy          |     3 |    1
  4 | Astrophysics       |     4 |    1
  5 | Cosmology          |     4 |    2
 14 | Programing         |     3 |    2
 15 | Chemia             |     3 |    3
 16 | Fizyka             |     3 |    4
  6 | Hobbies            |     2 |    2
  7 | Amateurs_Astronomy |     3 |    2
  8 | Collections        |     2 |    3
  9 | Pictures           |     3 |    1
 10 | Astronomy          |     4 |    1
 11 | Stars              |     5 |    1
 12 | Galaxies           |     5 |    2
 13 | Astronauts         |     5 |    3
(16 rows)

Dziękuje nie mam do Pana więcej pytań, rozwalił mnie jego poziom wiedzy.

To co tutaj przedstawiłem to tylko przedsmak tego co dzięki tej sposobności możemy doświadczyć, a są to:

  1. ACL
  2. RBAC
  3. Hierarchia grup
  4. Drzewa ^^

Nie będę opisywał funkcji jakie są dostępne w tym module, a na pewno nie w tym wpisie. Chciałem przedstawić że coś takiego istnieje, gdyż bardzo mało osób wie o tym, nie zdaje sobie sprawy z potężnej mocy jaką to posiada.