método rápido relacional de armazenamento de dados da árvore (por exemplo rosca comentários sobre artigos)

StackOverflow https://stackoverflow.com/questions/846201

Pergunta

Eu tenho um cms que armazena comentários contra artigos. Estes comentários podem ser tanto threaded e não. Embora tecnicamente eles são o mesmo apenas com a coluna de resposta em branco quando ele não está encadeado. Meu aplicativo funciona em SqlLite, MySQL e pgsql Então eu preciso de SQL bastante normal.

Actualmente tenho um comentário a tabela 

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

A minha pergunta é descobrir a melhor forma de representar os comentários rosqueados na base de dados. Talvez em uma tabela separada que suporta o conjunto de árvore sem o conteúdo e uma tabela simples para manter o texto? Talvez no caminho que já é? Talvez uma outra maneira?

Se os comentários são un-threaded eu posso facilmente apenas a ordem pela timestamp.

Se eles são enfiados eu classifico como este 

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

Como você pode ver a partir do ORDER BY, as consultas comentando nunca vai usar um índice como função baseada índices só é realmente vivos em Oracle. Ajuda-me ter um raio de comentário páginas rápidas.

Foi útil?

Solução

Eu realmente gosto de como Drupal resolve este problema. Ele atribui um ID de thread para cada comentário. Este id começa em 1 para o primeiro comentário. Se a resposta for acrescentada a este comentário, o 1.1 ID é atribuído a ele. A resposta ao comentário 1.1 é dada a 1.1.1 fio id. Um irmão do comentário 1.1 é dada a 1.2 fio id. Você entendeu a ideia. Calcular esses ids de rosca pode ser feito facilmente com uma consulta quando um comentário é adicionado.

Quando o segmento é processado, todos os comentários que pertencem ao thread são obtidos em uma única consulta, classificado pelo identificador do tópico. Isto dá-lhe os fios na ordem crescente. Além disso, usando o identificador do tópico, você pode encontrar o nível de aninhamento de cada comentário, e recuar lo em conformidade. 

1
1.1
1.1.1
1.2
1.2.1

Existem algumas questões para resolver:

  • Se um componente do identificador do tópico cresce a 2 dígitos, a classificação por identificador do tópico não vai produzir a ordem esperada. Uma solução fácil é garantir que todos os componentes de um identificador do tópico são preenchidos por zeros ter a mesma largura.
  • Classificação descendo identificador do tópico não produz a ordem descendente esperado.

Drupal resolve o primeiro problema de uma forma mais complicada utilizando um sistema de numeração chamado vancode. Quanto à segunda questão, que é resolvido adicionando uma barra invertida (cujo código ASCII é maior do que dígitos) para enfiar ids ao ordenar por ordem decrescente. Você pode encontrar mais detalhes sobre essa implementação, verificando o código-fonte do rel comentários módulo (ver a grande comentário antes da comment_get_thread função).

Outras dicas

Eu sei a resposta é um pouco tarde, mas para a árvore de dados usar uma tabela de fechamento http://www.slideshare.net/billkarwin/models-for-hierarchical-data

Ele descreve 4 métodos:

  • lista Adjcency (o pai de chave estrangeira simples)
  • enumeração Path (a estratégia Drupal mencionado na resposta aceite)
  • conjuntos aninhados
  • tabela de fecho (armazenando ancestral / fatos descendentes em uma relação em separado [Tabela], com uma coluna de distância possível)

A última opção tem vantagens de operações CRUD fácil em comparação com o resto. O custo é de espaço, que é O (n ^ 2) tamanho nos gânglios número de árvores no pior caso, mas provavelmente não tão ruim na prática.

Infelizmente, os métodos SQL puro para fazê-lo são bastante lento.

O NESTED SETS proposto por @Marc W são bastante elegante, mas eles podem exigir atualizando toda a árvore se seus galhos de árvores atingiu as faixas, que pode ser bastante lento.

Veja este artigo no meu blog sobre como fazê-lo rápido em MySQL:

Você vai precisar para criar uma função: 

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 usá-lo em uma consulta como esta: 

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

Este é, naturalmente específica MySQL mas é muito rápido.

Se você quer que isso seja PostgreSQL betwen portátil e MySQL, você pode usar contrib do PostgreSQL para CONNECT BY e envolva a consulta em um procedimento armazenado com o mesmo nome para ambos os sistemas.

Eu apenas fiz isso mesmo, na verdade! Eu usei o modelo de conjunto aninhado de representar dados hierárquicos em um banco de dados relacional.

Gerenciamento de dados hierárquicos em MySQL era de ouro puro para mim . conjuntos aninhados são o segundo modelo descrito nesse artigo.

Você tem uma escolha entre a adjacência e os modelos de conjunto aninhado. O artigo Gerenciamento de dados hierárquicos em marcas MySQL para uma boa introdução.

Para uma discussão teórica, consulte Árvores de Celko e hierarquias .

É bastante fácil de implementar uma lista de rosca se o seu banco de dados suporta de janelas funções. Tudo que você precisa é uma referência recursiva na sua tabela de banco de dados alvo, tais como: 

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

Você pode então usar um recursivo expressão de tabela comum para exibir uma visão de rosca. Um exemplo está disponível aqui .

Na verdade, tem que haver um equilíbrio entre ler e escrever.

Se você está OK com a atualização de um monte de linhas em cada inserção, conjunto, em seguida, aninhada (ou equivalente) lhe dará fácil, rápido lê.

Além disso, um simples FK no pai lhe dará ultra-simples inserção, mas poderia muito bem ser um pesadelo para recuperação.

Eu acho que eu iria com os conjuntos aninhados, mas tenha cuidado sobre os padrões de volume de dados e utilização esperada (atualizando vários, talvez um monte de, fileiras em duas colunas indexadas (para informações esquerda e direita) para cada força de inserção ser um problema em algum ponto).

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top