Pesquisa em Arquivos Árvore B

Prévia do material em texto

Pesquisa em Arquivos 
 
Árvore B 
Gilda Aparecida de Assis 
Pesquisa em Arquivos 
 Pesquisa em Árvore B 
 Algoritmo iterativo 
 Carrega uma página do disco para a memória primária e então 
pesquisa dentro da página, até chegar no nível folha 
 A árvore B garante que pelo menos 50% da página (exceção da 
raiz) é utilizada no armazenamento dos dados (chave-referência) 
do arquivo de índices ou do arquivo de dados 
 Todo nodo tem pelo menos m/2 descendentes, exceto raiz e 
folhas 
 Árvore B é balanceada 
 Nos nodos folha estão as referências para os registros do arquivo 
de dados, mas não há referências para esses registros de dados 
nos nodos internos. Isso gera chaves duplicadas nos níveis mais 
altos da árvore. 
 
 
 
 
 
Pesquisa em Arquivos 
 Inserção em Árvore B 
 Inicia com pesquisa que percorre todo o caminho da 
raiz até uma folha 
 Após localizar o nodo folha, o seguinte procedimento 
se repete da folha até a raiz: 
 Detecção de overflow 
 Divisão 
 Inserção 
 Atualizar nodo pai (promover chaves) 
 Se a raiz foi dividida, criar uma nova raiz 
 
 
 
 
 
 
Pesquisa em Arquivos 
 Remoção em Árvore B 
 Garantir que todo nodo terá pelo menos m/2 chaves após a 
remoção, exceto raiz e folhas 
 Situações: 
 Remover chave da folha sem gerar underflow no nodo e sem 
mudar seu maior valor: Apenas remover chave do nodo 
 
 
 
 
 
 
 
 
 
D G I 
A B C D E F G H I 
Remover chave C da árvore D G I 
A B D E F G H I 
Pesquisa em Arquivos 
 Remoção em Árvore B 
 Situações: 
 Remover chave da folha sem gerar underflow no nodo mas 
causando mudança no maior valor: Remover chave da folha 
e atualizar o maior nos níveis anteriores 
 
 
 
 
 
 
 
 
 
N O P 
I P Z 
M P 
Remover chave P 
N O 
I O Z 
M O 
Pesquisa em Arquivos 
 Remoção em Árvore B 
 Situações: 
 Remover chave da folha que gera underflow no nodo: Remover 
chave da folha, inserir chaves restantes no vizinho(merge) e 
remover nodo folha. Níveis superiores devem refletir isso. 
 
 
 
 
 
 
 
 
 
D G I 
A B C D E F G H I 
Remover chave H D I 
A B C D E F G I 
Pesquisa em Arquivos 
 Remoção em Árvore B 
 Situações: 
 Merge pode se propagar até a raiz. Se a raiz fica com somente 
1 chave e 1 filho, ela pode ser eliminada e seu filho se torna a 
nova raiz. 
 
 
 
 
 
 
 
 
 
D 
E F G 
D E F G 
Pesquisa em Arquivos 
 Remoção em Árvore B 
 Situações: 
 Se o nodo i tem exatamente o número mínimo de chaves e 
algum de seus nodos vizinhos tem chaves sobrando, 
redistribua as chaves do vizinho para o nodo i e modifique os 
índices dos níveis superiores para refletir isso. 
 
 
 
 
 
 
 
 
 
E N U Z 
P R S T U V W Z 
Remover W da 
árvore de ordem 5, 
redistribuição das 
chaves entre vizinhos 
(mesmo pai) 
E N T Z 
P R S T U V Z 
Pesquisa em Arquivos 
 Complexidade de busca em Árvore B 
 Ex: 1.000.000 chaves 
 Árvore B de ordem 512 
 No pior caso, qual será o número máximo de acessos 
ao disco para encontrar uma chave? Em outras 
palavras, quão profunda a árvore será? 
 Todas chaves aparecem nas folhas, portanto, são 
1.000.000 chaves nas folhas 
 Pior caso ocorre quando todas as páginas têm o 
número mínimo de descendentes m/2, ou seja, 
largura mínima e altura máxima da árvore 
 
 
 
 
 
Pesquisa em Arquivos 
 Redistribuição em Árvore B 
 Redistribuição pode ser utilizada tanto na remoção 
quanto na inserção de novas chaves 
 
 O uso da redistribuição no lugar da divisão quando 
ocorre overflow na inserção pode tornar a árvore B 
mais eficiente quanto ao uso do espaço, evitando ou 
pelo menos postergando, a criação de novas páginas. 
 Dividir uma página somente quando ambos os 
vizinhos estão cheios 
 
 
 
 
 
 
Pesquisa em Arquivos 
 Complexidade de busca em Árvore B 
 
 
 
 
 
 
 
 
 
• Para árvore B com n chaves nas folhas: n≥ 2xm/2d-1 , ou seja, n/2 ≥ m/2d-1, 
aplicando logaritmo na equação 
• d -1 ≤ log m/2 (n/2), ou seja, d ≤ 1 + log m/2 (n/2), 
• No exemplo d ≤ 1 + log 512/2(1.000.000/2), d ≤ 3.37 
 
• Indexar 1.000.000 de chaves em não mais que 3 seeks é o desempenho 
que precisamos para indexação em arquivo. 
 
 
 
Nível Número mínimo de descendentes 
1 (raiz) 2 
2 2 x m/2 
3 2 x m/2 x m/2 = 2xm/22 
4 2xm/23 
... ... 
d 2xm/2d-1 
Pesquisa em Arquivos 
 Árvore B* 
 Criada por Knuth em 1973, explora a redistribuição na 
inserção e estabelece novas regras para a divisão 
 Redistribuição é utilizada até que o nodo e pelo menos 
um vizinho estejam cheios 
 A divisão é feita partindo dos dois nodos cheios e 
gerando 3 novos nodos 
 Os novos nodos são cada um cerca de 2/3 cheios 
ao invés de 1/2 cheios como ocorre na divisão de 
um nodo apenas 
 
 
 
 
 
 
 
Pesquisa em Arquivos 
 Propriedades da Árvore B* 
 Toda página tem no máximo m descendentes 
 Toda página exceto a raiz tem pelo menos (2m-1)/3 
descendentes 
 A raiz tem pelo menos 2 descendentes, exceto se ela é 
uma folha 
 Todas as folhas estão no mesmo nível 
 
 
 
 
 
 
 
 
Pesquisa em Arquivos 
 Otimização da busca em árvore B ou B* 
 Como reduzir ainda mais os acessos ao disco para recuperar chaves 
de um nodo folha? 
 Manter uma parte do índice na memória principal pode reduzir 
para um acesso ao disco ou menos 
 Criar um buffer de páginas na memória 
 Quando uma nova pesquisa é feita, inicia-se pelas páginas que já 
estão no buffer da RAM 
 Se a página desejada não está na memória, ela é lida do disco 
para o buffer, substituindo uma das páginas do buffer. Como? 
 LRU – Least Recently Used (Menos Recentemente Usada), 
ou seja, a página que sai é a que ficou mais tempo sem 
requisição de uso. 
 Substituição baseada no nível da página : Manter na RAM as 
páginas dos níveis mais altos da árvore