Question Quelle est la manière la plus efficace / élégante d'analyser une table plate dans un arbre?


Supposons que vous avez une table plate qui stocke une hiérarchie arborescente ordonnée:

Id   Name         ParentId   Order
 1   'Node 1'            0      10
 2   'Node 1.1'          1      10
 3   'Node 2'            0      20
 4   'Node 1.1.1'        2      10
 5   'Node 2.1'          3      10
 6   'Node 1.2'          1      20

Voici un diagramme, où nous avons [id] Name. Le nœud racine 0 est fictif.

                       [0] ROOT
                          / \
              [1] Noeud 1 [3] Noeud 2
              / \ \
    [2] Noeud 1.1 [6] Noeud 1.2 [5] Noeud 2.1
          /
 [4] Noeud 1.1.1

Quelle approche minimaliste utiliseriez-vous pour afficher ce HTML (ou texte, d'ailleurs) comme un arbre correctement ordonné et correctement indenté?

Supposons en outre que vous ayez seulement des structures de données de base (tableaux et hashmaps), pas d'objets fantaisie avec des références parents / enfants, pas d'ORM, pas de framework, juste vos deux mains. La table est représentée sous la forme d'un jeu de résultats, auquel il est possible d'accéder de manière aléatoire.

Le pseudo-code ou l’anglais pur est correct, c’est purement une question de conception.

Question bonus: Y a-t-il une façon fondamentalement meilleure de stocker une structure arborescente comme celle-ci dans un SGBDR?


EDITS ET ADDITIONS

Pour répondre à un commentateur (Mark Bessey's) question: Un nœud racine n'est pas nécessaire, car il ne sera jamais affiché de toute façon. ParentId = 0 est la convention pour exprimer "ceux-ci sont de premier niveau". La colonne Ordre définit comment les nœuds avec le même parent vont être triés.

Le «jeu de résultats» dont j'ai parlé peut être décrit comme un tableau de hashmaps (pour rester dans cette terminologie). Car mon exemple était censé être déjà là. Certaines réponses vont le mile supplémentaire et le construire d'abord, mais c'est d'accord.

L'arbre peut être arbitrairement profond. Chaque noeud peut avoir N enfants. Je n'avais pas exactement un arbre "millions d'entrées" en tête.

Ne confondez pas mon choix de nom de noeud ('Node 1.1.1') avec quelque chose sur lequel compter. Les nœuds pourraient aussi bien s'appeler 'Frank' ou 'Bob', aucune structure de nommage n'est implicite, c'était simplement pour le rendre lisible.

J'ai posté ma propre solution afin que vous puissiez la mettre en pièces.


466
2017-10-10 16:47


origine


Réponses:


Maintenant que MySQL 8.0 est proche de la version, toutes les bases de données SQL populaires prendront en charge les requêtes récursives en syntaxe standard.

WITH RECURSIVE MyTree AS (
    SELECT * FROM MyTable WHERE ParentId IS NULL
    UNION ALL
    SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;

J'ai testé des requêtes récursives dans MySQL 8.0 dans ma présentation Redirection de requête récursive en 2017.

Voici ma réponse originale de 2008:


Il existe plusieurs manières de stocker des données structurées en arborescence dans une base de données relationnelle. Ce que vous montrez dans votre exemple utilise deux méthodes:

  • Liste d'adjacence (la colonne "parent") et
  • Enumération de chemin (les numéros en pointillés dans la colonne de votre nom).

Une autre solution s'appelle Ensembles imbriqués, et il peut être stocké dans la même table aussi. Lis "Arbres et hiérarchies en SQL pour Smarties"par Joe Celko pour beaucoup plus d'informations sur ces modèles.

Je préfère généralement un design appelé Table de fermeture (aka "Relation d'Adjacence") pour stocker des données arborescentes. Il nécessite une autre table, mais l'interrogation des arbres est assez facile.

Je couvre la table de clôture dans ma présentation Modèles pour les données hiérarchiques avec SQL et PHP et dans mon livre Antipatterns SQL: éviter les pièges de la programmation de base de données.

CREATE TABLE ClosureTable (
  ancestor_id   INT NOT NULL REFERENCES FlatTable(id),
  descendant_id INT NOT NULL REFERENCES FlatTable(id),
  PRIMARY KEY (ancestor_id, descendant_id)
);

Stocker tous les chemins dans la table de fermeture, où il existe une ascendance directe d'un nœud à l'autre. Inclure une ligne pour chaque nœud pour se référencer lui-même. Par exemple, en utilisant l'ensemble de données que vous avez montré dans votre question:

INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
  (1,1), (1,2), (1,4), (1,6),
  (2,2), (2,4),
  (3,3), (3,5),
  (4,4),
  (5,5),
  (6,6);

Vous pouvez maintenant obtenir un arbre commençant au noeud 1 comme ceci:

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;

La sortie (dans le client MySQL) ressemble à ceci:

+----+
| id |
+----+
|  1 | 
|  2 | 
|  4 | 
|  6 | 
+----+

En d'autres termes, les nœuds 3 et 5 sont exclus, car ils font partie d'une hiérarchie distincte, et non du nœud 1.


Re: commentaire d'e-satis sur les enfants immédiats (ou parent immédiat). Vous pouvez ajouter un "path_length"colonne à la ClosureTable pour rendre plus facile d'interroger spécifiquement pour un enfant ou un parent immédiat (ou toute autre distance).

INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
  (1,1,0), (1,2,1), (1,4,2), (1,6,1),
  (2,2,0), (2,4,1),
  (3,3,0), (3,5,1),
  (4,4,0),
  (5,5,0),
  (6,6,0);

Vous pouvez ensuite ajouter un terme dans votre recherche pour interroger les enfants immédiats d'un noeud donné. Ce sont des descendants dont path_length est 1.

SELECT f.* 
FROM FlatTable f 
  JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
  AND path_length = 1;

+----+
| id |
+----+
|  2 | 
|  6 | 
+----+

Re commentaire de @ashraf: "Que diriez-vous de trier l'arbre entier [par nom]?"

Voici un exemple de requête pour renvoyer tous les nœuds qui sont des descendants du nœud 1, joignez-les à la FlatTable qui contient d'autres attributs de nœud tels que name, et trier par le nom.

SELECT f.name
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;

Commentaire de @Nate:

SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f 
JOIN ClosureTable a ON (f.id = a.descendant_id) 
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id) 
WHERE a.ancestor_id = 1 
GROUP BY a.descendant_id 
ORDER BY f.name

+------------+-------------+
| name       | breadcrumbs |
+------------+-------------+
| Node 1     | 1           |
| Node 1.1   | 1,2         |
| Node 1.1.1 | 1,2,4       |
| Node 1.2   | 1,6         |
+------------+-------------+

Un utilisateur a suggéré une modification aujourd'hui. Les modérateurs SO ont approuvé l'édition, mais je l'inverse.

L'édition a suggéré que le ORDER BY dans la dernière requête ci-dessus devrait être ORDER BY b.path_length, f.name, probablement pour s'assurer que la commande correspond à la hiérarchie. Mais cela ne marche pas, car il commanderait "Node 1.1.1" après "Node 1.2".

Si vous souhaitez que l'ordre corresponde de manière judicieuse à la hiérarchie, cela est possible, mais pas simplement en fonction de la longueur du chemin. Par exemple, voir ma réponse à Base de données hiérarchique MySQL Closure Table - Comment extraire les informations dans le bon ordre.


406
2017-10-10 17:58



Si vous utilisez des ensembles imbriqués (parfois appelés Traversal d'arborescence de précommande modifié), vous pouvez extraire l'arborescence complète ou toute sous-arborescence de celle-ci dans un ordre d'arborescence avec une seule requête, au prix d'une insertion plus coûteuse. gérer les colonnes qui décrivent un chemin dans l'ordre de l'arborescence.

Pour Django-mptt, J'ai utilisé une structure comme celle-ci:

id parent_id tree_id niveau lft droit
- --------- ------- ----- --- ----
 1 null 1 0 1 14
 2 1 1 1 2 7
 3 2 1 2 3 4
 4 2 1 2 5 6
 5 1 1 1 8 13
 6 5 1 2 9 10
 7 5 1 2 11 12

Qui décrit un arbre qui ressemble à ceci (avec id représentant chaque article):

 1
 + - 2
 | + - 3
 | + - 4
 |
 + - 5
     + - 6
     + - 7

Ou, en tant que diagramme d'ensemble emboîté qui rend plus évident comment le lft et rght les valeurs fonctionnent:

__________________________________________________________________________
| Racine 1 |
| ________________________________ ________________________________ |
| | Enfant 1.1 | | Enfant 1.2 | |
| | ___________ ___________ | | ___________ ___________ | |
| | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | |
1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14
| | ________________________________ | | ________________________________ | |
| __________________________________________________________________________ |

Comme vous pouvez le voir, pour obtenir l'intégralité du sous-arbre pour un nœud donné, dans l'ordre de l'arborescence, il vous suffit de sélectionner toutes les lignes qui ont lft et rght valeurs entre ses lft et rght valeurs. Il est également simple de récupérer l'arbre des ancêtres pour un nœud donné.

le level colonne est un peu de dénormalisation pour plus de commodité que tout et la tree_id colonne vous permet de redémarrer le lft et rght numérotation pour chaque noeud de niveau supérieur, ce qui réduit le nombre de colonnes affectées par les insertions, les déplacements et les suppressions, lft et rght les colonnes doivent être ajustées en conséquence lorsque ces opérations ont lieu afin de créer ou de fermer des espaces. j'en ai fait notes de développement au moment où j'essayais de comprendre les requêtes requises pour chaque opération.

En termes de travailler réellement avec ces données pour afficher un arbre, j'ai créé un tree_item_iterator fonction utilitaire qui, pour chaque nœud, devrait vous donner suffisamment d'informations pour générer le type d'affichage que vous souhaitez.

Plus d'infos sur MPTT:


53
2017-10-11 12:31



A partir d'Oracle 9i, vous pouvez utiliser CONNECT BY.

SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)

À partir de SQL Server 2005, vous pouvez utiliser une expression de table commune récursive (CTE).

WITH [NodeList] (
  [Id]
  , [ParentId]
  , [Level]
  , [Order]
) AS (
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , 0 AS [Level]
    , CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
  WHERE [Node].[ParentId] = 0
  UNION ALL
  SELECT [Node].[Id]
    , [Node].[ParentId]
    , [NodeList].[Level] + 1 AS [Level]
    , [NodeList].[Order] + '|'
      + CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
  FROM [Node]
    INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
  INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]

Les deux produiront les résultats suivants.

prénom
"Node 1"
'Noeud 1.1'
'Noeud 1.1.1'
'Node 1.2'
'Nœud 2'
'Noeud 2.1'

18
2017-10-10 20:06



C'est une question assez ancienne, mais comme il a beaucoup de points de vue, je pense que cela vaut la peine de présenter une solution alternative, et à mon avis très élégante.

Pour lire une arborescence, vous pouvez utiliser Expressions de table communes récursives (CTEs). Il donne la possibilité d'aller chercher la structure arborescente entière à la fois, d'avoir des informations sur le niveau du nœud, son nœud parent et son ordre dans les enfants du nœud parent.

Laissez-moi vous montrer comment cela fonctionnera dans PostgreSQL 9.1.

  1. Créer une structure

    CREATE TABLE tree (
        id int  NOT NULL,
        name varchar(32)  NOT NULL,
        parent_id int  NULL,
        node_order int  NOT NULL,
        CONSTRAINT tree_pk PRIMARY KEY (id),
        CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) 
          REFERENCES tree (id) NOT DEFERRABLE
    );
    
    
    insert into tree values
      (0, 'ROOT', NULL, 0),
      (1, 'Node 1', 0, 10),
      (2, 'Node 1.1', 1, 10),
      (3, 'Node 2', 0, 20),
      (4, 'Node 1.1.1', 2, 10),
      (5, 'Node 2.1', 3, 10),
      (6, 'Node 1.2', 1, 20);
    
  2. Ecrire une requête

    WITH RECURSIVE 
    tree_search (id, name, level, parent_id, node_order) AS (
      SELECT 
        id, 
        name,
        0,
        parent_id, 
        1 
      FROM tree
      WHERE parent_id is NULL
    
      UNION ALL 
      SELECT 
        t.id, 
        t.name,
        ts.level + 1, 
        ts.id, 
        t.node_order 
      FROM tree t, tree_search ts 
      WHERE t.parent_id = ts.id 
    ) 
    SELECT * FROM tree_search 
    WHERE level > 0 
    ORDER BY level, parent_id, node_order;
    

    Voici les résultats:

     id |    name    | level | parent_id | node_order 
    ----+------------+-------+-----------+------------
      1 | Node 1     |     1 |         0 |         10
      3 | Node 2     |     1 |         0 |         20
      2 | Node 1.1   |     2 |         1 |         10
      6 | Node 1.2   |     2 |         1 |         20
      5 | Node 2.1   |     2 |         3 |         10
      4 | Node 1.1.1 |     3 |         2 |         10
    (6 rows)
    

    Les nœuds d'arbre sont classés par niveau de profondeur. Dans le résultat final, nous les présenterions dans les lignes suivantes.

    Pour chaque niveau, ils sont classés par parent_id et node_order dans le parent. Cela nous indique comment les présenter dans le noeud de lien de sortie au parent dans cet ordre.

    Avoir une telle structure, il ne serait pas difficile de faire une très belle présentation en HTML.

    Les CTE récursifs sont disponibles dans PostgreSQL, IBM DB2, MS SQL Server et Oracle.

    Si vous souhaitez en savoir plus sur les requêtes SQL récursives, vous pouvez consulter la documentation de votre SGBD préféré ou lire mes deux articles traitant de ce sujet:


16
2018-03-13 11:19



La réponse de Bill est plutôt bonne, cette réponse ajoute des choses qui me font souhaiter que les réponses filetées soient prises en charge.

En tout cas je voulais supporter la structure arborescente et la propriété Order. J'ai inclus une seule propriété dans chaque nœud appelé leftSibling ça fait la même chose Order est destiné à faire dans la question d'origine (maintenir l'ordre de gauche à droite).

mysql> desc nœuds;
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
| Champ | Type | Nul | Clé | Par défaut | Extra |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
| id | int (11) | NO | PRI | NULL | auto_increment |
| nom | varchar (255) | OUI | | NULL | |
| leftSibling | int (11) | NO | | 0 | |
+ ------------- + -------------- + ------ + ----- + ------- - + ---------------- +
3 lignes dans l'ensemble (0.00 sec)

mysql> desc adjacencies;
+ -------- + + --------- + ------ + ----- + --------- + --- ------------- +
| Champ | Type | Nul | Clé | Par défaut | Extra |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
| relationId | int (11) | NO | PRI | NULL | auto_increment |
| parent | int (11) | NO | | NULL | |
| enfant | int (11) | NON | | NULL | |
| pathLen | int (11) | NON | | NULL | |
+ ------------ + --------- + ------ + ----- + --------- + --- ------------- +
4 lignes dans l'ensemble (0.00 sec)

Plus de détails et de code SQL sur mon blog.

Merci Bill votre réponse a été utile pour commencer!


9
2017-12-22 04:31



Bien vu le choix, j'utiliserais des objets. Je créerais un objet pour chaque enregistrement où chaque objet a un children collectez et stockez-les tous dans un tableau assoc (/ hashtable) où l'ID est la clé. Et blitz à travers la collection une fois, en ajoutant les enfants aux champs d'enfants pertinents. Simple.

Mais parce que vous ne vous amusez pas en restreignant l'utilisation d'une bonne POO, je ferais probablement une itération en fonction de:

function PrintLine(int pID, int level)
    foreach record where ParentID == pID
        print level*tabs + record-data
        PrintLine(record.ID, level + 1)

PrintLine(0, 0)

Edit: c'est similaire à quelques autres entrées, mais je pense que c'est un peu plus propre. Une chose que je vais ajouter: ceci est extrêmement SQL-intensif. Ses méchant. Si vous avez le choix, passez par la voie de la POO.


7
2017-10-10 17:36



Cela a été écrit rapidement, et n'est ni joli ni efficace (en plus il autoboxes beaucoup, la conversion entre int et Integer c'est agaçant!), mais ça marche.

Cela brise probablement les règles puisque je crée mes propres objets mais bon je fais ça comme une diversion du vrai travail :)

