Rapide méthode Relational de stockage de données d'arbre (par exemple des commentaires sur les articles filetés)

https://stackoverflow.com/questions/846201

21-08-2019
|

Question

J'ai un CMS qui stocke des commentaires contre des articles. Ces commentaires peuvent être à la fois filetés et non filetés. Bien qu'ils soient techniquement la même juste avec la colonne de réponse laissée en blanc quand il est pas enfilée. Mon application fonctionne sur SqlLite, MySQL et pgsql donc j'ai besoin assez standard SQL.

J'ai actuellement une table de commentaire

comment_id
article_id
user_id
comment
timestamp
thread (this is the reply column)

Ma question est de savoir comment mieux représenter les commentaires filetés dans la base de données. Peut-être dans un tableau distinct qui prend en charge l'arbre sans mettre le contenu et une simple table pour contenir le texte? Peut-être dans la façon dont il est déjà? Peut-être une autre façon?

Si les commentaires sont un-thread, je peux facilement simplement commander par l'horodatage.

Si elles sont je sorte enfilés comme ceci

ORDER BY SUBSTRING(c.thread, 1, (LENGTH(c.thread) - 1))

Comme vous pouvez le voir ORDER BY, les requêtes commentent ne pourra jamais utiliser un index en fonction des index basés uniquement vraiment vivent dans Oracle. Aide-moi éclaircir les pages de commentaires rapides.

La solution

Je aime vraiment comment Drupal permet de résoudre ce problème. Il attribue un identifiant de fil à chaque commentaire. Cet ID commence à 1 pour le premier commentaire. Si une réponse est ajouté à ce commentaire, l'identifiant est attribué à 1.1 il. Une réponse à des commentaires est donnée l'1.1.1 id fil 1.2. Un frère de commentaires est donné l'<=> id fil <=>. Vous avez eu l'idée. Calcul de ces ids de fil peut se faire facilement avec une requête lorsqu'un commentaire est ajouté.

Lorsque le fil est rendu, tous les commentaires qui appartiennent au fil sont récupérés dans une seule requête, triés par l'identifiant de fil. Cela vous donne les fils dans l'ordre croissant. De plus, en utilisant l'identifiant de fil, vous pouvez trouver le niveau d'imbrication de chaque commentaire et indentera en conséquence.

1
1.1
1.1.1
1.2
1.2.1

Il y a quelques questions à trier:

Si un composant de l'ID de fil augmente à 2 chiffres, le tri par id fil ne produira pas l'ordre attendu. Une solution facile est d'assurer que tous les composants d'un identifiant de fil sont rembourrées par des zéros pour avoir la même largeur.
Tri par décroissant id fil ne produit pas l'ordre décroissant attendu.

Drupal résout le premier problème d'une manière plus compliquée à l'aide d'un système de numérotation appelé vancode. En ce qui concerne le deuxième problème, il est résolu en ajoutant une barre oblique inverse (dont le code ASCII est supérieur à celui des chiffres) pour enfiler ids lors du tri par ordre décroissant. Vous pouvez trouver plus de détails sur cette mise en œuvre en vérifiant le code source de module commentaires (voir le grand commentaire avant que la fonction comment_get_thread).

Autres conseils

Je sais que la réponse est un peu en retard, mais pour les données arbres utiliser un code de fermeture http://www.slideshare.net/billkarwin/models-for-hierarchical-data

Il décrit les méthodes 4:

Liste de Adjcency (parent simple clé étrangère)
énumération Path (la stratégie Drupal mentionné dans la réponse acceptée)
ensembles emboîtés
Tableau de fermeture (stockage de données ancêtre / descendant dans une relation séparée [Table], avec une colonne possible à distance)

La dernière option présente des avantages des opérations de CRUD facile par rapport aux autres. Le coût est de l'espace, qui est O taille (n ^ 2) dans les nœuds d'arbres numéro dans le pire des cas, mais probablement pas si mal dans la pratique.

