Estrutura de Dados Espaciais
 Necessidade de indexação dos dados
espaciais de modo a reduzir o tempo de
acesso aos mesmo
 Métodos de indexação tradicionais não são
indicados para dados espaciais


Hash: não atendem a consultas de faixa (reange
queries)
B-Tree: trata apenas uma dimensão
Estrutura de Dados Espaciais
 Operação comum com dados espaciais é a
pesquisa de objetos que estão numa
determinada área

Ex.: Encontre todos os hospitais que estão a no
máximo 20KM deste ponto
Estrutura de Dados Espaciais
 Algumas estruturas de dados propostas:




Grid
quad-trees
k-d-tree
r-tree
R-Tree
 É uma árvore similar a uma B+-tree, com
índices para dados nas folhas
 Nós correspondem à páginas de disco
 A estrutura é projetada de forma que uma
pesquisa espacial requer visitar um número
pequeno de nós
 Um BD espacial consiste de tuplas
representando objetos espaciais, onde cada
tupla possui um identificador
R-Tree
 Nós folhas contêm entradas da forma:




(R, TId)
Onde: R contém o retângulo que encobre a área
da tupla identificada por TId.
Este retângulo é conhecido por Minimum
Bounding Box
Ex.
R-Tree
 Nós não -folhas contêm entradas da forma:


(R, Filho)
Onde R é o retângulo que envolve todos os
retângulos dos descendentes deste nó e Filho é
o endereço do nó filho
R-Tree
 Definição: Sejam M e m o número máximo
e mínimo de entradas de um nó
respectivamente, tal que m <= M/2



Uma R-tree satisfaz às seguintes propriedades:
P1. Cada nó contém entre M e m entradas,
exceto a raiz
P2. Para cada registro de índice (R, TId), R é o
menor retângulo que espacialmente contém os
dados n-dimensionais representados pela tupla
TId
R-Tree
 Definição (cont)




P3. Cada nó tem entre M e m filhos, exceto a
raiz
P4. Para cada entrada (R, filho) num nó não
folha, T é o menor retângulo que espacialmente
contém os retângulos descendentes
P5. O nó raiz tem pelo menos dois filhos a
menos que seja um nó folha
P6. Todas as folhas aparecem num mesmo nível
R-Tree
R-Tree
R-Tree
 Algoritmo de Busca


Inicia-se na raiz de forma similar a uma B-tree
Entretanto, mais de uma sub-árvore pode ser
visitada
R-Tree
 Algoritmo Busca: Dada uma R-tree cujo nó
raiz é T, encontre todos os registros de
índices cujos retângulos sobrepões (overlap)
o retângulo de busca S.

S1: Pesquisa Sub-árvores
• Se T não é folha, verifique cada entrada E para
determinar se E.R sobrepõe S
• Para todas entradas que sobrepõem, chame
Pesquisa(E.Tid)

S2: Se T é folha, verifique todas as entradas E
para determinar se E.R sobrepõe S. Se sim, E é
um registro do resultado.
R-Tree
 Algoritmo Inserção (similar à inserção em
B-tree: inserção nas folhas, nós que ficam
cheios são divididos e divisão se propaga
até a raiz):Inserir uma nova entrada E na Rtree


I1. Encontre a posição para o novo registro :
chamar escolhaFolha() para selecionar o nó
folha L que conterá E
I2. Adicione o registro ao nó folha: Se L tem
espaço coloque E, senão chame divideNo() para
obter L e LL que conterá E mais as entradas de
L
R-Tree
 Algoritmo Inserção


I3. Propagar mudanças para cima: chame
ajusteTree() em L, também passando LL se uma
divisão foi realizada
I4. Árvore cresce: Se uma propogação de
divisão de nó causar a raiz dividir-se, então crie
uma nova raiz cujos filhos são os dois nós
resultantes
R-Tree
 Algoritmo escolhaFolha()




