TABD – 2011/2012
ÁRVORES R
R*
The R*‐tree: An Efficient and Robust Access Method for Points and Rectangles
g
Susana João – 070316067
João Graça ‐ 080316115
Árvores R*
TABD – 2011/2012
SPATIAL DATABASES
• BD otimizada para armazenar e consultar dados
que estão relacionados com objetos no espaço,
pontos,, linhas e p
polígonos.
g
incluindo p
• Enquanto as BD típicas podem compreender
vários tipos de dados,
dados numéricos e caracteres,
caracteres
nas BD espaciais são precisas funcionalidades
adicionais
di i
i para processar tipos
ti
d dados
de
d d
espaciais.
Árvores R*
TABD – 2011/2012
Funcionalidades Spatial DB
• Distance(geometry, geometry) : number
• Equals(geometry, geometry) : boolean
•Intersects(geometry,
Intersects(geometry, geometry)
geometry) : boolean
: boolean
•Contains(geometry geometry) : boolean
•Contains(geometry, geometry)
: boolean
Árvores R*
TABD – 2011/2012
ALGUNS TIPOS DE SPATIAL DB
• Z‐order – Mapeia pontos multidimensionais numa só dimensão.
ó di
ã
• Quadtree – Todos os nós têm exatamente 4 filhos.
Todos os nós têm exatamente 8 filhos.
• Octree ‐ Todos os nós têm exatamente 8 filhos.
• UB‐tree – Mistura de B+ tree’s e z‐order tree’s.
• R+ tree
R+ tree – Evita sobreposição de nós internos
Evita sobreposição de nós internos
• R‐tree
• R* tree
R*
Árvores R*
TABD – 2011/2012
ÁRVORES R
• São ávores de estruturas de dados que são usadas para Métodos de Acesso Espacial, ou d
é d d
i l
seja, para indexar informação multi‐dimensional (como coordenadas geográficas, retângulos e polígonos)
• Ex. de uso: Encontrar todos os museus que estão até 2 km da minha posição geográfica atual
até 2 km da minha posição geográfica atual
Árvores R*
TABD – 2011/2012
ÁRVORES R
• Cada chave corresponde a uma caixa, ou coleção d i
de intervalos, com um intervalo por dimensão;
l
i
l
di
ã
• Divide o espaço hierarquicamente, sobrepondo retângulos de limite mínimos (minimum bounding rectangle);
(minimum bounding rectangle);
Árvores R*
TABD – 2011/2012
Árvore R
ÁRVORES R
Árvores R*
TABD – 2011/2012
ÁRVORES R
Dificuldades:
construir uma árvore eficiente que
construir uma árvore eficiente que:
• seja equilibrada (os nós folha fiquem na mesma altura);
g
p ç
• os retângulos não cobram muito espaço vazio e não se sobreponham muito (para reduzir o número de subarvores que têm
reduzir o número de subarvores que têm de ser processadas);
Árvores R*
TABD – 2011/2012
ÁRVORES R*
• Variante da Árvore R usada para indexar informação espacial
informação espacial;
• Suporta eficiententemente pontos e dados espaciais ao mesmo tempo 
• O seu custo de implementação é apenas p
ç
p
ligeiramente maior do que a de outras Árvores‐R
Árvores
R 

Árvores R*
TABD – 2011/2012
Árvore R*
Árvore R
ÁRVORES R*
Árvores R*
TABD – 2011/2012
Diferenças entre R* e R
•Principal diferença: R* usa inserções forçadas em vez de splitting;
A minimização da cobertura
minimização da cobertura e da sobreposição
e da sobreposição
•A
é crucial para o desempenho das R‐trees.
•R* otimiza as duas. •R
otimiza as duas
Árvores R*
TABD – 2011/2012
Diferenças entre R* e R
• R* reduz sobreposições (é procurado o retângulo mais favorável à inserção)
Quando um retângulo fica cheio, uma porção
• Quando um retângulo fica cheio, uma porção das entradas são removidas desse retângulo e reinseridas na árvore minimizando as minimum
reinseridas na árvore, minimizando as minimum
bounding boxes
Árvores R*
TABD – 2011/2012
Á
Árvore R
Á
Árvore R*
Árvores R*
TABD – 2011/2012
CRITÉRIOS DE OTIMIZAÇÃO
1.A área coberta por retângulo diretório deve ser minimizada
diretório deve ser minimizada
2.A sobreposição de retângulos 2
A sobreposição de retângulos
diretórios deve ser minimizada
Árvores R*
TABD – 2011/2012
ONDE SE OTIMIZA R R*
• Na escolha da subárvore
•Na divisão de retângulos
•Na inserção e Reinserção de nós
Árvores R*
TABD – 2011/2012
Exemplo
Nó sobrelotado
Divisão R
Árvores R*
Divisão R*
TABD – 2011/2012
CONCLUSÕES
• Reinserções diminuem sobreposições
• Utilização de espaço é melhorado
Devido à restruturação há menos divisões
• Devido à restruturação há menos divisões
• A forma dos retângulos é mais quadrática
• Custos de CPU são ligeiramente maiores devido
Custos de CPU são ligeiramente maiores devido
à inserção
• As queries são muito mais rápidas
á d
Árvores R*
TABD – 2011/2012
OBRIGADO PELA
ATENÇÃO!
Ç

Árvores R*