Qu'est-ce que le modèle d'ensemble imbriqué?

Le modèle d'ensemble imbriqué est également appelé algorithme modifié de traversée de l'arborescence de pré-ordre et constitue un moyen de stocker des données hiérarchiques dans des bases de données relationnelles. Ce modèle présente l'avantage de fournir un accès très rapide et il est préférable de le mettre en œuvre dans les hiérarchies lues plus fréquemment que celles écrites. Chaque nœud du modèle d'information se voit attribuer deux numéros stockés en tant qu'attributs. L'interrogation du modèle d'ensemble imbriqué est assez facile car les deux valeurs peuvent être utilisées pour extraire les données nécessaires. Effectuer des insertions, des suppressions, des déplacements et des mises à jour est cependant beaucoup plus fastidieux, car il peut impliquer de renuméroter les nœuds.

Généralement utilisé pour représenter des ensembles imbriqués ou des informations hiérarchiques sous la forme d'arbres, le modèle d'ensemble imbriqué a été introduit par Joe Celko. Dans ce cas, une arborescence est une structure de données contenant un certain nombre de nœuds liés. Par exemple, un nœud parent peut se connecter à plusieurs nœuds enfants et cette structure est répétée dans l'arborescence à travers plusieurs niveaux.

Les arbres sont un excellent moyen de stocker des informations dans un ordre particulier dans une base de données relationnelle, qui est un ensemble de données qui stocke des données en fonction de caractéristiques communes. Par exemple, les informations sur les produits dans la section des aliments d'un magasin peuvent commencer par les aliments, puis se transformer en fruits, en légumes et en viande. Les fruits peuvent en outre être subdivisés en baies, melons, pommes et légumes en tubercules, légumes verts et autres, et la viande en porc, mouton et veau.

Une base de données relationnelle stocke toutes ces informations dans un formulaire facile à comprendre et un modèle d'ensemble imbriqué permet de gérer efficacement l'arborescence. En utilisant l'exemple ci-dessus, le nœud racine serait un aliment, qui est représenté par deux valeurs. Étant donné que la valeur de gauche pour la nourriture est 1, les autres éléments de l’arborescence se voient attribuer un numéro à gauche, dans l’ordre. Les fruits auraient une valeur de 2 à gauche, les baies seraient de 3 et ainsi de suite. Les valeurs sont ensuite affectées du côté droit, en parcourant l’arbre, de bas en haut, jusqu’à chaque branche, jusqu’à ce que la dernière valeur soit affectée à l’alimentation du côté droit.

Chaque élément de l'arborescence se termine par deux valeurs, lft pour left et rgt pour right, qui peuvent être utilisées pour les identifier et indiquer leur relation avec les autres éléments. Par exemple, si les fruits ont une valeur de 2 et 15, tous les nœuds ayant laissé des valeurs supérieures à 2 et des valeurs correctes inférieures à 15 sont des descendants de l'arbre fruitier 2-15. Il devient facile d'extraire des informations sur tous les fruits en une fois, car ces valeurs peuvent être spécifiées dans une requête unique à la base de données.

Ce modèle est excellent pour stocker des informations auxquelles on accède souvent, mais les insertions, les suppressions et les informations de réorganisation dans le modèle d'ensemble imbriqué deviennent très fastidieuses. La réécriture des index et la renumérotation des informations peuvent entraîner le blocage de la base de données, en particulier si l’arborescence comprend désormais des centaines de milliers de nœuds. Le modèle d'ensemble imbriqué convient parfaitement aux systèmes de gestion de contenu légers comportant un nombre réduit d'insertions et de modifications. Les insertions peuvent être réalisées beaucoup plus rapidement dans le modèle d'intervalle imbriqué car il stocke la position de chaque nœud dans l'arborescence à l'aide de décimales à virgule flottante tout en codant les informations de chemin.