O velho problema “pai” em conjuntos de dados baseados em árvore é antigo. A questão continua: “como você obtém um conjunto de dados com pais e filhos rapidamente, sem ter que escrever uma consulta recursiva ou massiva de junção aninhada?” Os casos de uso mais comuns para isso são estrutura de página, pastas ou comentários encadeados.
Conjuntos aninhados são uma solução, mas geralmente podem ser pesados e inflexíveis. Uma das minhas formas preferidas de obter esses dados é usar uma estrutura chamada “Tabela de Fechamento”, na qual você armazena todos os caminhos de um nó para outro na árvore. Esta solução permite travessias de nós da árvore em tempo O (N) ou menos. A compensação é obviamente o espaço, já que agora você está armazenando um pouco mais de dados em termos de caminho, mas geralmente é preferível.
Começando
A configuração é simples. Usaremos um sistema de comentários encadeados como exemplo. Vamos supor que temos as seguintes tabelas (simplificadas para este tutorial):
comment
- id
- text
- parent
- rank
comment_closure
- ancestor
- descendant
- depthNossa tabela de comentários tem simplesmente um ID gerado automaticamente do comentário, o texto e o ID do comentário pai. Ele também tem uma “classificação”, que veremos mais tarde. A seguir está a tabela de fechamento para os comentários, na qual armazenamos “ancestral” (o pai), “descendente” (o filho) e “profundidade”, que é o nível de profundidade da raiz da árvore.
Digamos que temos uma árvore de comentários como esta:
1
| - 2
| - 3
| - 6
| - 5
| - 4Digamos que queremos capturar o comentário 2 e todos os seus filhos – em uma consulta. Fazer uma ordem direta por ID não funcionará, pois o 6º comentário foi postado após o 5º, mas está em um local diferente na navegação da árvore. Um criado por também não funcionará. Então, é aqui que entram nossas tabelas de fechamento.
A Mesa de Fechamento
Nossos dados de fechamento para esta árvore se parecem com isto:
INSERT INTO `comments_closure` (`ancestor`, `descendant`, `depth`) VALUES
(1, 1, 0),
(0, 1, 0),
(2, 2, 0),
(1, 2, 1),
(0, 2, 1),
(3, 3, 0),
(1, 3, 2),
(2, 3, 1),
(0, 3, 2),
(4, 4, 0),
(1, 4, 1),
(0, 4, 1),
(5, 5, 0),
(1, 5, 2),
(2, 5, 1),
(0, 5, 2),
(6, 6, 0),
(1, 6, 3),
(2, 6, 2),
(3, 6, 1),
(0, 6, 3);Você pode ver a ancestralidade na tabela aqui – cada comentário tem um mapeamento completo de como ele se relaciona com todos os outros comentários em sua linhagem. Então, agora podemos escrever nossa consulta:
SELECT `id`,`parent` FROM `comments` `comment`
JOIN `comments_closure` `closure`
ON `comment`.`id` = `closure`.`descendant`
WHERE `closure`.`ancestor` = 2Isso nos retorna esta bela tabela:
id parent
2 1
3 2
5 2
6 3Ótimo! Exceto uma coisa. Os comentários não são classificados; 6 deve ser antes de 5. Bem, isso torna difícil ler um tópico de comentários, com certeza. Precisamos de classificação .
Ranking
A classificação é realmente uma coisa complicada de fazer; você não pode simplesmente inserir um número em uma coluna e torná-lo a classificação – fazer isso significaria que cada vez que um comentário profundo fosse inserido, você teria que reajustar a classificação para cada comentário no tópico. Em threads grandes, isso pode levar muuuuito tempo e geralmente não é uma maneira inteligente de fazer isso.
Eu prefiro uma solução pequena e elegante que se baseie no enchimento de cordas. Para mostrar a você, vou calcular a classificação do comentário ID 6, que é bom e profundo no tópico (3 níveis). Para começar, vamos precisar de um campo na commentstabela chamado “rank”, e vamos torná-lo um tipo TINYTEXT.
Vamos supor que o próprio comentário raiz já tenha sua classificação preenchida. O formato que vamos usar para a classificação desse comentário é:
0000000001Basicamente, estou preenchendo o ID do comentário em até 10 espaços. Você pode aumentá-lo, se quiser – é um preenchimento arbitrário – mas 10 é o suficiente para atender aos requisitos da maioria das pessoas. Também presumiremos que todos os outros comentários têm sua classificação classificada (exceto nosso comentário de ID 6) e devem ser parecidos com:
id rank
1 0000000001
2 0000000001-0000000002
3 0000000001-0000000002-0000000003
4 0000000001-0000000004
5 0000000001-0000000002-0000000005Observe como estamos basicamente mapeando a ancestralidade do nó com a classificação, mas usando o ID auto-incrementado para nosso benefício. Sabemos que um ID inferior significa que ele foi criado anteriormente e queremos exibir comentários anteriores acima dos comentários posteriores, portanto, podemos usar o ID automático para determinar a classificação. (Se você não estiver usando uma identificação automática, pode substituí-la por algum outro campo enumerado e classificável.) Em segundo lugar, estamos separando-os com um travessão. Você pode usar qualquer delimitador que desejar aqui.
Voltar para ID 6. Cada vez que salvamos esse comentário e mudamos seu pai, precisaremos atualizar sua classificação. Para fazer isso, trapacearemos e obteremos a classificação dos pais. Temos isso armazenado na commentstabela e, portanto, em nosso comentário com ID 6, então vamos supor que temos esse ID do pai (que aqui é 3):
SELECT `rank` FROM `comments` WHERE `id` = 3Agora isso vai nos dar isso:
0000000001-0000000002-0000000003E podemos apenas corrigir isso com -0000000006
0000000001-0000000002-0000000003-0000000006E viola! Temos uma classificação para nosso campo. Agora podemos executar nossa consulta anterior para obter um resultado classificado com algumas modificações:
SELECT `id`,`parent`,`rank` FROM `comments` `comment`
JOIN `comments_closure` `closure` ON `comment`.`id` = `closure`.`descendant`
WHERE `closure`.`ancestor` = 2
ORDER BY `rank` ASCE obtenha nosso resultado:
id parent rank
2 1 0000000001-0000000002
3 2 0000000001-0000000002-0000000003
6 3 0000000001-0000000002-0000000003-0000000006
5 2 0000000001-0000000002-0000000003É isso aí! As tabelas de fechamento fornecem uma solução de pesquisa poderosa para árvores grandes, que é usada em uma variedade de aplicativos de conteúdo encadeados. Eles transferem os custos de cálculo e armazenamento para métodos destrutivos (POST / PUT) e permitem que os métodos READ sejam bons e rápidos com sobrecarga mínima. Há muito mais nisso (como paginar corretamente em sub-threads, os métodos de inserção e remoção, recalcular a classificação), mas este tutorial deve ajudá-lo a começar.