Quel est le moyen le plus efficace / élégant d’analyser une table plate dans un arbre?
https://stackoverflow.com/questions/192220
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Supposons que vous ayez une table plate qui stocke une hiérarchie d’arborescence:
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] Nom . Le nœud racine 0 est fictif.
[0] ROOT
/ \
[1] Node 1 [3] Node 2
/ \ \
[2] Node 1.1 [6] Node 1.2 [5] Node 2.1
/
[4] Node 1.1.1
Quelle approche minimaliste utiliseriez-vous pour générer cela en HTML (ou en texte, d'ailleurs) sous forme d'arborescence correctement ordonnée et correctement mise en retrait?
Supposons en outre que vous n’avez que des structures de données de base (tableaux et hashmaps), aucun objet de fantaisie avec références parent / enfant, aucun ORM, aucun cadre, seulement vos deux mains. La table est représentée sous la forme d'un ensemble de résultats auquel il est possible d'accéder de manière aléatoire.
Un pseudo-code ou un anglais simplifié convient, c'est une question purement conceptuelle.
Question bonus: existe-t-il un moyen fondamentalement meilleur de stocker une telle arborescence dans un SGBDR?
MODIFICATIONS ET AJOUTS
Pour répondre à la question d'un commentateur ( Mark Bessey ): un nœud racine n'est pas nécessaire, car ne sera jamais affiché de toute façon. ParentId = 0 est la convention pour exprimer "ce sont des niveaux supérieurs". La colonne Order définit le mode de tri des nœuds avec le même parent.
Le " jeu de résultats " J'ai parlé de peut être décrit comme un tableau de hashmaps (pour rester dans cette terminologie). Pour mon exemple était censé être déjà là. Certaines réponses font un effort supplémentaire et le construisent d’abord, mais c’est correct.
L'arbre peut être arbitrairement profond. Chaque nœud peut avoir N enfants. Je n'avais pas exactement un " millions d'entrées " arbre à l'esprit, cependant.
Ne confondez pas mon choix de dénomination de nœud ('Node 1.1.1') avec quelque chose sur lequel compter. Les nœuds peuvent tout aussi bien s'appeler 'Frank' ou 'Bob', aucune structure de nommage n'est impliquée, c'était simplement pour le rendre lisible.
J'ai posté ma propre solution pour que vous puissiez la mettre en pièces.
La solution
Maintenant que MySQL 8.0 est sur le point de sortir, toutes les bases de données SQL courantes prennent 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é les requêtes récursives dans MySQL 8.0 dans ma présentation Analyse des requêtes récursive dans 2017.
Voici ma réponse originale de 2008:
Il existe plusieurs façons 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 des adresses adjacentes (la colonne "parent") et
- Énumération du chemin (les nombres en pointillés dans la colonne Nom).
Une autre solution s'appelle Ensembles imbriqués . Elle peut également être stockée dans le même tableau. Lisez les Arbres et hiérarchies dans SQL pour Smarties " par Joe Celko pour beaucoup plus d'informations sur ces dessins.
Je préfère généralement un modèle appelé table de fermeture (aka "relation d'adjacence") pour le stockage de données structurées en arborescence. Cela nécessite une autre table, mais interroger les 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)
);
Stockez tous les chemins dans la table de fermeture, où il existe une ascendance directe d'un noeud à un autre. Inclure une ligne pour chaque nœud pour se référencer. Par exemple, en utilisant l'ensemble de données que vous avez indiqué 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 (sur le client MySQL) a l'aspect suivant:
+----+
| 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 ne descendent pas du nœud 1.
Re: commentaire d’e-satis concernant les enfants immédiats (ou le parent immédiat). Vous pouvez ajouter un " longueur de chemin " colonne à ClosureTable pour faciliter l’interrogation spécifique d’un enfant ou d’un parent immédiat (ou de 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 nœud donné. Ce sont des descendants dont path_length est égal à 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 |
+----+
Commentaire de @ashraf: "Pourquoi ne pas trier l’arbre entier [par son nom]?"
Voici un exemple de requête visant à renvoyer tous les nœuds descendants du nœud 1, à les associer au FlatTable contenant d'autres attributs de nœud tels que nom et à les trier par 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 donc approuvé le montage, mais je l’inverse.
La modification a suggéré que ORDER BY dans la dernière requête ci-dessus soit ORDER BY b.path_length, f.name , probablement pour s'assurer que l'ordre correspond à la hiérarchie. Mais cela ne fonctionne pas, car cela commanderait "Node 1.1.1". après "Node 1.2".
Si vous souhaitez que l'ordre corresponde à la hiérarchie de manière judicieuse, c'est possible, mais pas simplement en ordonnant selon la longueur du chemin d'accès. Par exemple, voir ma réponse à Base de données hiérarchique MySQL Closure Table - Comment extraire les informations dans le bon ordre .
Autres conseils
Si vous utilisez des ensembles imbriqués (parfois appelés traversée de l’arborescence de la pré-commande modifiée), vous pouvez extraire l’arborescence entière ou tout sous-arbre de celle-ci dans l’ordre de l’arborescence avec une seule requête, au prix d’insertions vous devez gérer les colonnes décrivant un chemin dans l’ordre dans l’arborescence.
Pour django-mptt , j'ai utilisé une structure comme celle-ci:
id parent_id tree_id level lft rght -- --------- ------- ----- --- ---- 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 une arborescence qui ressemble à ceci (avec id représentant chaque élément):
1
+-- 2
| +-- 3
| +-- 4
|
+-- 5
+-- 6
+-- 7
Ou, en tant que diagramme d'ensemble imbriqué, qui rend plus évident le fonctionnement des valeurs lft et juste :
__________________________________________________________________________ | Root 1 | | ________________________________ ________________________________ | | | Child 1.1 | | Child 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 le sous-arbre entier pour un nœud donné, vous devez simplement sélectionner toutes les lignes qui ont des valeurs lft et rght entre ses valeurs lft et droit . Il est également simple de récupérer l’arbre des ancêtres d’un nœud donné.
La colonne niveau est un peu de dénormalisation pour plus de commodité et la colonne tree_id vous permet de redémarrer les codes lft et rght pour chaque nœud de niveau supérieur, ce qui réduit le nombre de colonnes affectées par les insertions, les déplacements et les suppressions, car les colonnes lft et rght doivent: être ajustés en conséquence lorsque ces opérations ont lieu afin de créer ou de combler des lacunes. J'ai créé des notes de développement à l'époque où j'étais J'essaie de comprendre les requêtes nécessaires à chaque opération.
En ce qui concerne l'utilisation de ces données pour afficher une arborescence, j'ai créé un tree_item_iterator fonction utilitaire qui, pour chaque nœud, devrait vous fournir suffisamment d’informations pour générer le type d’affichage souhaité.
Plus d'infos sur MPTT:
C'est une question assez ancienne, mais comme elle suscite de nombreux points de vue, je pense qu'il vaut la peine de présenter une solution de rechange, et à mon avis très élégante, une solution.
Pour lire une arborescence, vous pouvez utiliser des expressions de table communes récursives (CTE). Cela donne la possibilité d’extraire l’ensemble de l’arborescence à la fois, d’avoir les informations sur le niveau du nœud, son nœud parent et son ordre au sein des enfants du nœud parent.
Laissez-moi vous montrer comment cela fonctionnerait dans PostgreSQL 9.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); -
Écrire 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ésenterons 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.
Avec 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:
À 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.
Name 'Node 1' ' Node 1.1' ' Node 1.1.1' ' Node 1.2' 'Node 2' ' Node 2.1'
La réponse de Bill est plutôt bonne, cette réponse ajoute des éléments qui me font souhaiter que les réponses threadées à SO soient prises en charge.
Quoi qu'il en soit, je souhaitais prendre en charge l’arborescence et la propriété Order. J'ai inclus dans chaque nœud une propriété unique appelée leftSibling qui fait la même chose que Order est censé faire dans la question d'origine (maintien de l'ordre de gauche à droite).
mysql> desc nodes ; +-------------+--------------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------------+--------------+------+-----+---------+----------------+ | id | int(11) | NO | PRI | NULL | auto_increment | | name | varchar(255) | YES | | NULL | | | leftSibling | int(11) | NO | | 0 | | +-------------+--------------+------+-----+---------+----------------+ 3 rows in set (0.00 sec) mysql> desc adjacencies; +------------+---------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +------------+---------+------+-----+---------+----------------+ | relationId | int(11) | NO | PRI | NULL | auto_increment | | parent | int(11) | NO | | NULL | | | child | int(11) | NO | | NULL | | | pathLen | int(11) | NO | | NULL | | +------------+---------+------+-----+---------+----------------+ 4 rows in set (0.00 sec)
Plus de détails et du code SQL sur mon blog .
Merci Bill, votre réponse a été utile pour commencer!
Bien, si le choix était fait, j'utiliserais des objets. Je créerais un objet pour chaque enregistrement où chaque objet aurait une collection children et les stockerais tous dans un tableau assoc (/ hashtable) où l'id est la clé. Et blitzez une fois dans la collection en ajoutant les enfants aux champs correspondants. Simple.
Mais parce que vous n'êtes pas amusant en limitant l'utilisation d'une bonne POO, je le ferais probablement sur la base 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)
Modifier: cela ressemble à quelques autres entrées, mais je pense que c'est un peu plus propre. J'ajouterai une chose: c'est extrêmement gourmand en SQL. C'est méchant . Si vous avez le choix, passez à la POO.
Ceci a été écrit rapidement et n’est ni joli ni efficace (en plus, il utilise beaucoup de boîtes automatiques, convertir entre int et Integer est ennuyant!), mais cela fonctionne.
Cela brise probablement les règles puisque je crée mes propres objets, mais bon, je le fais comme une diversion du travail réel:)
Cela suppose également que la table resultSet / est complètement lue dans une sorte de structure avant de commencer à créer 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;
}
}
En supposant que vous sachiez que les éléments racines sont à zéro, voici le pseudocode à afficher en 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)
Vous pouvez émuler n'importe quelle autre structure de données avec une table de hachage, ce qui ne constitue pas une limitation terrible. En analysant de haut en bas, vous créez une table de hachage pour chaque ligne de la base de données, avec une entrée pour chaque colonne. Ajoutez chacun de ces hashmaps à un " maître " hashmap, saisi sur l'id. Si un nœud a un " parent " que vous n'avez pas encore vu, créez une entrée pour ce paramètre dans la table de hachage principale et complétez-la lorsque vous voyez le nœud réel.
Pour l’imprimer, effectuez un simple passage en profondeur dans les données, en gardant une trace du niveau de retrait le long du chemin. Vous pouvez rendre cela plus facile en conservant un " enfants " entrée 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 manière 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 a beaucoup de sens si les niveaux dans l’arbre ne sont pas tout à fait équivalents après tout (les catégories de niveau supérieur étant différentes des feuilles).
Il existe de très bonnes solutions qui exploitent la représentation btree interne des index SQL. C’est basé sur des recherches remarquables faites 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 à la représentation sous forme d'arborescence sont les suivants:
- tw: index de précommande DFS de gauche à droite, où root = 1.
- pa: référence (en utilisant tw) au noeud parent, la racine a la valeur null.
- sz: taille de la branche du noeud, y compris lui-même.
- nc: est utilisé comme sucre syntaxique. il s'agit de tw + nc et représente le tw du "prochain enfant" du noeud.
Voici un exemple de population de 24 nœuds, ordonnée 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'arborescence peut être effectué de manière non récursive. Par exemple, pour obtenir une liste des ancêtres du noeud à tw = '22 '
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 triviaux - il suffit d'utiliser l'ordre des champs pa par tw.
Descendants
Par exemple, l'ensemble (la branche) des nœuds 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 |
+-----+---------+----+------+------+------+
Remarques supplémentaires
Cette méthodologie est extrêmement utile dans les cas où le nombre de lectures est beaucoup plus important que les insertions ou les mises à jour.
Etant donné que l'insertion, le déplacement ou la mise à jour d'un nœud dans l'arborescence nécessite l'ajustement 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 de l’index tw et de la taille de branche sz 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 d'une branche implique le déplacement de la valeur tw de la branche en dehors de sa plage. Il est donc également nécessaire de désactiver les contraintes de clé étrangère lors du déplacement d'une branche. Il faut essentiellement quatre requêtes pour déplacer une branche:
- Déplacez la branche hors de portée.
- Fermez l’espace laissé. (l’arbre restant est maintenant normalisé).
- Ouvrez l'espace où il ira.
- Déplacez la branche dans sa nouvelle position.
Ajuster les requêtes d'arborescence
L'ouverture / la fermeture des espaces dans l'arborescence est une sous-fonction importante utilisée par les méthodes create / update / delete, je l'inclue donc ici.
Nous avons besoin de deux paramètres: un drapeau indiquant si nous sommes en train de réduire ou de réduire la taille, et l'index tw du nœud. Ainsi, par exemple tw = 18 (qui a une taille de branche de 5). Supposons que nous réduisions (supprimons 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 tw de 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;
Si des cartes de hachage ou des tableaux imbriqués peuvent être créés, je peux simplement parcourir la table depuis le début et ajouter chaque élément au tableau imbriqué. Je dois tracer chaque ligne jusqu'au nœud racine afin de savoir à quel niveau du tableau imbriqué insérer. Je peux utiliser la mémoisation pour ne pas avoir à chercher le même parent encore et encore.
Éditer: Je lirais d’abord le tableau entier dans un tableau, afin qu’il n’interroge pas le DB à plusieurs reprises. Bien sûr, cela ne sera pas pratique si votre table est très grande.
Une fois la structure construite, je dois d'abord la traverser en profondeur et imprimer le code HTML.
Il n’existe pas de meilleur moyen fondamental de stocker ces informations à l’aide d’un seul tableau (j’aurais peut-être tort;), et j'aimerais bien trouver une meilleure solution). Cependant, si vous créez un schéma pour utiliser des tables de base de données créées dynamiquement, vous ouvrez un tout nouveau monde au prix de la simplicité et du risque de l’enfer SQL;).
Si les éléments sont dans l'arborescence, comme indiqué dans votre exemple, vous pouvez utiliser quelque chose comme l'exemple Python suivant:
delimiter = '.'
stack = []
for item in items:
while stack and not item.startswith(stack[-1]+delimiter):
print "</div>"
stack.pop()
print "<div>"
print item
stack.append(item)
Cela permet de maintenir une pile représentant la position actuelle dans l’arbre. Pour chaque élément de la table, il extrait les éléments de la pile (en fermant les div correspondants) jusqu'à ce qu'il trouve le parent de l'élément en cours. Ensuite, il sort le début de ce noeud et le place dans la pile.
Si vous souhaitez afficher l’arborescence en utilisant l’indentation plutôt que les éléments imbriqués, vous pouvez simplement ignorer les instructions d’impression pour imprimer les div et imprimer un nombre d’espaces égal à un multiple de la taille de la pile avant chaque élément. Par exemple, en Python:
print " " * len(stack)
Vous pouvez également utiliser facilement cette méthode pour construire un ensemble de listes ou de dictionnaires imbriqués.
Éditer: je vois dans votre clarification que les noms n'étaient pas destinés à être des chemins de nœuds. Cela suggère une autre approche:
idx = {}
idx[0] = []
for node in results:
child_list = []
idx[node.Id] = child_list
idx[node.ParentId].append((node, child_list))
Ceci construit un arbre de tableaux de tuples (!). idx [0] représente la ou les racine (s) de l'arbre. Chaque élément d'un tableau est un 2-tuple composé du nœud lui-même et d'une liste de tous ses enfants. Une fois construit, vous pouvez conserver idx [0] et ignorer idx, sauf si vous souhaitez accéder aux nœuds par leur ID.
Pour étendre la solution SQL de Bill, vous pouvez en principe faire de même en utilisant un tableau plat. De plus, si vos chaînes ont toutes la même longueur et que votre nombre maximal d’enfants est connu (par exemple dans un arbre binaire), vous pouvez le faire en utilisant une seule chaîne (tableau de caractères). Si vous avez un nombre d'enfants arbitraire, cela complique un peu les choses ... Il faudrait que je vérifie mes anciennes notes pour voir ce qui peut être fait.
Ensuite, en sacrifiant un peu de mémoire, en particulier si votre arborescence est rare et / ou déséquilibrée, vous pouvez, avec un peu de calcul d'index, accéder à toutes les chaînes de façon aléatoire en stockant votre arborescence, la largeur en premier dans le tableau, pour un arbre binaire):
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
vous connaissez votre longueur de chaîne, vous le savez
Je suis au travail, je ne peux donc pas y passer beaucoup de temps, mais avec un intérêt particulier, je peux aller chercher un peu de code pour le faire.
Nous avons l'habitude de le faire pour rechercher dans des arbres binaires constitués de codons d'ADN, un processus construit pour construire l'arbre, puis nous l'avons aplati pour rechercher des modèles de texte et, une fois trouvé, bien que l'index mathématique (inverse de ci-dessus) récupère le nœud. .. très rapide et efficace, difficile notre arbre a rarement eu des noeuds vides, mais nous pourrions rechercher des giga-octets de données en un tournemain.
Pensez à utiliser des outils nosql tels que neo4j pour les structures hiérarchiques. Par exemple, une application en réseau telle que linkedin utilise couchbase (une autre solution nosql)
Mais utilisez nosql uniquement pour les requêtes de niveau données et ne pas stocker / gérer les transactions