Malheureusement, les méthodes pures SQL pour le faire sont assez lent.

Le proposé par NESTED SETS sont tout à fait élégante @Marc W mais ils peuvent nécessiter la mise à jour de l'arbre entier si vos branches d'arbres ont frappé les plages, ce qui peut être assez lent.

Voir cet article dans mon blog sur la façon de le faire rapidement dans MySQL:

requêtes hiérarchiques dans MySQL - l 'émule Oracle CONNECT BY

Vous devez créer une fonction:

CREATE FUNCTION hierarchy_connect_by_parent_eq_prior_id(value INT) RETURNS INT
NOT DETERMINISTIC
READS SQL DATA
BEGIN
        DECLARE _id INT;
        DECLARE _parent INT;
        DECLARE _next INT;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET @id = NULL;

        SET _parent = @id;
        SET _id = -1;

        IF @id IS NULL THEN
                RETURN NULL;
        END IF;

        LOOP
                SELECT  MIN(id)
                INTO    @id
                FROM    t_hierarchy
                WHERE   parent = _parent
                        AND id > _id;
                IF @id IS NOT NULL OR _parent = @start_with THEN
                        SET @level = @level + 1;
                        RETURN @id;
                END IF;
                SET @level := @level - 1;
                SELECT  id, parent
                INTO    _id, _parent
                FROM    t_hierarchy
                WHERE   id = _parent;
        END LOOP;
END

et l'utiliser dans une requête comme ceci:

SELECT  hi.*
FROM    (
        SELECT  hierarchy_connect_by_parent_eq_prior_id(id) AS id, @level AS level
        FROM    (
                SELECT  @start_with := 0,
                        @id := @start_with,
                        @level := 0
                ) vars, t_hierarchy
        WHERE   @id IS NOT NULL
        ) ho
JOIN    t_hierarchy hi
ON      hi.id = ho.id

Ceci est bien sûr spécifique, mais ce PostgreSQL est vraiment rapide.

Si vous voulez que ce soit portable Situés entre et <=> <=>, vous pouvez utiliser contrib de pour <=> et envelopper la <=> requête dans une procédure stockée avec le même nom pour les deux systèmes.

Je viens de faire moi-même, en fait! J'utilisé le modèle de série emboîtée de représenter des données hiérarchiques dans une base de données relationnelle.

Gestion des données hiérarchiques dans MySQL était d'or pur pour moi . ensembles imbriqués sont le deuxième modèle décrit dans cet article.

Vous avez le choix entre la contiguïté et les modèles imbriqués ensemble. L'article Gestion des données hiérarchiques dans MySQL fait pour une bonne introduction.

Pour une discussion théorique, voir Celko arbres et Hiérarchies.

Il est assez facile à mettre en œuvre une liste filetée si votre base de données prend en charge les fonctions de fenêtrage. Tout ce que vous avez besoin est une référence récurrente dans votre base de données cible, telles que:

create Tablename (
  RecordID integer not null default 0 auto_increment,
  ParentID integer default null references RecordID,
  ...
)

Vous pouvez ensuite utiliser une expression récurrente de la table commune pour afficher une vue filetée. Un exemple est disponible .

En fait, il doit y avoir un équilibre entre lecture et d'écriture.

Si vous êtes OK avec la mise à jour d'un groupe de lignes sur chaque insert, puis emboîtés ensemble (ou un équivalent) vous donnera facilement, des lectures rapides.

Autre que cela, un simple FK sur le parent vous donnera insert ultra-simple, mais pourrait bien être un cauchemar pour la récupération.

Je pense que je partirais avec les ensembles imbriqués, mais attention sur les modèles de volume de données attendu et d'utilisation (mise à jour de plusieurs, peut-être beaucoup de, rangées sur deux colonnes indexées (informations relatives à gauche et à droite) pour chaque insert pourrait être un problème à un moment donné).

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow