Ensembles imbriqués Nested set
Un modèle d'arbre où chaque nœud reçoit deux nombres — une valeur gauche et une valeur droite — attribués en « faisant le tour » de l'arbre. Un sous-arbre devient alors un simple intervalle : tous les descendants d'un nœud ont des valeurs gauche/droite comprises dans les siennes. Lectures rapides, modifications coûteuses.
Le mécanisme : on parcourt l'arbre en pré-ordre et on numérote chaque nœud en « descendant » (gauche) puis en « remontant » (droite). Le gain : « récupérer tout le sous-arbre » devient WHERE lft BETWEEN node.lft AND node.rgt — une seule requête d'intervalle, rapide, sans récursion, et le nombre de descendants se calcule par simple arithmétique. Le prix : insérer ou déplacer un nœud oblige à renuméroter une grande partie de l'arbre (tous les nœuds aux valeurs supérieures doivent être décalés) → très coûteux quand les changements sont fréquents. Le mieux adapté : les hiérarchies lues souvent et modifiées rarement (l'arbre des catégories d'une boutique). Plus complexe que la liste d'adjacence, mais plus rapide pour lire des sous-arbres. La table de fermeture offre un compromis. À rapprocher du chemin matérialisé et de la table de fermeture.