EF1. Inicialize: N = raiz
EF2. Verifique Folhas: Se N é folha, retorne N
EF3. Escolha sub-árvore: Se N não é folha,
Seja F a entrada em N cujo retângulo F.R
precisa do menor crescimento para incluir E.R
(escolhe-se a entrada com retângulo de menor
área)
EF4. Descer até encontrar folha: Faça N ser o
nó filho apontado por F.Tid e volte para EF2.
R-Tree
 Algoritmo ajusteTree()



AT1. Inicialize: N = L. Se L foi dividido faça
NN = LL
AT2. Verifique se já finalizou: Se N é raiz,
então pare.
AT3. Ajuste retângulo na entrada pai: Seja P
o pai do nó N, e seja En a n-ésima entrada em
P. Ajuste En.R de modo que englobe todos os
retângulos em N.
R-Tree
 Algoritmo ajusteTree() (cont)

AT4. Propagar divisão de nós para cima:
• Se N tem um irmão NN resultante de uma divisão
anterior, crie uma nova entrada ENN com
ENN.Tid apontando para NN e ENN.R
englobando todos retângulos de NN.
• Adicione ENN a P se existir espaço
• Caso contrário chame divideNo() para produzir
P e PP contendo ENN e todas as entradas de P

AT5. Mova para cima para o próximo nível
• Faça N=P e NN=PP
• Se uma divisão ocorrer, repita de AT2.
R-Tree
 Algoritmo Remoção(): Remove um
registro E de uma R-tree

R1. Encontre o nó contendo o registro:
• Chame encontreFolha() para localizar o nó folha L
contendo E
• Pare se o registro não foi encontrado



R2. Remova o registro: remova E de L
R3. Propague as mudanças: chame
árvoreDensa(), passando L
R5. Diminua a árvore: se a raiz tem apenas
um filho depois que a árvore foi ajustadam faça
este filho a nova raiz
R-Tree
 Algoritmo encontreFolha():
• Dada uma R-tree cuja raiz é T, encontre a folha
contendo a entrada E