Cela suppose également que resultSet / table est complètement lu dans une sorte de structure avant de commencer à construire des nœuds, ce qui ne serait pas la meilleure solution si vous avez des centaines de milliers de lignes.

public class Node {

    private Node parent = null;

    private List<Node> children;

    private String name;

    private int id = -1;

    public Node(Node parent, int id, String name) {
        this.parent = parent;
        this.children = new ArrayList<Node>();
        this.name = name;
        this.id = id;
    }

    public int getId() {
        return this.id;
    }

    public String getName() {
        return this.name;
    }

    public void addChild(Node child) {
        children.add(child);
    }

    public List<Node> getChildren() {
        return children;
    }

    public boolean isRoot() {
        return (this.parent == null);
    }

    @Override
    public String toString() {
        return "id=" + id + ", name=" + name + ", parent=" + parent;
    }
}

public class NodeBuilder {

    public static Node build(List<Map<String, String>> input) {

        // maps id of a node to it's Node object
        Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();

        // maps id of a node to the id of it's parent
        Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();

        // create special 'root' Node with id=0
        Node root = new Node(null, 0, "root");
        nodeMap.put(root.getId(), root);

        // iterate thru the input
        for (Map<String, String> map : input) {

            // expect each Map to have keys for "id", "name", "parent" ... a
            // real implementation would read from a SQL object or resultset
            int id = Integer.parseInt(map.get("id"));
            String name = map.get("name");
            int parent = Integer.parseInt(map.get("parent"));

            Node node = new Node(null, id, name);
            nodeMap.put(id, node);

            childParentMap.put(id, parent);
        }

        // now that each Node is created, setup the child-parent relationships
        for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
            int nodeId = entry.getKey();
            int parentId = entry.getValue();

            Node child = nodeMap.get(nodeId);
            Node parent = nodeMap.get(parentId);
            parent.addChild(child);
        }

