Méthode de stockage de structure de données arborescente (requête)

Modèle de liste de contiguïté

Dans le développement commercial quotidien, nous rencontrons souvent des données arborescentes avec une structure hiérarchique. Lorsqu'elle est stockée dans une base de données relationnelle, cette structure de données est souvent stockée dans un modèle appelé liste de contiguïté, comme ceci :

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `pid` int(11) DEFAULT 0,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

Ce modèle représente L'image montre :

Je pense que beaucoup de gens connaissent déjà ce modèle de données, je n'entrerai donc pas trop dans les détails ici. Concentrons-nous sur le modèle de données suivant

Modèle d'ensemble imbriqué

Une autre façon de représenter un arbre est de le stocker sous forme d'ensemble. Nous redéfinissons la structure de table suivante :

CREATE TABLE `categories` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `title` char(100) NOT NULL,
  `lft` int(11) NOT NULL UNIQUE CHECK (lft> 0),
  `rgt` int(11) NOT NULL UNIQUE CHECK (rgt> 1),
  PRIMARY KEY (`id`)
) ENGINE=InnoDB;

Et le schéma de ce modèle ressemblera à ce qui suit :

lft et rgt sont utilisés comme limite de l'ensemble. Plus la différence entre les deux est grande, plus l'ensemble est grand et plus il contient d'éléments.

Selon le sous-ensemble, trouvez la catégorie du parent

SELECT c2.* 
  FROM categories as c1, categories as c2
  WHERE c1.lft BETWEEN c2.lft and c2.rgt 
      AND c1.title = '华为';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  5 | Harmony OS  |  10 |  13 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

Selon le parent, trouvez tous les sous-ensembles en dessous

SELECT c1.*
   FROM categories AS c1, categories AS c2
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
    AND c2.title = 'Smartphones';
+----+-------------+-----+-----+
| id | title       | lft | rgt |
+----+-------------+-----+-----+
|  1 | Smartphones |   1 |  14 |
|  3 | Android     |   2 |   5 |
|  4 | iOS         |   6 |   9 |
|  5 | Harmony OS  |  10 |  13 |
|  6 | 小米        |   3 |   4 |
|  7 | iPhone      |   7 |   8 |
|  8 | 华为        |  11 |  12 |
+----+-------------+-----+-----+

Voir le niveau de chaque catégorie

 SELECT COUNT(c2.id) AS indentation, c1.title
  FROM categories AS c1, categories AS c2下周三we'fv
  WHERE c1.lft BETWEEN c2.lft AND c2.rgt
  GROUP BY c1.title
  ORDER BY c1.lft;
+-------------+-------------+
| indentation | title       |
+-------------+-------------+
|           1 | Smartphones |
|           2 | Android     |
|           3 | 小米        |
|           2 | iOS         |
|           3 | iPhone      |
|           2 | Harmony OS  |
|           3 | 华为        |
+-------------+-------------+

Avantages et inconvénients

Modèle de liste de contiguïté

Le modèle de liste de contiguïté est facile à comprendre et le code dont nous avons besoin l'est également très simple.

Mais dans la plupart des langages de programmation, c'est lent et inefficace. Ceci est principalement dû à la récursion. Nous devons effectuer une requête de base de données pour chaque nœud de l'arborescence.

Cela peut rendre la fonction très lente lorsqu'il s'agit de grands arbres puisque chaque requête prend un certain temps. Car pour chaque fonction, un algorithme récursif est nécessaire pour obtenir le nombre.

Bien sûr, si vous utilisez un langage récursif comme List, vous pouvez ignorer les lacunes de ce modèle de données. Mais pour PHP, cela rendra l’ensemble du traitement de ce modèle de données extrêmement lent.

Modèle d'ensemble imbriqué

Comparé au modèle de liste de contiguïté, ce modèle de données n'est évidemment pas si facile à comprendre. Et il ne peut pas être aussi simple d'ajouter des données. Il faut calculer les valeurs sur les côtés gauche et droit lors de l'ajout et déplacer les valeurs suivantes, ce qui augmente la pression de l'ajout de données.

De même, l'avantage qu'il apporte est qu'il vous permet de compléter une requête arborescente avec une simple requête, et vous pouvez calculer le nombre de sous-éléments qu'elle contient en fonction des deux paramètres lft et rgt.

Résumé

Les deux modèles ont leurs propres avantages et inconvénients, l'un est meilleur que l'insertion et l'autre est meilleur que la requête. Bien que je préfère le modèle d’ensembles imbriqués, il doit néanmoins être choisi en fonction de l’activité spécifique.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!