Bonnes vues d’ensemble
En règle générale, vous prenez une décision entre des temps de lecture rapides (par exemple, un ensemble nested) ou des temps d’écriture rapides (liste d’adjacence). Généralement, vous obtenez une combinaison des options ci-dessous qui correspondent le mieux à vos besoins. Ce qui suit fournit une lecture approfondie:
Les options
Je connais des caractéristiques générales:
O(n/2)
se déplace, insère, supprime en raison de l’encodage volatile O(log n)
(taille du sous-arbre) pour l’insertion, les mises à jour, les suppressions LEFT(lineage, #) = '/enumerated/path'
) O(log n)
(taille du sous-arbre) pour l’insertion, les mises à jour, les suppressions Notes spécifiques à la firebase database
MySQL
Oracle
PostgreSQL
serveur SQL
Ma réponse préférée est ce que la première phrase de ce fil a suggéré. Utilisez une liste de zones adjacentes pour gérer la hiérarchie et utilisez des ensembles nesteds pour interroger la hiérarchie.
Le problème jusqu’à présent était que la méthode de couverture d’une liste Adjacecy aux ensembles nesteds était terriblement lente, car la plupart des gens utilisent la méthode RBAR extrême appelée “Push Stack” pour effectuer la conversion. pour atteindre le Nirvana de la simplicité de la maintenance par la liste des adjacences et les performances impressionnantes des ensembles nesteds. En conséquence, la plupart des gens finissent par devoir se contenter de l’un ou de l’autre, surtout s’il y a plus de 100 000 noeuds environ. Utiliser la méthode de la stack push peut prendre une journée entière pour effectuer la conversion sur ce que les MLM considèrent comme une hiérarchie de plusieurs millions de nœuds.
Je pensais donner un peu de concurrence à Celko en proposant une méthode pour convertir une liste d’adjacence en ensembles nesteds à des vitesses qui semblent tout simplement impossibles. Voici la performance de la méthode de stack push sur mon ordinateur portable i5.
Duration for 1,000 Nodes = 00:00:00:870 Duration for 10,000 Nodes = 00:01:01:783 (70 times slower instead of just 10) Duration for 100,000 Nodes = 00:49:59:730 (3,446 times slower instead of just 100) Duration for 1,000,000 Nodes = 'Didn't even try this'
Et voici la durée de la nouvelle méthode (avec la méthode push stack entre parenthèses).
Duration for 1,000 Nodes = 00:00:00:053 (compared to 00:00:00:870) Duration for 10,000 Nodes = 00:00:00:323 (compared to 00:01:01:783) Duration for 100,000 Nodes = 00:00:03:867 (compared to 00:49:59:730) Duration for 1,000,000 Nodes = 00:00:54:283 (compared to something like 2 days!!!)
Oui c’est correct. 1 million de nœuds convertis en moins d’une minute et 100 000 nœuds en moins de 4 secondes.
Vous pouvez en savoir plus sur la nouvelle méthode et obtenir une copie du code à l’URL suivante. http://www.sqlservercentral.com/articles/Hierarchy/94040/
J’ai également développé une hiérarchie “pré-agrégée” utilisant des méthodes similaires. Les MLM et les personnes qui rédigent des nomenclatures seront particulièrement intéressés par cet article. http://www.sqlservercentral.com/articles/T-SQL/94570/
Si vous vous arrêtez pour jeter un coup d’œil à l’un ou l’autre de ces articles, lancez-vous dans le lien «Rejoignez la discussion» et dites-moi ce que vous en pensez.
Ce design n’a pas encore été mentionné:
Bien qu’il y ait des limites, si vous pouvez les supporter, c’est très simple et très efficace. Caractéristiques:
Voici un exemple – arbre taxonomique des oiseaux de sorte que la hiérarchie est Class / Order / Family / Genus / Species – l’espèce est le niveau le plus bas, 1 rang = 1 taxon (ce qui correspond aux espèces dans le cas des nœuds foliaires):
CREATE TABLE `taxons` ( `TaxonId` smallint(6) NOT NULL default '0', `ClassId` smallint(6) default NULL, `OrderId` smallint(6) default NULL, `FamilyId` smallint(6) default NULL, `GenusId` smallint(6) default NULL, `Name` varchar(150) NOT NULL default '' );
et l’exemple des données:
+---------+---------+---------+----------+---------+-------------------------------+ | TaxonId | ClassId | OrderId | FamilyId | GenusId | Name | +---------+---------+---------+----------+---------+-------------------------------+ | 254 | 0 | 0 | 0 | 0 | Aves | | 255 | 254 | 0 | 0 | 0 | Gaviiformes | | 256 | 254 | 255 | 0 | 0 | Gaviidae | | 257 | 254 | 255 | 256 | 0 | Gavia | | 258 | 254 | 255 | 256 | 257 | Gavia stellata | | 259 | 254 | 255 | 256 | 257 | Gavia arctica | | 260 | 254 | 255 | 256 | 257 | Gavia immer | | 261 | 254 | 255 | 256 | 257 | Gavia adamsii | | 262 | 254 | 0 | 0 | 0 | Podicipediformes | | 263 | 254 | 262 | 0 | 0 | Podicipedidae | | 264 | 254 | 262 | 263 | 0 | Tachybaptus |
C’est génial car de cette façon, vous accomplissez toutes les opérations nécessaires d’une manière très simple, tant que les catégories internes ne changent pas de niveau dans l’arborescence.
C’est une réponse très partielle à votre question, mais j’espère toujours utile.
Microsoft SQL Server 2008 implémente deux fonctionnalités extrêmement utiles pour la gestion des données hiérarchiques:
Jetez un coup d’oeil à “Modélisez vos hiérarchies de données avec SQL Server 2008” par Kent Tegels sur MSDN pour les démarrages. Voir aussi ma propre question: Requête récursive de même table dans SQL Server 2008
Je suis allé là-bas parce que je pouvais insérer facilement de nouveaux éléments dans l’arborescence (vous avez juste besoin d’un identifiant de twig pour y insérer un nouvel élément) et pour l’interroger assez rapidement.
+-------------+----------------------+--------+-----+-----+ | category_id | name | parent | lft | rgt | +-------------+----------------------+--------+-----+-----+ | 1 | ELECTRONICS | NULL | 1 | 20 | | 2 | TELEVISIONS | 1 | 2 | 9 | | 3 | TUBE | 2 | 3 | 4 | | 4 | LCD | 2 | 5 | 6 | | 5 | PLASMA | 2 | 7 | 8 | | 6 | PORTABLE ELECTRONICS | 1 | 10 | 19 | | 7 | MP3 PLAYERS | 6 | 11 | 14 | | 8 | FLASH | 7 | 12 | 13 | | 9 | CD PLAYERS | 6 | 15 | 16 | | 10 | 2 WAY RADIOS | 6 | 17 | 18 | +-------------+----------------------+--------+-----+-----+
parent
. lft
et rgt
de parent. lft
inférieur à lft
et rgt
du nœud plus grand que le rgt
du nœud et sortingez-le par parent
. J’avais besoin de rendre l’access à l’arborescence plus rapide que les insertions, c’est pourquoi j’ai choisi cette option.
Le seul problème est de corriger les colonnes left
et right
lors de l’insertion de nouveaux éléments. Eh bien, j’ai créé une procédure stockée pour cela et l’ai appelée chaque fois que j’ai inséré un nouvel élément, ce qui était rare dans mon cas, mais c’est vraiment rapide. J’ai eu l’idée du livre de Joe Celko, et la procédure stockée et comment je l’ai trouvée est expliquée ici dans DBA SE https://dba.stackexchange.com/q/89051/41481
Si votre firebase database prend en charge les tableaux, vous pouvez également implémenter une colonne de lignage ou un chemin matérialisé sous la forme d’un tableau d’identifiants parents.
Plus précisément, avec Postgres, vous pouvez utiliser les opérateurs de l’ensemble pour interroger la hiérarchie et obtenir d’excellentes performances avec les index GIN. Cela rend la recherche des parents, des enfants et de la profondeur assez simple en une seule requête. Les mises à jour sont également faciles à gérer.
Si vous êtes curieux, j’ai une description complète de l’utilisation de tableaux pour les chemins matérialisés .
Ceci est vraiment une cheville carrée, question de trou rond.
Si les bases de données relationnelles et SQL sont les seuls éléments que vous avez ou êtes prêt à utiliser, les réponses qui ont été affichées sont adéquates. Cependant, pourquoi ne pas utiliser un outil conçu pour gérer les données hiérarchiques? La firebase database de graphes est idéale pour les données hiérarchiques complexes.
Les inefficacités du modèle relationnel et les complexités de toute solution de code / requête pour mapper un modèle graphique / hiérarchique sur un modèle relationnel ne valent pas la peine par rapport à la facilité avec laquelle une solution de firebase database de graphes peut résoudre le même problème.
Considérez une nomenclature comme une structure de données hiérarchique commune.
class Component extends Vertex { long assetId; long partNumber; long material; long amount; }; class PartOf extends Edge { }; class AdjacentTo extends Edge { };
Chemin le plus court entre deux sous-assemblages : algorithme de traversée de graphe simple. Les chemins acceptables peuvent être qualifiés en fonction de critères.
Similarité : Quel est le degré de similitude entre deux assemblées? Effectuez une traversée sur les deux sous-arbres en calculant l’intersection et l’union des deux sous-arbres. Le pourcentage similaire est l’intersection divisée par l’union.
Fermeture transitive : Parcourez le sous-arbre et résumez le ou les champs d’intérêt, par exemple “Quelle quantité d’aluminium dans un sous-ensemble?”
Oui, vous pouvez résoudre le problème avec SQL et une firebase database relationnelle. Cependant, il existe de meilleures approches si vous souhaitez utiliser le bon outil pour le travail.
J’utilise PostgreSQL avec des tables de fermeture pour mes hiérarchies. J’ai une procédure stockée universelle pour toute la firebase database:
CREATE FUNCTION nomen_tree() RETURNS sortinggger LANGUAGE plpgsql AS $_$ DECLARE old_parent INTEGER; new_parent INTEGER; id_nom INTEGER; txt_name TEXT; BEGIN -- TG_ARGV[0] = name of table with entities with PARENT-CHILD relationships (TBL_ORIG) -- TG_ARGV[1] = name of helper table with ANCESTOR, CHILD, DEPTH information (TBL_TREE) -- TG_ARGV[2] = name of the field in TBL_ORIG which is used for the PARENT-CHILD relationship (FLD_PARENT) IF TG_OP = 'INSERT' THEN EXECUTE 'INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) SELECT $1.id,$1.id,0 UNION ALL SELECT $1.id,ancestor_id,depth+1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$1.' || TG_ARGV[2] USING NEW; ELSE -- EXECUTE does not support conditional statements inside EXECUTE 'SELECT $1.' || TG_ARGV[2] || ',$2.' || TG_ARGV[2] INTO old_parent,new_parent USING OLD,NEW; IF COALESCE(old_parent,0) <> COALESCE(new_parent,0) THEN EXECUTE ' -- prevent cycles in the tree UPDATE ' || TG_ARGV[0] || ' SET ' || TG_ARGV[2] || ' = $1.' || TG_ARGV[2] || ' WHERE id=$2.' || TG_ARGV[2] || ' AND EXISTS(SELECT 1 FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ' AND ancestor_id=$2.id); -- first remove edges between all old parents of node and its descendants DELETE FROM ' || TG_ARGV[1] || ' WHERE child_id IN (SELECT child_id FROM ' || TG_ARGV[1] || ' WHERE ancestor_id = $1.id) AND ancestor_id IN (SELECT ancestor_id FROM ' || TG_ARGV[1] || ' WHERE child_id = $1.id AND ancestor_id <> $1.id); -- then add edges for all new parents ... INSERT INTO ' || TG_ARGV[1] || ' (child_id,ancestor_id,depth) SELECT child_id,ancestor_id,d_c+d_a FROM (SELECT child_id,depth AS d_c FROM ' || TG_ARGV[1] || ' WHERE ancestor_id=$2.id) AS child CROSS JOIN (SELECT ancestor_id,depth+1 AS d_a FROM ' || TG_ARGV[1] || ' WHERE child_id=$2.' || TG_ARGV[2] || ') AS parent;' USING OLD, NEW; END IF; END IF; RETURN NULL; END; $_$;
Ensuite, pour chaque table où j’ai une hiérarchie, je crée un déclencheur
CREATE TRIGGER nomenclature_tree_tr AFTER INSERT OR UPDATE ON nomenclature FOR EACH ROW EXECUTE PROCEDURE nomen_tree('my_db.nomenclature', 'my_db.nom_helper', 'parent_id');
Pour remplir une table de fermeture à partir d’une hiérarchie existante, j’utilise cette procédure stockée:
CREATE FUNCTION rebuild_tree(tbl_base text, tbl_closure text, fld_parent text) RETURNS void LANGUAGE plpgsql AS $$ BEGIN EXECUTE 'TRUNCATE ' || tbl_closure || '; INSERT INTO ' || tbl_closure || ' (child_id,ancestor_id,depth) WITH RECURSIVE tree AS ( SELECT id AS child_id,id AS ancestor_id,0 AS depth FROM ' || tbl_base || ' UNION ALL SELECT t.id,ancestor_id,depth+1 FROM ' || tbl_base || ' AS t JOIN tree ON child_id = ' || fld_parent || ' ) SELECT * FROM tree;'; END; $$;
Les tables de fermeture sont définies avec 3 colonnes – ANCESTOR_ID, DESCENDANT_ID, DEPTH. Il est possible (et même conseillé) de stocker des enregistrements de même valeur pour ANCESTOR et DESCENDANT, et une valeur de zéro pour DEPTH. Cela simplifiera les requêtes pour la récupération de la hiérarchie. Et ils sont très simples en effet:
-- get all descendants SELECT tbl_orig.*,depth FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth <> 0; -- get only direct descendants SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON descendant_id = tbl_orig.id WHERE ancestor_id = XXX AND depth = 1; -- get all ancestors SELECT tbl_orig.* FROM tbl_closure LEFT JOIN tbl_orig ON ancestor_id = tbl_orig.id WHERE descendant_id = XXX AND depth <> 0; -- find the deepest level of children SELECT MAX(depth) FROM tbl_closure WHERE ancestor_id = XXX;