Acts_as_nested_set, uma árvore turbinada para consulta
No projeto Lucidus ficamos diante de um problema há algumas semanas. Chegamos num ponto do projeto onde muitas coisas haviam sido desenvolvidas em torno de uma chave natural que representava uma conta pertencente a uma árvore de contas contábil. A árvore contábil (ou plano de contas) é uma estrutura hierárquica de 5 níveis.
Uma conta num sistema contábil é um número, que possui uma semantica associada, onde se colocam lançamentos de despesa (gastos com luz, empregados, etc) ou receita (recebimento de aluguél, condomínio, etc).
Simples exemplo de árvore contábil:
- 1 0 00 00 00 - Primeiro nível
- 1 1 00 00 00 - Segundo nível
- 1 1 01 00 00 - Terceiro nível
- 1 1 01 01 00 - Quarto nível
- 1 1 01 01 01 - Quinto nível
- 1 1 01 01 02 - Quinto nível
O problema se desenvolveu pelo fato de estarmos utilizando uma chave natural e uma estrutura com simulação de árvore através da chave natural. Para encontrarmos o pai ou os filhos de uma conta era necessário realizarmos buscas no banco utilizando coisas como “like ‘1101%’”, por exemplo, o que fazia os índices não terem efeito algum. Em algumas situações geramos relatórios consolidados buscando dados dos últimos 12 meses, o que gerava (sem exagero) milhares de queries no banco e cálculos absurdos.
A coisa começou a ficar inviável por 2 motivos: o desempenho não estava satisfatório e a complexidade do código dos nossos modelos estava ficando grande demais, devido a necessidade de simular o efeito de árvore e outros problemas decorrentes.
Tínhamos que resolver o problema, mas qualquer solução que se utilizasse de uma simples árvore iria decair em problema semelhante de desempenho, pela quantidade de queries que teriam que ser realizadas para varrer toda a árvore de contas. Resolvemos ver do que se tratava o acts_as_nested_set do Rails e ele implementava justamente o que precisávamos: uma árvore de busca implementada para um modelo do ActiveRecord! Para inserção de um nó ela é mais lenta que no acts_as_tree, mas na consulta ela pode buscar todos os filhos(e filhos dos filhos e assim por diante) de um nó com apenas uma query.
O acts_as_nested_set ainda não implementava todos os métodos que necessitávamos, como o método level, que informa a qual nível um nó pertence. Então continuando a busca por uma solução encontramos o plugin better_nested_set que faz tudo que o original faz, mas implementando diversos outros métodos utilitários.
Então decidimos resolver o problema de vez e tivemos a coragem de refatorar todo o sistema implementando o better_nested_set na árvore de contas.
Para a teoria de funcionamento dessa árvore, modo de cálculo dos índices e etc, busque nos links citados que encontrará todas as informações. Farei apenas uma pequena explicação sobre como utilizá-la em seu projeto Rails.
Primeiro de tudo, instale o plugin no seu projeto:
script/plugin install svn://rubyforge.org/var/svn/betternestedset/tags/stable/betternestedset
Crie um modelo e uma migração. No projeto exemplo criei um modelo conta:
script/generate model conta
E defini a migração assim:
class CreateContas < ActiveRecord::Migration
def self.up
create_table :contas do |t|
t.string :codigo, :limit => 8, :null => false
t.integer :parent_id
t.integer :lft
t.integer :rgt
t.timestamps
end
end
def self.down
drop_table :contas
end
end
Repare que há um campo parent_id que representará o nó pai e os índices lft e rgt (não use left e right, pois em geral são palavras reservadas nos banco de dados) que são utilizados pela árvore.
O nosso modelo fica assim:
class Conta < ActiveRecord::Base
acts_as_nested_set
end
Agora podemos brincar com nossa árvore! Vamos ao console:
Loading development environment (Rails 2.0.2)
>> Conta.roots
=> []
Nosso modelo dizendo que não há nenhum nó raiz. Vamos criar um:
>> conta1 = Conta.create(:codigo => '10000000')
=> #<Conta id: 1, codigo: "10000000", parent_id: nil, lft: 1, rgt: 2, created_at: "2008-02-01 00:28:58", updated_at: "2008-02-01 00:28:58">
>>
Conta.roots agora retorna nossa recém criada conta:
>> Conta.roots
=> [#<Conta id: 1, codigo: "10000000", parent_id: nil, lft: 1, rgt: 2, created_at: "2008-02-01 00:30:56", updated_at: "2008-02-01 00:30:56">]
>>
Podemos adicionar um filho a ela:
>> conta1.add_child(Conta.create(:codigo => '11000000'))
E consultar os filhos de conta1:
>> conta1.children
=> [#<Conta id: 2, codigo: "11000000", parent_id: 1, lft: 2, rgt: 3, created_at: "2008-02-01 00:33:03", updated_at: "2008-02-01 00:33:03">]
>>
E adicionar um filho a nossa segunda conta:
>> conta2 = Conta.find(2)
=> #<Conta id: 2, codigo: "11000000", parent_id: 1, lft: 2, rgt: 3, created_at: "2008-02-01 00:33:03", updated_at: "2008-02-01 00:33:03">
>> conta2.add_child(Conta.create(:codigo => '11010000'))
=> #<Conta id: 2, codigo: "11000000", parent_id: 1, lft: 2, rgt: 5, created_at: "2008-02-01 00:33:03", updated_at: "2008-02-01 00:33:03">
>>
E assim sucessivamente até termos os 5 níveis contábeis(inseri dois nós no último nível, como no exemplo no início do artigo). Após as inserções fazemos uma busca por todos os filhos do nosso nó raiz:
>> conta1.all_children
=> [#<Conta id: 2, codigo: "11000000", parent_id: 1, lft: 2, rgt: 11, created_at: "2008-02-01 00:33:03", updated_at: "2008-02-01 00:33:03">, #<Conta id: 3, codigo: "11010000", parent_id: 2, lft: 3, rgt: 10, created_at: "2008-02-01 00:35:18", updated_at: "2008-02-01 00:35:18">, #<Conta id: 4, codigo: "11010100", parent_id: 3, lft: 4, rgt: 9, created_at: "2008-02-01 00:37:17", updated_at: "2008-02-01 00:37:17">, #<Conta id: 5, codigo: "11010101", parent_id: 4, lft: 5, rgt: 6, created_at: "2008-02-01 00:37:50", updated_at: "2008-02-01 00:37:50">, #<Conta id: 6, codigo: "11010102", parent_id: 4, lft: 7, rgt: 8, created_at: "2008-02-01 00:40:28", updated_at: "2008-02-01 00:40:28">]
>> conta1.all_children.size
=> 5
>>
E se verificarmos no log, apenas uma sql foi executada para busca de todos os filhos:
Conta Load (0.004532) SELECT * FROM contas WHERE (1 = 1 AND (lft BETWEEN 1 AND 10)) ORDER BY lft
Espero que possa ser útil para alguém! Se precisarem de uma estrutura que se pareça com uma árvore e precise ser otimizada para consulta, não deixe de conferir esse plugin.
Os arquivos desse artigo podem ser baixados aqui:
http://mergulhao.info/assets/2008/8/22/betternestedset.tgz
2 comentários : 01.02.2008 01:10 AM
Atualização - Monografia Rails x Struts
Fiz upload de uma ISO com o conteúdo completo (cd igual ao que foi entregue à banca avaliadora) do que foi desenvolvido no meu trabalho de conclusão de curso. A imagem contém: monografia, slides da apresentação, projeto java+struts, projeto Rails, audio da apresentação.
Confiram na área dos meus artigos.
0 comentários : 29.07.2007 08:44 PM
Artigos
Coloco a disposição aqui alguns dos artigos – acadêmicos ou não – que elaborei ou que participei da elaboração.
Scaling Rails: Redeparede.com servindo 7,5 milhões por mês - Palestra - Junho 2009
Apresentada no FISL 10, Porto Alegre.
Empreendedorismo on Rails - Palestra - Novembro 2008
Palestra gentilmente cedida pelo Vinícius, originalmente apresentada no Rails Summit 2008.
Download apresentação
Download palestra
A palestra possui muitas figuras, para entender melhor o contexto é bom acompanhar os slides lendo a transcrição da palestra.
Utilizando Bluetooth com Ruby - Palestra - Outubro 2008
Apresentado no Latinoware 2008, Foz do Iguaçu.
Participação no Railsbox podcast!
O tema foi licenciamento de softwares livres/open source. Falamos muito sobre software livre e licenças open source, fazendo paralelo com a realidade atual de nós desenvolvedores Rails e nossos projetos.
Rails 2 - Arrumando a Casa - Abril 2008
Rails 2 - Arrumando a Casa
Lucidus: Rails +XP = produtividade
Gnu, Linux e Software Livre: Encaixando as peças do quebra-cabeça - Palestra - Novembro 2007
Palestra apresentada aos funcionários da Drive Consultoria e Informática.
Nos Trilhos com Rails(Versão atualizada) - Palestra Conisli - Novembro 2007
Palestra apresentada no Conisli 2007 em São Paulo.
Montando seu callcenter com thinclients e Software Livre - Palestra - Outubro 2007
Palestra apresentada no V Fórum de Software Livre do Rio de Janeiro.
BlueZone - Programando um disparador de conteúdo por Bluetooth - Secomp - Agosto 2007
Palestra apresentada no Secomp 2007 em Itajubá/MG.
BlueZone - Programando um disparador de conteúdo por Bluetooth - Enecomp - Agosto 2007
Palestra apresentada no XXV Enecomp em Cuiabá/MT.
Aplicações ricas para web com Prototype - Enecomp - Agosto 2007
Curso ministrado no XXV Enecomp em Cuiabá/MT.
Nos Trilhos com Rails - Palestra FISL - Abril 2007
Esta palestra é baseada na minha monografia de conclusão de curso. Faz uma breve apresentação do Ruby e mostra funcionalidades interessantes providas pelo framework Rails.
Monografia de conclusão - Março 2007
Atualização: Disponibilizado agora download completo, que inclui: Monografia, slides da apresentação, projeto java+struts, projeto Rails, audio da apresentação(não é a melhor gravação, mas se consegue ouvir).
Essa foi a monografia desenvolvida para conclusão do curso de Bacharelado em Sistemas de Informação que cursei na UNIRIO — Universidade Federal do Estado do Rio de Janeiro. Trata-se de um comparativo de frameworks para desenvolvimento web. Foram estudados para o comparativo os frameworks Struts e Hibernate, desenvolvidos em Java, e o framework Rails, desenvolvido em Ruby.
No comparativo não foi abordado o desenvolvimento com Struts devido a já existirem outros trabalhos acadêmicos com esse foco. Este trabalho mostra um estudo das funcionalidades que considerei mais relevantes no Rails e faz um paralelo com as equivalentes no Struts.
Para este trabalho foram desenvolvidas duas aplicações de comércio eletrônico idênticas na interface com o usuário e no banco de dados. Em breve disponibilizarei as aplicações também.
Data da defesa: 27 de março de 2007.
Monografia — Monografia em formato pdf
Apresentação monografia — Apresentação da defesa da monografia em formado odp
Download completo — Imagem iso (80MB)
LTSP: Linux Terminal Server Project - Palestra ENECOMP - Agosto 2006
Palestra que expõe os conceitos de funcionamento do projeto LTSP. Foi apresentada no Encontro Nacional dos Estudantes de Computação, organizado pela ENEC e realizado em Poços de Caldas.
Reaproveitamento de Lixo Tecnológico com SL - Palestra - Outubro 2005
Palestra que expõe os conceitos de funcionamento do projeto LTSP e apresenta o caso de sucesso da UNIRIO com sua implantação para quiosques de acesso à internet. Foi apresentada na 3a. Semana de Software Livre do Rio de Janeiro.
Reaproveitamento de Lixo Tecnológico com SL - Ourinhos - Setembro 2005
Palestra que apresenta o caso de sucesso da UNIRIO com a implantação do LTSP em quiosques de acesso à internet. Foi apresentada na 2a. Semana de Software Livre de Ourinhos.
: 05.05.2007 04:47 PM