EF1: Pesquise Sub-árvores
• SE T não é folha, verifique cada entrada F em T para
determinar se F.R sobrepõe E.R
• Para cada tal entrada cmae encotreFolha(() na árvore
cuja raiz é apontada por F.Tid até que E seja
encontrado ou todas as entradas tenham sido
checadas

EF2: Pesquise nó folha :
• Se T é folha verifique cada entrada para ver se casa
com E
• Se E não for encontrada, retornar T
R-Tree
 Algoritmo condensaTree
• Dado um nó folha L que tenha tido uma entrada
removida, elimine o nodo se ele tem poucas entradas
e realoque suas entradas
• Propague a eliminação do nó para cima quando
necesário
• Ajuste todos os retângulos no caminho no sentido da
raiz, fazendo-os menores quando possível


CT1. Inicialize: Faça N =L, Seja Q, o conjunto
de nós eliminados inicialmente vazio.
CT2. Encontra a entrada pai
• Se N é raiz, vá para CT6
• Seja P o pai de N, e En a N entrada em P
R-Tree
 Algoritmo condensaTree (cont)

CT3. Elimine nós underflow:
• Se N tem menos que m entradas, remova En de P e
adicione N ao conjunto Q

CT4. Ajuste retângulo
• Se N não foi eliminado, ajuste EN.R para conter
todas as entradas em N.


CT5. Mova para cima um nível: Faça N=P e
repita de CT2
CT6. Re-insira entradas orfãs
• Re-insira toras as entradas de nodos do conjunto Q
R-Tree
 Divisão de Nó



Para adicionar uma nova entrada a um nó cheio
é necessário dividir as entradas em dois nós
A divisão deve ser feita de modo que seja
improvável que ambos nós sejam examinados
em pesquisas subsequentes
Uma vez que a decisão de visitar um nó
depende se seu retângulo sobrepões a área
sendo pesquisada, a área total dos dois
retângulos deve ser minimizada
R-Tree
Veja que a área do Bad Split é muito maior
do que a área de Good Split
Quad trees
 Acelera o acesso a dados num plano 2d
 Técnica bastante simples
 O espaço de busca é recursivamente
decomposto em quadrantes até que o
número de retângulos sobrepondo cada
quadrante é menor do que a capacidade da
página.
 Os quadrante são nomeados: Noroeste,
Nordeste, Sudeste e Sudoeste
Quad trees
 O índice é representado como uma árvore
quaternária (cada nó interno tem 4 filhos,
um por quadrante)
 Cada folha é associada com uma página de
disco
 Cada retângulo aparece em todos os
quadrantes folhas que o sobrepõem
Quad trees
x
1
2
y
5
a
14
8
6 t
z
11
R
12
a
13
3
c
7
4
b
9
10
b
[8,11,12,13]
c
d
[3,4,7] d [9,10,13]
d
x
y
z
t
[1,2,5,6] [5,6,14] [2,3,6] [6]
Quad tree
 Consulta de ponto (point query) é simples
em quad tree.
 Um único path (caminho) é percorrido da
raiz até a folha
 Em cada nível, é escolhido um dos
quadrantes que contém o ponto da consulta
Quad trees
Exemplo de Consulta Ponto P
x
y
a
b
11
1
5
14
2
8
6
z
t
12
P
13
3
c
9
d
7
4
10
R
a
b
[8,11,12,13]
x
y
z
c
d
[3,4,7] d [9,10,13]
t
[1,2,5,6] [5,6,14] [2,3,6] [6]
Quad trees
 Inserção em quadtrees




um retângulo será inserido em cada quadrante
folha que o sobrepõe
então todos os caminhos que para as folhas que
sobrepõem o retângulo a ser inserido são
percoridos
a página P associada com cada folha é lida
Se P não está cheio, então insere o novo
retângulo
Quad trees
 Inserção em quadtrees (cont)



Se P estiver cheio, O quadrante deve ser
dividido em quatro quadrantes e 3 novas
páginas são alocadas
As entradas da página antiga mais a página
nova são divididas nas quatro páginas
Uma entrada E é adicionada a toda página cujo
quadrante intercepta E.MBR (Minimum
Bounding Rectangle)
Quad trees
Inserção em Quadtree
x
1
2
y
5
am
14
p 8
6 t
z
3
n
11
b
15
12 q
13
16
c
7
9
d
10
4
Como ficará a árvore após as inserções de 15 e 16?
k-d tree
 Usado para representar pontos
 árvore kd particiona o espaço em
células
 é uma árvore de busca binária,
 reside em memória principal, tal que os nós
interiores em cada nível contêm valores
referentes a um único eixo, X ou Y,
alternadamente
 as folhas apontam para páginas físicas
 Várias folhas podem apontar para a mesma
k-d tree
 o valor armazenado na raiz divide o espaço
em dois subespaços através de uma reta
perpendicular ao eixo dos X, digamos;
 o valor armazenado no filho à esquerda (ou
direita) por sua vez divide o subespaço à
esquerda (ou direita) em dois subespaços
através de uma reta perpendicular ao eixo
dos Y ; e assim por diante, alternando as
dimensões.
K-D-Tree
K-D-Tree
Árvore para figura anterior
A
B
D
C
K-d Tree
 Outro Exemplo
 Sejam as cidades com coordenadas
Cidade
Mossoró
Natal
Campina Grande
João Pessoa
Monteiro
(X,Y)
(19,45)
(40,50)
(38,38)
(54,40)
(4,4)
K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
K-d Tree
 Inserção de Mossoró
Mossoró (19,45)
 Inserção de Natal
Mossoró (19,45)
Natal (40,50)
K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
K-d Tree
 Inserção de Campina
Mossoró (19,45)
Natal (40,50)
Campina (38,38)
K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
K-d Tree
 Inserção de João Pessoa:
Mossoró (19,45)
Natal (40,50)
Campina(38,38)
JP(54,40)
K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
K-d Tree
 Inserção de Monteiro:
Mossoró (19,45)
Monteiro(4,4)
Natal (40,50)
Campina(38,38)
JP(54,40)
K-d Tree
Natal
Mossoró
João Pessoa
Campina Grande
Monteiro
K-D-Tree
Árvore para figura anterior
A
B
D
C