Stocarea de arbori în baze de date relaționale

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ă.