Árvores R

Exemplo simples de uma árvore R para retângulos 2D

Árvores R são árvores de estruturas de dados que são similares as árvores B, mas que são usadas para métodos de acesso no espaço com o fim de indexar informação multi-dimensional, por exemplo, as coordenadas (X, Y) de uma posição geográfica. Um exemplo de uso comum das árvores R seria: "Encontre todos os museus que estão até no máximo 1,5 km da minha posição geográfica atual".

A estrutura de dados divide o espaço com aninhamento hierarquico, e possivelmente sobreposição de retangulos de limite mínimos (também chamados de caixas limitantes - bounding boxes).

Cada nodo de uma árvore R tem um número variável de entradas(até um limite máximo pré-definido). Cada entrada dentro de um nodo. que não é folha, armazena dois tipos de dados: uma maneira de identificar um nodo filho, e a caixa limitante de todas as entradas dentro deste nodo filho.

Os algoritmos de inserção e remoção usam caixas limitantes a partir dos nodos para assegurar que todos os elementos próximos estão localizados no mesmo nodo folha (Em particular, um novo elemento será adicionado ao nodo folha que requer o menor aumento espacial na sua caixa limitante). Cada entrada dentro de um nodo folha armazena também dois pedaços de informação: uma maneira de identificar o elemento de dados real(o que, alternadamente, pode ser colocado diretamente no nodo), e a caixa limitante do elemento de dados.

Analogamente, os algoritmos de busca(por exemplo: intersecção, contém, mais próximo) usam caixas limitantes para decidir se irão buscar ou não dentro de um nodo filho. Desta forma, a maioria dos nodos na árvore jamais são alcançados durante uma busca. Como árvores B, isto torna as árvores R mais indicadas para banco de dados, aonde nodos podem ser paginados na memória do computador quando preciso.

Algoritmos diferentes podem ser usados para dividir os nodos quando ele se tornam cheios demais, resultando em subtipos de árvores R: quadricas e lineares.

Árvores R não garantem historicamente boa performance no pior caso, mas geralmente demonstram boa performance na aplicação prática com dados reais. Contudo, um novo algoritmo foi publicado em 2004 que definiu a prioridade de uma árvore R, e que assume ser tão eficiente quanto os mais eficientes métodos atuais e assume-se ter ótima performance nos testes de pior caso.

Ligações externas

• Antonin Gutman, «R-Trees: A Dynamic Index Structure for Spatial Searching» (PDF) , Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84 (Vol. 14, No. 2, pp. 47-57), 1984