Armazendo árvores em banco de dados

December 17th, 2003 § 4 comments

Um dos problemas mais espinhosos de programação é armazenar estruturas em árvore — ou seja, hierárquicas — em um banco de dados. Exceto quando o banco suporta isso diretamente, providenciando alguma alternativa para resolver a impedância entre o modelo relacional e o modelo hierárquico, implementar esse tipo de coisa é sempre um trabalho complicado, passível de erros e percalços no meio do caminho.

Uma das implementações mais comuns é o modelo de listas adjacentes, ou modelo de pai e filho. Nesse modelo, as inserções e remoções são facilmente implementadas e tem uma performance boa. Por outro lado, retornar a estrutura hierárquica completa da árvore com uma boa eficiência é sempre mais difícil e mais custoso em termos de execução.

De uns tempos para cá, eu comecei a usar um modelo diferente chamado de conjuntos aninhados, que usa um algoritmo conhecido como travessia raiz-esquerda-direita modificada (modified preorder tree traversal). O algoritmo é um modelo um pouco complicado de entender inicialmente, mas a aplicação do mesmo fornece bons benefícios para o problema em questão. A inserção e remoção de dados é mais complicada e mais cara nele do que no modelo de listas adjacentes, mas a visualização dos dados e a operação da árvore de várias formas é também muito mais eficiente e fácil.

Eu já usei o modelo em algumas situações reais nos últimos tempos e os resultados foram muito bons. Além do ganho de velocidade, houve também um bom ganho no tempo de programação. Dado o fato de que estruturas hierárquicas são muito freqüentes na maioria dos sistemas, esse algoritmo compensa o tempo gasto aprendendo. Além do mais, existem também implementações prontas em algumas linguagens de programação mais usados, tornando a questão ainda mais fácil.

§ 4 Responses to Armazendo árvores em banco de dados"

  • SGBD não é bem a minha área, mas achei interessante colocar dois links que podem ser úteis.

    O primeiro é do Roberto Mello e é específico sobre a implementação de ‘nested sets’ (para quem trabalha com PostgreSQL, é interessante passear pelas páginas do site)
    http://www.brasileiro.net/postgres/cookbook/view-recipes.adp?section_id=310&format=long

    O segundo é um patch para o PostgreSQL que implementa o CONNECT BY do Oracle.
    http://gppl.terminal.ru/index.eng.html

  • Ronaldo says:

    O primeiro link é uma cópia do que eu postei, do Joe Celko. Estava distraído? 😛

    O segundo é bem interessante. Pena que só dar para usar se você tiver controle sobre o servidor…

  • Bem, pelo menos a cópia é do Joe Celko mesmo (confesso que não fui no segundo link; como o primeiro era MySQL deduzi erroneamente que o sengundo também era).

    Se tiver o controle do servidor, pode ser utilizado
    http://www.sai.msu.su/~megera/postgres/gist/ltree/ que está na árvore ‘contrib’ do PostgreSQL. Fica mais fácil (pode ser até que já tenha os pacotes compilados na distribuição)

    Mas parece que nenhum dos dois SGBS possuem nativamente as facilidades necessárias para este tipo de problema que nem é tão raro assim. :(

  • Ronaldo says:

    O maior problema que eu vejo com essas extensões é que elas implementam coisas fora padrão. Às vezes, mesmo quando se tem controle do servidor, você quer fazer para ser multi-banco. Nesses casos, fica-se limitado ao que se pode fazer no modelo relacional (e olhe lá).

    Por isso é que eu gostei tanto dessa técnica de conjuntos aninhados. Basta dois campos padrões inteiros e tudo fica mais simples. Pelo menos quando você faz mais OLAP do que OLTP. :-)

What's this?

You are currently reading Armazendo árvores em banco de dados at Superfície Reflexiva.

meta