La représentation intervallaire (ou MPTT)

La représentation intervallaire est une technique qui permet de gérer une arborescence dans une base de données relationnelle.

Prenons par exemple les catégories d'un site ou d'un blog :

Graphisme               #1
	Photoshop           #2
		Retouche photo  #3
		Dessin          #4
		Typographie     #5
	GIMP                #6
Vidéo/3D                #7
	After Effects       #8
	Premiere Pro        #9
	3D Studio Max       #10
	Cinema 4D           #11
Programmation           #12
	Web                 #13
		PHP             #14
			Symfony     #15
		Wordpress       #16
		Javascript      #17
			jQuery      #18
			Mootools    #19
	Base de donnée      #20
		MySQL           #21
		MongoDB         #22

Ces catégories peuvent s'imbriquer les unes dans les autres.

La méthode récursive

Pour stocker ces catégories dans une base de données comme MySQL, le méthode conventionnelle c'est d'utiliser une table comme celle-ci, avec un champ parent_id qui fait référence à la catégorie parente (héritage) :

CREATE TABLE `categories` (
	`id` INT(11) NOT NULL AUTO_INCREMENT,
	`parent_id` INT(11) NULL DEFAULT NULL,
	`titre` VARCHAR(250) NULL DEFAULT NULL,
	`description` TEXT NULL,
	PRIMARY KEY (`id`)
)

L'énorme inconvénient de cette approche, c'est qu'elle ne permet pas de manipuler l'arbre des catégories facilement.

Imaginons qu'on souhaite récupérer la catégorie Web, ainsi que toutes ses sous catégories : il faut d'abord récupérer la liste de tous les enfants directs de la catégorie web : PHP, Wordpress, Javascript, avec une requête SQL comme celle-ci :

SELECT * FROM categories WHERE parent_id = 13

Puis il faudrait répéter l'opération pour toutes les catégories enfant de premier niveau retournées par la requête ci-dessus, comme ceci :

SELECT * FROM categories WHERE parent_id IN(14, 16, 17)

Et ainsi de suite, jusqu'aux catégories qui n'ont pas de sous catégorie (qu'on appelle des feuilles, au passage (leaf en anglais)). Le nombre de requêtes SQL à exécuter dépend de la profondeur de l'arbre, c'est pour cette raison que cette première technique s'appelle la méthode récursive (on l'appelle aussi parfois liste d'adjacence mais c'est plus rare). C'est une catastrophe d'un point de vue des performances, et ça n'est pas pratique d'un point de vue programmation.

Représentation intervallaire

La représentation intervallaire, qu'on appelle aussi MPTT en anglais (Modified Preorder Tree Traversal) permet de résoudre tous les problèmes de performances de la méthode récursive.

L'idée c'est d'utiliser 2 champs supplémentaires que l'on attribue à chaque noeud de l'arbre (à chaque catégorie dans notre exemple) :

• bord gauche, que l'on nomme par convention lft (pour left)
• bord droit, que l'on nomme rgt(pour right)

Ces deux champs correspondent aux bornes d'un intervalle. J'ai représenté ces intervalles sur cette image :

Voici un billet similaire qui vous permettera d'en savoir plus sur comparer 2 colonnes dans excel.

Grâce à ces 2 champs, on peut très facilement récupérer toutes les sous catégories, on peut aussi obtenir la liste des catégories parentes pour construire un fil d'ariane (breadcrumb), le tout en une seule requête SQL à chaque fois, comme celles-ci :

Sous catégories de la catégorie Graphisme :

SELECT * FROM categories WHERE lft BETWEEN 1 AND 12

Catégories parentes de la catégorie jQuery :

SELECT * FROM categories WHERE lft < 32 AND rgt > 33 ORDER BY lft ASC

Le MPTT est conçu pour optimiser les performances en lecture. Le revers de la médaille est qu'il faut maintenir à jour la valeur des champs bord gauche et bord droit, à chaque fois qu'on ajoute de nouvelles catégories ou qu'on déplace des catégories dans l'arbre. Ces traitements diminuent les performances en écriture, mais ça n'est pas gênant puisqu'en général les écritures sont beaucoup moins fréquentes que les écritures.

Certains framework gèrent nativement la représentation intervallaire et la maintenance des bords, comme CakePHP et son Tree Behavior. Si vous n'utilisez pas CakePHP, la bonne méthode pour maintenir un arbre est de vous créer une classe qui va faire office de modèle (en référence à l'architecture Modèle Vue Controlleur) pour gérer les noeuds de l'arbre.

Inutile de perdre du temps à écrire des algorithmes de mise à jour des bords, il en existe déjà, je vous invite à lire cet excellent tutoriel : http://www.sitepoint.com/hierarchical-data-database-3/.

Allez donc jeter un oeil sur cette page : déverouiller le calque arrière plan.