        return root;
    }
}

public class NodePrinter {

    static void printRootNode(Node root) {
        printNodes(root, 0);
    }

    static void printNodes(Node node, int indentLevel) {

        printNode(node, indentLevel);
        // recurse
        for (Node child : node.getChildren()) {
            printNodes(child, indentLevel + 1);
        }
    }

    static void printNode(Node node, int indentLevel) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < indentLevel; i++) {
            sb.append("\t");
        }
        sb.append(node);

        System.out.println(sb.toString());
    }

    public static void main(String[] args) {

        // setup dummy data
        List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
        resultSet.add(newMap("1", "Node 1", "0"));
        resultSet.add(newMap("2", "Node 1.1", "1"));
        resultSet.add(newMap("3", "Node 2", "0"));
        resultSet.add(newMap("4", "Node 1.1.1", "2"));
        resultSet.add(newMap("5", "Node 2.1", "3"));
        resultSet.add(newMap("6", "Node 1.2", "1"));

        Node root = NodeBuilder.build(resultSet);
        printRootNode(root);

    }

    //convenience method for creating our dummy data
    private static Map<String, String> newMap(String id, String name, String parentId) {
        Map<String, String> row = new HashMap<String, String>();
        row.put("id", id);
        row.put("name", name);
        row.put("parent", parentId);
        return row;
    }
}

