Indexação de Arquivos
Memória × Disco
• Acesso a qualquer parte da memória leva
o mesmo tempo
– (Ignorando fatores como localidade de
referência e ‘cache’)
• Disco: Acesso seqüencial é mais rápido
que acesso randômico
– Características mecânicas dos dispositivos
• Mover as cabeças de leitura e gravação é mais
lento que o movimento de rotação
• Acesso a blocos do mesmo cilindro é rápido
Um dispositivo de disco típico
Estruturas de dados para discos
• Uso de ponteiros deve ser minimizado
• Acesso seqüencial é incentivado
• Se é necessário acessar o disco, então
uma boa quantidade de dados deve ser
lida ou escrita “pra não desperdiçar a
viagem”
– Acesso é feito em “blocos” de tamanho
constante
Árvores de Busca n-árias
• Podemos ver que as árvores binárias de
busca não são adequadas para serem
usadas em disco (ponteiros demais!)
• Uma solução é admitir mais de uma chave
por nó
C1 C2 C3 ... Cn
< C1
≥ Cn
≥ C1
< C2
≥ C2
< C3
≥ Cn-1
< Cn
Árvores de busca n-árias balanceadas
• Idealmente, gostaríamos de empregar
árvores de busca n-árias balanceadas
– Cada nó deveria ser mantido cheio (para não
desperdiçar operações de leitura)
– O tempo de busca a uma chave deveria ser
logarítmico, isto é, O (log N)
• Uma estrutura de dados que tem essas
qualidades é a B-tree, que nada mais é do
que uma ABB n-ária à qual se impõe
critérios adicionais
Características das B-trees (Árvores-B)
• Cada nó, exceto o nó raiz, tem entre n/2 e n
chaves
– O nó raiz pode ter apenas 1 chave (ou nenhuma, se a
árvore estiver vazia)
• Cada nó é da forma P0C1P1C2P2…CkPk, onde Pi é
– Um ponteiro para outro nó da árvore contendo apenas
chaves cujos valores são maiores ou iguais a Ci e
menores que Ci –1 [se o nó é interno] ou
– Um ponteiro nulo [se o nó é folha]
Busca em B-trees
•
Algoritmo análogo ao usado em árvores de
busca. Seja X o valor buscado
1. Nó raiz é lido
2. Faz-se uma busca binária nas k chaves do nó.
2.1 . Se X for encontrado, o algoritmo termina retornando
Verdadeiro
2.2. Senão, X corresponde ao intervalo de algum Pi .
2.2.1 Se Pi é nulo, o algoritmo termina retornando Falso
2.2.2 Senão, o nó apontado por Pi é lido e retorna-se ao
passo 2
Busca em B-trees - Exemplo
X = 18
13
4 8
1 2
5 7
17 20
9 12
15 16
18 19
21 22
Inserção em B-trees
• Buscar o nó folha onde o valor X deve ser
inserido
• Se o nó ainda tem lugar, algoritmo termina
• Senão, dividir as n+1 chaves em três grupos: [1]
as n/2 menores chaves, [2] a chave mediana e
[3] as n/2 maiores chaves
• O grupo [1] permanece no nó folha e o grupo [3]
vai formar um novo nó folha
• A chave mediana, é inserida (recursivamente se
necessário) no nó pai
– Se não existe nó pai, uma nova raiz é criada
Inserção em B-trees
N=4
3 17 19 18 21 22 20
Ordem de Inserção: 8 5 15 12 7 16 13 9 1 2 3`
13
8 4 8 8 134 84 13
8 13 17
17 20
1 21 21 2 55
87
888512
15
7 15
5 7 5 79
12
912
12
13
15159 16
12 915
1215
16 16 15 1618151916 17 18
1921
19 22
21 22
Remoção em B-trees
• O algoritmo de exclusão de uma chave é
um pouco mais complexo do que o de
inserção
• Há vários casos a serem considerados:
– Nó que contém a chave é folha ou interno?
– Há risco de “underflow” (nó fica com chaves
de menos) ou não?
Remoção em B-trees
• Se a chave está num nó folha
– Se o nó não corre risco de underflow, a chave
é removida e o algoritmo termina
– Senão, 2 situações são possíveis:
• O nó vizinho à esquerda ou à direita têm uma
chave para emprestar, isto é, não correm o risco
de underflow. Neste caso fazer operação de
empréstimo
• Ambos os vizinhos têm o número mínimo de
chaves. Neste caso fazer a operação dee
combinação do nó com um de seus vizinhos
Operação de Empréstimo
Remoção da chave 7
13
4 8
9
1 2
5 7
8
17 20
9 10
10
1212
15 16
18 19
21 22
Operação de Combinação
Remoção da chave 7
Solução
Pode
ocasionar
é vista
nóseguir
a
interno
com underflow
13
?
4 8
1 2
5 7
5 8 10
1012
12
17 20
15 16
18 19
21 22
Remoção em B-trees
• Se a chave está num nó interno
– Se é possível fazer uma operação de empréstimo
entre os nós filhos à esquerda e à direita, então fazêla e remover a chave do filho que a recebeu
13
4 8
9
1 2
5 7 8
17 20
9
1010
1212
15 16
18 19
21 22
Remoção em B-trees
• Se a chave está num nó interno e não é
possível fazer uma operação de
empréstimo entre os nós filhos à esquerda
e à direita,
– Combine-os (junto com a chave) e remova a
recursivamente a chave do nó filho resultante
– Se o nó interno resultante estiver com
underflow, aplicar um empréstimo com um nó
vizinho se possível, ou então uma
combinação
Exemplo de Remoção
13
4 8
1 2
5 7
5577 8101012
12
12
4 13 17 20 17 20
15 16
18 19
21 22