Ponownie mam do zaproponowania ciekawe rozwiązanie dość powszedniego problemu - tym razem padło na sposób reprezentacji drzewiastego forum w bazie danych. Drzewiasty oznacza w tym momencie, iż odpowiedź na daną wiadomość pojawia się pod tą wiadomością (coś w stylu komentarzy w serwisie onet.pl).

Założenia naszego forum są następujące:

• możliwość odpowiedzi na wiadomość,
• ograniczenie zagnieżdżenia (np możemy odpowiadać maksymalnie do 5 poziomu zagnieżdżenia),
• każdy temat (główna wiadomość) oraz wiadomości mają takie same pola: tytuł, treść, data dodania, autor.

Zatem nasza baza danych (w wersji uproszczonej) wygląda mniej więcej tak:

id parent_id title …. 1 0 Wątek główny …. 2 1 Wiadomość pierwsza …. 3 1 Wiadomość druga …. 4 2 Wiadomość pod pierwszą ….

Przy czym zakładamy, iż jeżeli parent_id jest równe 0 to dana pozycja jest tematem.

W tym momencie pojawia się jednak problem z generowaniem wpisów - na przykład dla prostego scenariusza “wyświetl wszystkie odpowiedzi na wiadomość o id 1 w strukturze drzewiastej”. Przy tej strukturze bazy jest to wręcz niemożliwe, ponieważ nie wiemy ile należy zrobić połączeń (ang. inner join) tabeli forum i o ile pobranie pierwszego poziomu jest stosunkowo łatwe to już następnych dużo trudniejsze.

Rozwiązaniem jest dodanie nowego pola do bazy danych (nazwijmy je path) typu VARCHAR, które będzie przechowywało ścieżkę zagnieżdżenia danej pozycji. Budowa tejże ścieżki wygląda następująco:

• pobierz id wszystkich swoich przodków w kolejności rosnącej (np. dla pozycji “Wiadomość pod pierwszą” będzie to zbiór 1, 2)
• stwórz z nich liczby o stałej liczbie cyfr, nazwijmy ją SLC, (*) przez dodanie na początku odpowiedniej liczby zer (np. 0001, 0002)
• konkatenacja tych liczb oddzielona określonym znakiem (**) staje się poszukiwana ścieżką (np. 0001|0002|)

(*) Określenie tej liczby ogranicza maksymalną liczbę wiadomości np. jeżeli wyniesie ona 6 będziemy mogli dodać maksymalnie niecałe milion wiadomości (zakres id wyniesie wówczas 1 - 999.999). W dalszej części dla prostoty założę, iż wynosi ona 4.
(**) W dalszej części znakiem tym będzie ‘|’

id parent_id title …. path 1 0 Wątek główny …. 2 1 Wiadomość pierwsza …. 0001| 3 1 Wiadomość druga …. 0001| 4 2 Wiadomość pod pierwszą …. 0001|0002|

Teraz wcześniej podany scenariusz nie sprawia nam żadnego problemu a zapytanie wygląda następująco:

Pozostaje kwestia jak budować tą niezastąpioną magiczną wartość? Opis wydaje się być dość złożony jednak w praktyce jest bardzo prosty, a to ze względu na fakt, iż ścieżka danej pozycji składa się z ścieżki jej ojca w połączeniu z parent_id. Czyli podczas dodawania nowej wiadomości ścieżkę tworzymy na podstawie jej ojca, oto przykładowy kod w PHP:

Przydatne właściwości:

• na podstawie ścieżki możemy obliczyć poziom zagnieżdżenia, wystarczy podzielić długość ciągu przez SLC+1, w naszym przypadku dla pozycji o id 4 wygląda to następująco: długość pola path wynosi 10, wartość SLC wynosi 4, w związku z czym poziom zagnieżdżenia wynosi 10 / (4+1) = 2.
• dzięki sortowaniu po path mamy pewność, iż pozycje są w odpowiedniej kolejności (na końcu ostatnie wiadomości). Właśnie dlatego podczas budowania ścieżki zapewniamy stałą liczbę cyfr, dzięki temu sortowanie leksykograficzne ma sens.

Uwagi:

• przy tym rozwiązaniu zakładamy, iż im później dodana pozycja tym większy ma id, w przeciwnym przypadku sortowanie po path mija się z celem.
• w przykładzie pole path jest typu VARCHAR, dlatego też aby nie przekroczyć maksymalnej długości ścieżki należy odpowiednio dostosować wartości SLC oraz poziom zagnieżdżenia (na przykład dla SLC równej 6 oraz pola długości 64 maksymalne zagnieżdżenie wynosi 9)
• na pole path należy założyć index, dzięki czemu wyszukiwanie będzie znacznie szybsze - pod warunkiem jednak, iż warunek będzie w postaci “kod|%”.