5
2017-10-10 18:25



En supposant que vous savez que les éléments racine sont nuls, voici le pseudo-code à afficher dans le texte:

function PrintLevel (int curr, int level)
    //print the indents
    for (i=1; i<=level; i++)
        print a tab
    print curr \n;
    for each child in the table with a parent of curr
        PrintLevel (child, level+1)


for each elementID where the parentid is zero
    PrintLevel(elementID, 0)

3
2017-10-10 16:59



Vous pouvez émuler n'importe quelle autre structure de données avec un hashmap, ce n'est donc pas une limitation terrible. En scannant du haut vers le bas, vous créez un hashmap pour chaque ligne de la base de données, avec une entrée pour chaque colonne. Ajoutez chacun de ces hashmaps à un hashmap "maître", indexé sur l'ID. Si un nœud a un "parent" que vous n'avez pas encore vu, créez une entrée pour lui dans le hashmap principal, et remplissez-le quand vous voyez le nœud réel.

Pour l'imprimer, effectuez un simple passage en profondeur des données, en suivant le niveau de retrait en cours de route. Vous pouvez faciliter cela en conservant une entrée "enfants" pour chaque ligne et en la remplissant au fur et à mesure que vous analysez les données.

Quant à savoir s'il existe un "meilleur" moyen de stocker un arbre dans une base de données, cela dépend de la façon dont vous allez utiliser les données. J'ai vu des systèmes dont la profondeur maximale connue utilisait une table différente pour chaque niveau de la hiérarchie. Cela fait beaucoup de sens si les niveaux dans l'arbre ne sont pas tout à fait équivalents après tout (les catégories de haut niveau étant différentes des feuilles).


