PUBLIC MARKS with tags arbre & sql

Représentation intervallaire des arborescences

Dans le cadre d’un projet que je développe en ce moment, j’ai besoin de stocker un arbre dans une base de données, c’est à dire un groupe d’éléments reliés par une relation de type parent-enfant.

Miguel Sofer, dans le travail de recherche qu'il a effectué présente une méthode novatrice. Il s'agit d'ajouter une colonne à toute table stockant les noeuds de l'arbre. Grâce à un encodage particulier, on arrive ainsi à savoir très rapidement : * quel est le niveau du noeud dans l'arbre ; * quel est le père d'un noeud dans l'arbre ; * quel est la lignée d'un noeud de l'arbre ; * etc. Il démontre son efficacité de manière mathématique, et propose des exemples de code d'implémentation en PostgreSQL !

Il s'agit de modéliser un arbre en sachant à l'avance quelle sera la "largeur" de celui-ci. C'est à dire que pour un arbre donné, la racine ira de 1 à n, le premier fils de la racine, de 1 à m. Le second fils de la racine, de m+1 à n et ainsi dessuite pour les descendants.