Fast Relational Methode von Baumdaten speichern (beispielsweise Gewinde Kommentare zu den Artikeln)

Question

Ich habe ein CMS, die Kommentare gegen Artikel speichert. Diese Kommentare können sowohl mit Gewinde und nicht eingefädelt werden. Obwohl technisch sind sie gleich nur mit der Antwort Spalte leer gelassen, wenn es nicht mit Gewinde versehen ist. Meine Anwendung funktioniert auf SQLLite, MySQL und pgsql so brauche ich ziemlich Standard-SQL.

Im Moment habe ich einen Kommentar Tabelle

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

Meine Frage ist, um herauszufinden, wie man am besten die Gewinde Kommentare in der Datenbank repräsentieren. Vielleicht in einer separaten Tabelle, die den Baum ohne den Inhalt und eine einfache Tabelle zu halten, den Text unterstützt? Vielleicht in der Art und Weise es ohnehin schon ist? Vielleicht eine andere Art und Weise?

Wenn die Kommentare sind un-Threading kann ich einfach nur durch die Zeitstempel bestellen.

Wenn sie Gewinde I Art wie diese

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

Wie Sie aus der ORDER BY sehen können, werden die Kommentierung Abfragen immer keinen Index verwenden als Funktion basiert Indizes nur dann wirklich in Oracle lebt. Helfen Sie uns, haben blitzschnelle Kommentar-Seiten.

Answer 1

Ich mag wirklich, wie Drupal dieses Problem löst. Er weist eine Thread-ID an jeden Kommentar. Diese ID beginnt bei 1 für den ersten Kommentar. Wenn eine Antwort auf diesen Kommentar hinzugefügt wird, wird die ID 1.1 ihm zugeordnet. Eine Antwort 1.1 Kommentar wird den Thread-ID 1.1.1 gegeben. Ein Geschwister Kommentar 1.1 ist der Thread-ID 1.2 gegeben. Du hast die Idee. Berechnung dieser Thread-IDs leicht mit einer Abfrage durchgeführt werden kann, wenn ein Kommentar hinzugefügt wird.

Wenn der Faden wiedergegeben wird, alle Kommentare, die dem Thread gehören geholt in einer einzigen Abfrage, durch die Thread-ID sortiert. Dies gibt Ihnen die Fäden in aufsteigender Reihenfolge. Darüber hinaus können den Thread-ID verwenden, können Sie die Verschachtelungsebene jeden Kommentar finden und einrücken es entsprechend.

1
1.1
1.1.1
1.2
1.2.1

Es gibt ein paar Fragen zu klären:

• Wenn eine Komponente der Thread-ID an 2 Stellen wächst, durch Thread-ID sortiert wird die erwartete Reihenfolge nicht produzieren. Eine einfache Lösung ist gewährleistet, dass alle Komponenten einer Thread-ID werden durch Nullen aufgefüllt, die gleiche Breite haben.
• Sortierung nach Thread-ID absteigend nicht der erwarteten absteigenden Reihenfolge erzeugen.

Drupal löst die erste Ausgabe in einer komplizierteren Weise ein Nummerierungssystem namens vancode. Wie bei der zweiten Ausgabe, wird es durch Anhängen eines umgekehrten Schrägstrich (deren ASCII-Code ist höher als Ziffern) gelöst ids einzufädeln, wenn sie von abnehmender Reihenfolge zu sortieren. Sie können durch Überprüfen der Quellcode des Kommentarmodul (siehe den großen Kommentar vor der Funktion comment_get_thread).

Answer 2

Ich weiß, dass die Antwort ein bisschen spät, aber für Baumdaten verwenden, um eine Schließung Tisch http://www.slideshare.net/billkarwin/models-for-hierarchical-data

Es beschreibt 4 Methoden:

• Adjcency Liste (der einfache Mutterfremdschlüssel)
• Pfad Aufzählung (die Drupal-Strategie in der akzeptierten Antwort erwähnt)
• Verschachtelte Sätze
• Closure Tabelle (Speicher Vorfahr / Abkömmling Tatsachen in einer separaten Beziehung [Tabelle], mit einer möglichen Abstand Spalte)

Die letzte Option hat Vorteile der einfachen CRUD-Operationen im Vergleich zum Rest. Die Kosten sind Raum, die O (n ^ 2) Größe in der Zahl Baumknoten im schlimmsten Fall ist, aber wahrscheinlich nicht so schlecht in der Praxis.

Answer 3

Leider ist die reinen SQL-Methoden zu tun, es ist ziemlich langsam.

Die NESTED SETS von @Marc W vorgeschlagen sind sehr elegant, aber sie können verlangen, den ganzen Baum zu aktualisieren, wenn Ihre Äste die Bereiche getroffen, die sehr langsam sein kann.

Lesen Sie diesen Artikel in meinem Blog auf, wie es geht schnell in MySQL:

• Hierarchische Abfragen in MySQL - emuliert Oracle des CONNECT BY

Sie müssen eine Funktion erstellen:

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

und es in einer Abfrage wie folgt verwendet werden:

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

Das ist natürlich MySQL spezifisch, aber es ist wirklich schnell.

Wenn Sie diese betwen PostgreSQL und MySQL tragbar sein möchten, können Sie PostgreSQL contrib für CONNECT BY und wickeln Sie die Abfrage in eine gespeicherte Prozedur mit demselben Namen für beide Systeme verwendet werden.

Answer 4

Ich habe gerade diese selbst, tatsächlich! Ich benutzen das Nested Set in einer relationalen Datenbank hierarchische Daten zu repräsentieren.

Verwalten hierarchischer Daten in MySQL reines Gold für mich . Verschachtelte Sätze sind das zweite Modell in diesem Artikel beschrieben wird.

Answer 5

Sie haben die Wahl zwischen dem adjacency und den verschachtelten Satz Modellen bekommen. Der Artikel Verwalten hierarchischer Daten in MySQL für eine schöne Einführung macht.

Für eine theoretische Diskussion siehe Celko Bäume und Hierarchien .

Es ist ziemlich einfach, eine verbundene Liste, wenn Ihre Datenbank unterstützt Windowing-Funktionen zu implementieren. Alles, was Sie brauchen, ist eine rekursive Referenz in Ihrer Zieldatenbanktabelle, wie zum Beispiel:

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

Sie können dann einen rekursiven allgemeinen Tabellenausdruck verwenden, um eine Gewindeansicht anzuzeigen. Ein Beispiel dafür ist verfügbar hier rel="nofollow.

Answer 6

Eigentlich hat es ein Gleichgewicht zwischen zu lesen und schreiben.

Wenn Sie mit der Aktualisierung ein paar Zeilen auf jeder Einsatz in Ordnung sind, dann verschachtelt Satz (oder ein Äquivalent) wird Ihnen einfach, schnell liest.

Other than that, ein einfaches FK auf den Eltern geben Sie ultra-einfachen Einsatz, kann aber auch ein Alptraum für den Abruf sein.

Ich denke, dass ich mit den verschachtelten Sätzen gehen würde, aber über das erwarteten Datenvolumen und Nutzungsmuster (Aktualisierung mehr, vielleicht viele Zeilen auf zwei indizierte Spalten (für links und rechts info) für jeden Einsatz vorsichtig sein könnten sein ein Problem an einem gewissen Punkt).