3
2017-10-10 17:24



Il existe de très bonnes solutions qui exploitent la représentation btree interne des indices sql. Ceci est basé sur de grandes recherches effectuées vers 1998.

Voici un exemple de table (dans mysql).

CREATE TABLE `node` (
  `id` int(10) unsigned NOT NULL AUTO_INCREMENT,
  `name` varchar(255) NOT NULL,
  `tw` int(10) unsigned NOT NULL,
  `pa` int(10) unsigned DEFAULT NULL,
  `sz` int(10) unsigned DEFAULT NULL,
  `nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
  PRIMARY KEY (`id`),
  KEY `node_tw_index` (`tw`),
  KEY `node_pa_index` (`pa`),
  KEY `node_nc_index` (`nc`),
  CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)

Les seuls champs nécessaires pour la représentation de l'arbre sont:

  • tw: L'index de pré-commande DFS de gauche à droite, où root = 1.
  • pa: La référence (en utilisant tw) au nœud parent, root a la valeur null.
  • sz: la taille de la branche du noeud, y compris elle-même.
  • nc: est utilisé comme sucre syntaxique. il est tw + nc et représente le tw du "prochain enfant" du nœud.

Voici un exemple de population de 24 noeuds, classés par tw:

+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|   2 | A       |  2 |    1 |   14 |   16 |
|   3 | AA      |  3 |    2 |    1 |    4 |
|   4 | AB      |  4 |    2 |    7 |   11 |
|   5 | ABA     |  5 |    4 |    1 |    6 |
|   6 | ABB     |  6 |    4 |    3 |    9 |
|   7 | ABBA    |  7 |    6 |    1 |    8 |
|   8 | ABBB    |  8 |    6 |    1 |    9 |
|   9 | ABC     |  9 |    4 |    2 |   11 |
|  10 | ABCD    | 10 |    9 |    1 |   11 |
|  11 | AC      | 11 |    2 |    4 |   15 |
|  12 | ACA     | 12 |   11 |    2 |   14 |
|  13 | ACAA    | 13 |   12 |    1 |   14 |
|  14 | ACB     | 14 |   11 |    1 |   15 |
|  15 | AD      | 15 |    2 |    1 |   16 |
|  16 | B       | 16 |    1 |    1 |   17 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
|  18 | D       | 23 |    1 |    1 |   24 |
|  19 | E       | 24 |    1 |    1 |   25 |
+-----+---------+----+------+------+------+

Chaque résultat d'arbre peut être fait de manière non récursive. Par exemple, pour obtenir une liste des ancêtres de node à tw = '22 '

Les ancêtres

select anc.* from node me,node anc 
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw 
order by anc.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|   1 | Root    |  1 | NULL |   24 |   25 |
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Les frères et sœurs et les enfants sont insignifiants.

Descendance

Par exemple, l'ensemble (branche) des nœuds qui sont enracinés à tw = 17.

select des.* from node me,node des 
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw 
order by des.tw;
+-----+---------+----+------+------+------+
| id  | name    | tw | pa   | sz   | nc   |
+-----+---------+----+------+------+------+
|  17 | C       | 17 |    1 |    6 |   23 |
| 359 | C0      | 18 |   17 |    5 |   23 |
| 360 | C1      | 19 |   18 |    4 |   23 |
| 361 | C2(res) | 20 |   19 |    3 |   23 |
| 362 | C3      | 21 |   20 |    2 |   23 |
| 363 | C4      | 22 |   21 |    1 |   23 |
+-----+---------+----+------+------+------+

Notes complémentaires

Cette méthodologie est extrêmement utile lorsque le nombre de lectures est beaucoup plus important que le nombre d'insertions ou de mises à jour.

Étant donné que l'insertion, le déplacement ou la mise à jour d'un nœud dans l'arborescence nécessite le réglage de l'arborescence, il est nécessaire de verrouiller la table avant de commencer l'action.

Le coût d'insertion / suppression est élevé car les valeurs d'index tw et de sz (taille de branche) devront être mises à jour sur tous les nœuds après le point d'insertion et pour tous les ancêtres respectivement.

Le déplacement de branche implique de déplacer la valeur tw de la branche hors de portée, il est donc également nécessaire de désactiver les contraintes de clé étrangère lors du déplacement d'une branche. Il y a essentiellement quatre requêtes requises pour déplacer une branche:

  • Déplacez la branche hors de portée.
  • Fermez l'écart qu'il a laissé. (l'arbre restant est maintenant normalisé).
  • Ouvrez l'écart là où il ira.
  • Déplacez la branche dans sa nouvelle position.

Ajuster les requêtes d'arbre

L'ouverture / fermeture des espaces dans l'arbre est une sous-fonction importante utilisée par les méthodes create / update / delete, donc je l'inclue ici.

Nous avons besoin de deux paramètres - un drapeau indiquant si nous réduisons ou sommes en train de migrer, et l'index tw du nœud. Donc, par exemple tw = 18 (qui a une taille de branche de 5). Supposons que nous réduisions (supprimant tw) - cela signifie que nous utilisons '-' au lieu de '+' dans les mises à jour de l'exemple suivant.

Nous utilisons d'abord une fonction ancêtre (légèrement modifiée) pour mettre à jour la valeur sz.

update node me, node anc set anc.sz = anc.sz - me.sz from 
node me, node anc where me.tw=18 
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));

Ensuite, nous devons ajuster le tw pour ceux dont le tw est supérieur à la branche à supprimer.

update node me, node anc set anc.tw = anc.tw - me.sz from 
node me, node anc where me.tw=18 and anc.tw >= me.tw;

Ensuite, nous devons ajuster le parent pour ceux dont le pa est supérieur à la branche à supprimer.

update node me, node anc set anc.pa = anc.pa - me.sz from 
node me, node anc where me.tw=18 and anc.pa >= me.tw;

3
2018-03-14 08:43