Quelle est la façon la plus efficace / élégante de couper une table plate en un arbre?
supposons que vous ayez une table plate qui stocke une hiérarchie d'arbre 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] 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 produire cela en HTML (ou en texte, d'ailleurs) comme un arbre correctement ordonné, correctement indenté?
supposons en outre que vous avez seulement des structures de données de base( tableaux et hachmaps), aucune Fantaisie objets avec références parents / enfants, pas D'ORM, pas de cadre, juste vos deux mains. La table est représentée sous la forme d'un jeu de résultats auquel on peut accéder au hasard.
Pseudo code ou simple anglais est acceptable, c'est une question purement conceptuelle.
question Bonus: y a-t-il une meilleure façon de stocker une structure arborescente comme celle-ci dans un RDBMS?
MODIFICATIONS ET AJOUTS
pour répondre à la question d'un commentateur ( Mark Bessey 's): un noeud racine n'est pas nécessaire, parce qu'il ne sera jamais affiché de toute façon. ParentId = 0 est la convention pour exprimer "ce sont de haut niveau". La colonne Ordre définit comment les noeuds avec le même parent seront 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). Pour mon exemple était censé être déjà y. Certaines réponses vont plus loin et construisent d'abord, mais c'est pas grave.
l'arbre peut être arbitrairement profond. Chaque noeud peut avoir N enfants. Je n'avais pas exactement un arbre "des millions d'entrées" à l'esprit, cependant.
ne confondez pas mon choix de nom de noeud ('noeud 1.1.1') avec quelque chose sur lequel compter. Les noeuds peuvent tout aussi bien être appelés 'Frank' ou 'Bob', aucune structure de nommage n'est implicite, ceci était simplement pour le rendre lisible.
j'ai posté ma propre solution pour que vous puissiez la mettre en pièces.
14 réponses
maintenant que MySQL 8.0 est sur le point de sortir, toutes les bases de données SQL populaires supporteront 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 Recursive Query Throwdown en 2017.
ci-dessous est ma réponse originale de 2008:
les données dans une base de données relationnelle. Ce que vous montrez dans votre exemple utilise deux méthodes:
- liste de contiguïté (colonne "parent") et
- chemin D'énumération (les numéros en pointillés dans la colonne de votre nom).
une autre solution est appelée ensembles imbriqués , et il peut être stocké dans la même table aussi. Lire arbres et Hiérarchies en SQL pour Smarties " par Joe Celko pour beaucoup plus d'informations sur ces conceptions.
je préfère habituellement un modèle appelé table de fermeture (alias" relation de contiguïté") pour stocker des données structurées par arbre. Il nécessite une autre table, mais alors interroger les arbres est assez facile.
je couvre la table de fermeture dans ma présentation modèles pour les données hiérarchiques avec SQL et PHP et dans mon livre SQL Antipatterns: É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 ya une ascendance directe d'un nœud à un autre. Inclure une ligne pour chaque nœud de référence 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);
Maintenant vous pouvez 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 à ce qui suit:
+----+
| id |
+----+
| 1 |
| 2 |
| 4 |
| 6 |
+----+
en d'autres termes, les noeuds 3 et 5 sont exclus, parce qu'ils font partie d'une hiérarchie séparée, ne descendant pas du noeud 1.
Re: commentaires de e-satis sur les enfants immédiats (ou le parent immédiat). Vous pouvez ajouter une colonne" path_length " à la colonne ClosureTable pour faciliter la recherche spécifiquement pour un enfant immédiat ou un parent (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);
, Alors vous pouvez ajouter un terme de votre recherche pour interroger les enfants immédiats d'un nœud donné. Ce sont des descendants dont le 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 comment from @ashraf: "Que Diriez-vous de trier l'arbre entier [par son nom]?"
voici un exemple de requête pour retourner tous les noeuds qui sont des descendants du noeud 1, les joindre au FlatTable qui contient d'autres attributs de noeud comme 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;
Re 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 édition aujourd'hui. Donc les modérateurs ont approuvé l'édition, mais je l'inverse.
l'édition a suggéré que l'ORDRE PAR dans la dernière requête ci-dessus devrait être ORDER BY b.path_length, f.name , probablement pour s'assurer que l'ordre correspond à la hiérarchie. Mais ce n'est pas fonctionne, parce qu'il commanderait "noeud 1.1.1" après "noeud 1.2".
si vous voulez que l'ordre corresponde à la hiérarchie d'une manière raisonnable, c'est possible, mais pas simplement en ordonnant par la longueur du chemin. Par exemple, voir ma réponse à MySQL Fermeture de la Table de base de données hiérarchique - Comment extraire des informations dans le bon ordre .
si vous utilisez des ensembles imbriqués (parfois appelé Arbre de traversée modifié avant l'ordre), vous pouvez extraire la structure entière de l'arbre ou n'importe quel sous-arbre à l'intérieur de celle-ci dans l'ordre de l'arbre avec une seule requête, au coût d'inserts étant plus coûteux, comme vous avez besoin de gérer des colonnes qui décrivent un chemin dans l'ordre à travers la structure de l'arbre.
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 un arbre qui ressemble à ceci (avec id représentant chaque élément):
1
+-- 2
| +-- 3
| +-- 4
|
+-- 5
+-- 6
+-- 7
ou, comme un diagramme de série imbriqué qui rend plus évidente la façon dont les valeurs lft et rght fonctionnent:
__________________________________________________________________________ | 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 toute la sous-arborescence pour un noeud donné, dans l'ordre de l'arbre, vous devez simplement sélectionner toutes les lignes qui ont des valeurs lft et rght entre ses valeurs lft et rght . C'est aussi simple pour récupérer l'arbre des ancêtres pour un noeud donné.
la colonne level est un peu de dénormalisation pour la commodité plus que tout et la colonne tree_id vous permet de redémarrer la numérotation lft et rght pour chaque noeud de premier niveau, ce qui réduit le nombre de colonnes affectées par inserts, mouvements et suppressions, car les colonnes lft et rght doivent être ajustées en conséquence lorsque ces opérations ont lieu dans afin de créer ou de combler les lacunes. J'ai fait quelques notes de développement au moment où j'essayais d'enrouler ma tête autour des requêtes nécessaires pour chaque opération.
en termes de travail réel avec ces données pour afficher un arbre, j'ai créé une fonction utilitaire tree_item_iterator qui, pour chaque noeud, devrait vous donner suffisamment d'informations pour générer n'importe quel type d'affichage que vous voulez.
plus d'information à propos de MPTT:
depuis 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)
depuis 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]
tous deux produiront les résultats suivants.
Name 'Node 1' ' Node 1.1' ' Node 1.1.1' ' Node 1.2' 'Node 2' ' Node 2.1'
c'est une question assez ancienne, mais comme il a de nombreux points de vue, je pense qu'il vaut la peine de présenter une alternative, et à mon avis très élégante, solution.
pour lire une structure arborescente, vous pouvez utiliser (CTEs). Il donne la possibilité de récupérer la structure entière de l'arbre à la fois, avoir les informations sur le niveau du noeud, son noeud parent et l'ordre dans les enfants du noeud parent.
Permettez-moi de 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 noeuds d'arbre sont ordonnés par un niveau de profondeur. Dans le résultat final nous les présentons dans les lignes suivantes.
pour chaque niveau, ils sont ordonnés par parent_id et node_order dans le parent. Ceci nous indique comment les présenter dans le noeud output - link au parent dans cet ordre.
ayant une telle structure, il ne serait pas difficile de faire une très belle présentation en HTML.
CTEs récursifs sont disponibles en PostgreSQL, IBM DB2, MS SQL Server et Oracle .
si vous souhaitez en savoir plus sur les requêtes SQL récursives, vous pouvez soit documentation de vos SGBD préférés ou lire mes deux articles couvrant ce sujet:
la réponse de Bill est sacrément bonne, cette réponse y ajoute des choses qui me font souhaiter des réponses filetées si soutenues.
de toute façon je voulais soutenir la structure de l'arbre et la propriété de L'ordre. J'ai inclus une propriété unique dans chaque noeud appelé leftSibling qui fait la même chose Order est destiné à faire dans la question originale (maintenir 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 de code SQL sur mon blog .
Merci Bill votre réponse a été utile pour commencer!
si j'avais le choix, j'utiliserais des objets. Je créerais un objet pour chaque enregistrement où chaque objet a une collection children et les stocke 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 enfants pertinents. Simple.
mais parce que vous n'êtes pas amusant en limitant l'utilisation d'une bonne OOP, je voudrais probablement itérer basé sur:
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 légèrement plus propre. Une chose que j'ajouterai: c'est extrêmement intensif en SQL. C'est nasty . si vous avez le choix, suivez la route OOP.
cela a été écrit rapidement, et n'est ni jolie ni efficace (plus il autoboxes alot, conversion entre int et Integer est ennuyeux!), mais il fonctionne.
cela enfreint probablement les règles puisque je crée mes propres objets mais hey je fais cela comme une diversion du vrai travail :)
cela suppose également que le jeu de résultats / table est complètement lu dans une sorte de structure avant de commencer à construire des noeuds, qui ne seraient pas le 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 savez que les éléments racine sont zéro, voici le pseudocode pour sortir au 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 un hashmap, donc ce n'est pas une limitation terrible. En scannant de haut en 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 "master", saisi sur l'id. Si un noeud a un "parent" que vous n'avez pas encore vu, créez une entrée placeholder pour lui dans le HashMap maître, et remplissez le quand vous voyez le noeud réel.
pour l'imprimer, faire une profondeur simple-d'abord passer à travers les données, en gardant la trace du niveau d'indentation le long du chemin. Vous pouvez rendre cela plus facile en gardant une entrée "enfants" pour chaque ligne, et en la peuplant pendant que vous scannez les données.
quant à savoir s'il y a une "meilleure" façon 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 qui avaient une profondeur maximale connue et qui utilisaient une table différente pour chaque niveau de la hiérarchie. Qui fait beaucoup de sens si les niveaux dans l'arbre n'est pas tout à fait équivalent après tout (catégories de niveau supérieur étant différent que les feuilles).
il y a vraiment de bonnes solutions qui exploitent la représentation btree interne des indices sql. Ceci est basé sur de grandes recherches effectuées aux alentours de 1998.
Voici un exemple de tableau (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 de l'arbre sont:
- tw: l'indice de pré-ordre DFS de gauche à droite, où root = 1.
- pa: la référence (en utilisant tw) à le noeud parent, root a nul.
- sz: la 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 la tw du "prochain enfant"du noeud.
voici un exemple de population de noeuds, 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'arbre peut être fait de façon non-récursive. Par exemple, pour obtenir une liste des ancêtres de 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 pa field ordering par tw.
Descendants
par exemple l'ensemble (branche) de noeuds 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 lorsqu'il y a une plus de lectures qu'il n'y a d'encarts ou de mises à jour.
Parce que l'insertion, le mouvement, ou la mise à jour d'un nœud dans l'arbre nécessite l'arbre pour être ajustée, il est nécessaire de verrouiller la table avant de commencer l'action.
le coût d'insertion/suppression est élevé car l'indice tw et les valeurs sz (taille de la branche) devront être mis à jour sur tous les noeuds après le point d'insertion, et pour tous les ancêtres respectivement.
déplacement de branche implique le déplacement de 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 existe essentiellement quatre requêtes nécessaires pour déplacer une branche:
- Déplacer la branche hors de portée.
- fermer la brèche qu'il a laissé. (l'arbre restant est maintenant normalisé).
- ouvrir la brèche où elle ira.
- déplacer le dans sa nouvelle position.
Ajuster Arbre De Requêtes
l'ouverture/fermeture des trous dans l'arbre est une sous-fonction importante utilisée par les méthodes create/update / delete, donc je l'inclus ici.
nous avons besoin de deux paramètres - un drapeau représentant si oui ou non nous réduisons ou augmentons, et l'index tw du noeud. Ainsi, par exemple tw=18 (qui a une taille de branche de 5). Supposons que nous sommes réduction des effectifs (suppression de tw) - cela signifie que nous utilisons '-' au lieu de '+' dans les mises à jour de l'exemple suivant.
nous utilisons d'abord une fonction d'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 la tw, pour ceux dont la tw est supérieure à la branche pour être supprimé.
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 la tw du pa est plus élevée que 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 imbriquées ou des tableaux peuvent être créés, alors je peux simplement descendre la table du début et ajouter chaque élément au tableau imbriqué. Je dois tracer chaque ligne jusqu'au noeud racine afin de savoir dans quel niveau dans le tableau imbriqué insérer. Je peux employer la mémoïsation pour que je n'aie pas besoin de chercher le même parent encore et encore.
Edit: je voudrais lire la table entière dans un tableau d'abord, de sorte qu'il ne sera pas interroger la base de données à plusieurs reprises. Bien sûr, ce ne sera pas être pratique si votre table est très importante.
après la construction de la structure, je dois faire un tour en profondeur et imprimer le HTML.
il n'y a pas de meilleure façon fondamentale de stocker cette information en utilisant une seule table (je pourrais me tromper ;), et j'aimerais voir une meilleure solution ). Cependant, si vous créez un schéma pour employer des tables de db créées dynamiquement, alors vous avez ouvert un tout nouveau monde au sacrifice de la simplicité, et le risque of SQL hell ;).
si les éléments sont dans l'ordre de l'arbre, 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)
ce n'est maintenir une pile représentant la position courante dans l'arbre. Pour chaque élément du tableau, il Pop éléments de pile (fermeture des divs correspondants) jusqu'à ce qu'il trouve le parent de l'élément courant. Puis il sort le début de ce noeud et le pousse vers la pile.
si vous voulez sortir l'arbre utilisant l'indentation plutôt que des éléments imbriqués, vous pouvez simplement sauter les instructions d'impression pour imprimer les divs, et imprimer un nombre d'espaces égal à un certain multiple de la taille de la pile avant chaque élément. Par exemple, en Python:
print " " * len(stack)
, Vous pouvez facilement utiliser cette méthode pour construire un ensemble de listes imbriquées ou les dictionnaires.
Edit: je vois de votre clarification que les noms n'étaient pas destinés à être des chemins de noeuds. Qui 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))
cela construit un arbre de tableaux de tuples(!). idx[0] représente la racine(s) de l'arbre. Chaque élément d'un tableau est un 2-tuple composé du nœud lui-même et une liste de tous ses enfants. Une fois construit, vous pouvez garder idx[0] et rejeter idx, à moins que vous ne vouliez accéder aux noeuds par leur ID.
pour étendre la solution SQL de Bill, vous pouvez faire la même chose en utilisant un tableau plat. En outre, si vos chaînes ont toutes la même longueur et que votre nombre maximum 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 arbitraire d'enfants, cela complique un peu les choses... Je dois vérifier mes anciennes notes, pour voir ce qui peut être fait.
alors, sacrifiant un peu de mémoire, surtout si votre arbre est clairsemé et / ou déséquilibré, vous pouvez, avec un peu d'index math, accéder à toutes les chaînes au hasard en stockant votre arbre, largeur d'abord dans le tableau comme so (pour un arbre binaire):
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
vous connaissez la longueur de votre corde, vous le savez
je suis au travail maintenant, donc je ne peux pas y passer beaucoup de temps, mais avec intérêt, je peux récupérer un peu de code pour le faire.
nous l'employons pour le faire à la recherche dans les arbres binaires faits de codons D'ADN, un processus construit le arbre, puis nous l'avons aplati pour rechercher des modèles de texte et une fois trouvé, bien que l'index math (des verveux d'en haut) nous récupérons le noeud... très rapide et efficace, tough notre arbre avait rarement des noeuds vides, mais nous pouvions chercher des gigabytes de données en un clin d'œil.
pensez à utiliser des outils nosql comme neo4j pour les structures hiérarchiques. E. g une application en réseau comme linkedin utilise couchbase (une autre solution nosql)
mais n'utiliser nosql que pour les requêtes au niveau data-mart et ne pas stocker /maintenir les transactions