Metodo relazionale veloce di memorizzare i dati di albero (ad esempio osservazioni filettate su articoli)

Question

Ho un cms che memorizza commenti contro articoli. Questi commenti possono essere sia filettato filettato e non. Anche se tecnicamente sono la stessa cosa solo con la colonna risposta lasciato vuoto quando non è filettato. La mia applicazione funziona su SqlLite, MySQL e pgsql quindi ho bisogno di SQL abbastanza standard.

Al momento ho un tavolo di commento

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

La mia domanda è quello di capire come rappresentare meglio i commenti filettati nel database. Forse in una tabella separata che supporta l'albero set senza il contenuto ed una semplice tabella per contenere il testo? Forse nel modo in cui già è? Forse un altro modo?

Se i commenti sono non-threaded posso facilmente ordinare appena il timestamp.

Se sono filettati I sorta come questo

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

Come si può vedere dalla ORDER BY, le query Commentando non potrà mai utilizzare un indice come indici basati funzione veramente solo vivono in Oracle. Aiutami ho alleggerimento pagine di commento veloci.

Answer 1

Mi piace molto come Drupal risolve questo problema. Si assegna un ID di thread per ogni commento. Questo id inizia da 1 per il primo commento. Se una risposta viene aggiunta a questo commento, l'id 1.1 viene assegnato ad esso. Una risposta per commentare 1.1.1 è dato solo l'ID 1.2. Un fratello del commento <=> è dato solo l'ID <=>. Si ottiene l'idea. CALCOLO questi ID filo può essere fatto facilmente con una sola query quando viene aggiunto un commento.

Quando il filo è reso, tutti i commenti che appartengono al thread sono recuperati in una singola query, in ordine di ID. Questo vi dà i fili in ordine ascendente. Inoltre, utilizzando l'ID, è possibile trovare il livello di nidificazione di ogni commento, e il rientro di conseguenza.

1
1.1
1.1.1
1.2
1.2.1

Ci sono alcuni problemi da risolvere:

• Se un componente del l'ID cresce a 2 cifre, l'ordinamento per filo id non produrrà nell'ordine previsto. Una soluzione semplice è garantire che tutti i componenti di un id filo vengono riempite da zeri per avere la stessa larghezza.
• Ordinamento decrescente filo id non produce l'ordine decrescente previsto.

Drupal risolve il primo problema in maniera più complicata utilizzando un sistema di numerazione chiamato vancode. Per quanto riguarda il secondo aspetto, viene risolto aggiungendo una barra rovesciata (il cui codice ASCII è superiore cifre) infilare ids durante l'ordinamento in ordine decrescente. Potete trovare ulteriori informazioni su questa implementazione controllando il codice sorgente del modulo commenti (vedi il grande commento prima della funzione comment_get_thread).

Answer 2

So che la risposta è un po 'tardi, ma per l'albero di dati di uso una tabella di chiusura http://www.slideshare.net/billkarwin/models-for-hierarchical-data

Si descrive 4 metodi:

• Elenco Adjcency (il semplice genitore chiave esterna)
• Percorso enumerazione (la strategia di Drupal menzionato nella risposta accettata)
• insiemi nidificati
• tavolo Chiusura (memorizzazione fatti antenato / discendente in una relazione separata [tabella], con una possibile colonna distanza)

L'ultima opzione presenta i vantaggi di operazioni CRUD facile rispetto al resto. Il costo è di spazio, che è O (n ^ 2) dimensioni nei nodi numero di alberi nel caso peggiore, ma probabilmente non è così male, in pratica.

Answer 3

Purtroppo, i metodi SQL puri di farlo sono piuttosto lento.

Il NESTED SETS proposta da @Marc W sono piuttosto elegante, ma essi possono richiedere l'aggiornamento del tutto l'albero, se i tuoi rami degli alberi ha colpito gli intervalli, che possono essere piuttosto lento.

Si veda questo articolo nel mio blog su come farlo velocemente in MySQL:

• query gerarchiche in MySQL - s 'Oracle emulando CONNECT BY

È necessario creare una funzione:

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

e utilizzarlo in una query come questa:

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

Questo è naturalmente PostgreSQL specifica ma è veloce reale.

Se si desidera che questo sia betwen portatili <=> e <=>, è possibile utilizzare <=> s 'contrib per <=> e avvolgere la query in una stored procedure con lo stesso nome per entrambi i sistemi.

Answer 4

ho appena fatto io stesso, in realtà! Ho usato il modello insieme nidificato di rappresentare dati gerarchici in un database relazionale.

Gestione dati gerarchici in MySQL era oro puro per me . insiemi nidificati sono il secondo modello descritto in tale articolo.

Answer 5

Hai una scelta tra l'adiacenza e insieme modelli annidati. L'articolo Gestione dati gerarchici in MySQL fa per una bella introduzione.

Per una discussione teorica, vedere di Celko Alberi e gerarchie .

E 'piuttosto facile da implementare una lista filettato se il database supporta le funzioni a finestre. Tutto ciò che serve è un riferimento ricorsivo nella tabella database di destinazione, come ad esempio:

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

È possibile quindi utilizzare un ricorsiva un'espressione di tabella comune per visualizzare una vista filettata. Un esempio è disponibile qui .

Answer 6

In realtà, deve essere un equilibrio tra lettura e scrittura.

Se sei OK con l'aggiornamento di un gruppo di righe su ogni inserto, insieme quindi nidificato (o equivalente) vi darà un facile, veloce legge.

Oltre a questo, una semplice FK sul genitore vi darà ultra-inserto semplice, ma potrebbe anche essere un incubo per il recupero.

Credo che mi piacerebbe andare con i set nidificati, ma fate attenzione sui modelli di volume e utilizzo dei dati attesi (aggiornamento diversi, forse un sacco di, righe su due colonne indicizzate (per info sinistra e destra) per ogni inserto potrebbe essere un problema ad un certo punto).