Destul de des se întâmplă ca să trebuiască să stocăm informații aflate sub formă de arbori (ex. posturi de pe un forum) într-o bază de date. Problema este că ma­jori­tatea bazelor de date sunt liniare și trebuie să trans­for­măm in­for­mați­ile noastre într-o variantă liniară.

Să considerăm că avem următorul arbore cu uti­liza­tori, grupați în diferite categorii:

O metodă naivă de stocare ar fi să stocăm lângă fiecare nod și părintele său. Astfel, în tabelul users am avea:


id   user   parent


Problema este că pentru a obține arborele din baza de date, trebuie să apelăm recursiv un query către baza de date, ceea ce nu îi bine deoarece unul din cele mai mari blocaje într-o aplicație (web) este legătura cu baza de date.

În cazul nostru am obține următorul tabel:


id   user   left   right


Pare mai complicat la prima vedere, dar este mai ușor de manipulat. O pro­pri­etate care se observă este că nodurile de­scen­dente au în­tot­deau­na marginile cuprinse între valorile marginilor nodului părinte.

Pentru a obține ancestorii unui anumit nod, folosim următoarea comandă MySQL:

SELECT user FROM users WHERE left < (SELECT left FROM users WHERE user = 'rolisz' ) AND right > (SELECT right FROM users WHERE user = 'rolisz') ORDER BY left

Această comandă ne returna 3 rânduri care conțin: Users, Mods, Admins.

Când inserăm un nod, va trebui să modificăm toate marginile care urmează după el. Pentru aceasta trebuie să știm valoarea din dreapta a nodului după care vrem să adăugăm. Să zicem că vrem să inserăm după Admins un moderator nou. Valoare din dreapta la Admins este 10.

UPDATE users SET left = left +2 WHERE left>10

UPDATE users SET right = right +2 WHERE left>10

INSERT INTO users (user, left, right) VALUES (`new_mod`, 11, 12)

Pentru a șterge facem invers, scădem 2 din marginile nodurilor care urmează.