Aller au contenu principal

Représentation intervallaire (nested sets)

Le modèle d’adjacency list (parent_id) est simple, mais certaines requêtes deviennent complexes, surtout :

  • récupérer tous les descendants d’un nœud,
  • récupérer le chemin complet d’un nœud.

La représentation intervallaire ou modèle d’ensembles imbriqués (Nested Sets) résout ce problème en attribuant à chaque nœud deux valeurs entièrement déterministes :

inf (gauche) sup (droite)

Ces valeurs définissent un intervalle [inf, sup] qui contient tous les descendants du nœud.

Principe​

Chaque nœud reçoit deux nombres (inf et sup) de telle sorte que :

  • la racine a l’intervalle le plus large [1, 2n] pour n nœuds,
  • un enfant est strictement inclus dans l’intervalle de son parent,
  • aucun nœud n’a un intervalle qui chevauche celui d’un nœud non descendant.

La représentation intervallaire est très efficace pour les lectures d’arbres complexes. Elle est particulièrement adaptée aux arbres stables. En cas de modifications il faut recalculer les bornes de tous les noeuds.

SELECT *
FROM famille
WHERE inf BETWEEN 2 AND 7
ORDER BY inf;

Récupérer tous les ancêtres​

SELECT *
FROM familles
WHERE inf <= 5 AND sup >= 6
ORDER BY inf;

Calculer la profondeur​

SELECT COUNT(parent.id) AS profondeur
FROM famille AS node
JOIN famille AS parent
  ON parent.inf < node.inf AND parent.sup > node.sup
WHERE node.code = '02CUCURB';