Arvore B parte 2

Prévia do material em texto

Pesquisa em Arquivos 
 
Árvore B 
Gilda Aparecida de Assis 
Pesquisa em Arquivos 
 Acesso indexado 
 Arquivo é um conjunto de registros indexados pela chave 
 Acesso sequencial 
 Arquivo pode ser acessado sequencialmente (um seek) em 
ordem pelas chaves 
 Árvore B fornece um excelente acesso indexado para qualquer 
registro, ainda que os registros sejam constantemente 
adicionados e removidos do arquivo. Entretanto, para recuperar 
todos os registros em ordem são necessários um seek randômico 
para cada registro, seguindo a ordem da árvore B. 
 Muitas aplicações requerem tanto acesso indexado a registros 
individuais quanto acesso sequencial para listar os registros na 
ordem da chave (arquivo sequencial indexado). 
 
 
 
 
 
 
 
Pesquisa em Arquivos 
 Como manter o conjunto em sequencia (acesso sequencial)? 
 Deixamos de lado, por enquanto, a parte indexada do acesso ao 
arquivo e focamos no problema de como manter o conjunto de 
registros em ordem física das chaves (conjunto em sequencia) à 
medida que novos registros são adicionados removidos. 
 Alternativa 1: Ordenar e manter todo arquivo ordenado é muito 
cara e está descartada 
 Alternativa 2: Mudanças locais, restringindo o efeito da inserção 
ou remoção a uma parte do conjunto em sequencia (registros 
em ordem). Como? 
 Blocos: Ler um bloco do disco para a RAM, ordenar e 
depois escrever de volta no disco. 
 Ponteiros apontam para o bloco anterior e o próximo. 
 
 
 
 
 
 
Pesquisa em Arquivos 
 Como manter o conjunto em sequencia (registros em ordem)? 
 Inserção de registros em um bloco pode gerar overflow e resultar na divisão 
de blocos (análogo à árvore B sem promoção de chaves) 
 Ex: Máximo de 4 registros por bloco e mínimo de 2 
 
 
 
 
 
 
 
 
 
Inserir CARTER 
Pesquisa em Arquivos 
 Como manter o conjunto em sequencia? 
 Deleção de registros em um bloco pode gerar underflow (menos da 
metade) e resultar no merge ou redistribuição (análogo à árvore B ) 
 
 
 
 
 
 
 
 
 Remover Davis, merge dos blocos 3 e 4 
Pesquisa em Arquivos 
 Custos para manter o conjunto em sequencia 
 Fragmentação interna dentro do bloco aumenta o espaço 
ocupado pelo arquivo quando comparado com um arquivo 
de registros ordenados que não utiliza blocos. 
 Para diminuir a fragmentação: Utilizar na inserção a 
redistribuição ao invés de divisão e divisão de 2-para-
3 ao invés de 1-para-2. 
 
 A ordem dos registros não é fisicamente sequencial entre 
blocos. Apenas dentro do bloco os registros são 
fisicamente sequenciais. 
Pesquisa em Arquivos 
 Tamanho de bloco? 
 Bloco é a unidade básica de operações de I/O e é o 
tamanho máximo garantido de registros fisicamente 
sequenciais 
 Bloco deve conter o maior número de registros possível e 
deve ser possível manter vários blocos na RAM ao mesmo 
tempo 
 Para executar divisão ou merge de blocos, deve ser 
possível manter pelo menos 2 blocos na RAM ao mesmo 
tempo 
 Para realizar divisão de 2-para-3, deve ser possível 
manter pelo menos 3 blocos na RAM ao mesmo tempo. 
Pesquisa em Arquivos 
 Tamanho de bloco? 
 Ainda que se tenha RAM ilimitada, se não houver 
limite superior para tamanho do bloco nós teríamos 
que ler o arquivo inteiro (único bloco) para obter um 
único registro. 
 
 Tamanho do bloco deve ser tal que possamos 
acessá-lo sem o custo de um seek dentro do bloco 
 
 Cluster é um número mínimo de setores fisicamente 
contíguos que são alocados no disco por vez, os 
dados dentro do cluster são acessados sem seeks. 
Ex: cluster de 8 setores. 
Pesquisa em Arquivos 
 Tamanho de bloco? 
 Decidir com base nas seguintes restrições: 
 Tamanho do cluster do disco 
 Quantidade de RAM disponível 
 Número de blocos a manter na memória por vez 
 
 Ex: Tamanho de bloco = trilha do disco 
Pesquisa em Arquivos 
 Acesso indexado no conjunto em sequencia? 
 Como localizar um bloco que contenha o registro 
pesquisado a partir da sua chave, de forma eficiente? 
 
 Conjunto em sequencia pode ser visto como uma 
sequencia de blocos, onde cada bloco contém uma faixa 
de chaves. 
Pesquisa em Arquivos 
 Acesso indexado no conjunto em sequencia? 
 Escolher a maior chave de cada bloco para representar 
o bloco todo no índice 
Chave Bloco 
BERNE 1 
CAGE 2 
DUTTON 3 
EVANS 4 
FOLK 5 
GADIS 6 
Pesquisa em Arquivos 
 Acesso indexado no conjunto em sequencia? 
 Índice simples deve ser mantido na memória. Por 
que? 
 Como é um índice simples, o registro é encontrado através de 
pesquisa binária no índice. Pesquisa binária funciona bem se 
todo o arquivo de índices pode ser carregado pra RAM, mas 
precisa de muitos seeks se a busca é feita no disco. 
 À medida que os blocos no conjunto em sequencia mudam por 
causa de divisão, merge e redistribuição, o arquivo de índices 
também deve ser atualizado. Atualizar o índice funciona bem se 
o índice cabe na RAM. Senão a atualização pode requerer 
seeks em registros individuais no disco (muito caro). 
Pesquisa em Arquivos 
 Acesso indexado no conjunto em sequencia? 
 E se o índice de blocos não couber na memória? 
 Dividir o arquivo de índices em páginas, de forma que 
várias páginas possam ser carregadas pra RAM a 
cada vez. 
 Árvores B são estruturas de dados excelentes para 
manipular índices que não cabem na RAM. 
 
 Árvore B+ = Árvore B + conjunto de blocos em 
sequencia 
Pesquisa em Arquivos 
 O que armazenar no Índice? 
 Separadores ao invés de chaves 
 O índice deve nos guiar para o bloco correto do conjunto em 
sequencia que pode conter a chave, se ela existe. 
 O índice não contém ele mesmo respostas mas somente 
nos diz onde ir para obter essas respostas. Portanto, não é 
necessário ter chaves no índice mas sim separadores 
 Muitos separadores são possíveis mas optamos pelos 
separadores mais curtos. Nem sempre o separador mais 
curto é único. 
Pesquisa em Arquivos 
 Que bloco recuperar do Índice? 
 
 Se chave < separador → bloco da esquerda 
 Se chave == separador → bloco da direita 
 Se chave > separador → bloco da direita 
Pesquisa em Arquivos 
 Árvore B+ pré-fixada simples 
 Conjunto em sequencia (blocos em ordem) 
 Conjunto indexado (separadores de blocos) 
 Pré-fixada indica que o índice contém os prefixos 
(separadores mais curtos) das chaves ao invés de 
cópias das próprias chaves 
 Simples por que os separadores são as letras iniciais 
das chaves 
 Como trata-se de uma árvore B, o número de 
separadores e referências para os filhos têm um 
mínimo e um máximo com exceção da raiz 
 Número de chaves/separadores (n) tem n+1 filhos 
Pesquisa em Arquivos 
 Árvore B+ pré-fixada simples 
 
Pesquisa em Arquivos 
 Mudanças na Árvore B+ pré-fixada simples 
 
 Mudanças dentro dos blocos 
1) Remover registros que não resultem nem em merge 
nem em redistribuição. 
 Desde que o número de blocos no conjunto em 
sequencia não mudou e que nenhum registro foi 
movido entre blocos, o conjunto indexado também 
não muda. 
Excluir EMBRY 
Excluir FOLKS 
FOLKS ainda é 
bom separador 
dos blocos 5 e 6 
Pesquisa em Arquivos 
 Mudanças na Árvore B+ pré-fixada simples 
 
 Mudanças dentro dos blocos 
2) Inserir registros quando há espaço disponível no 
bloco e que não resultem em divisão de blocos 
 
 Desde que o número de blocos no conjunto em 
sequencia não mude e que nenhum registro seja 
movido entre blocos, o conjunto indexado tambémnão muda. 
Inserir EATON 
Pesquisa em Arquivos 
 Mudanças na Árvore B+ pré-fixada simples 
 
 Mudanças envolvendo múltiplos blocos 
 O que acontece se a inserção ou a remoção de registros 
muda o número de blocos no conjunto em sequência? 
 Se temos mais blocos então serão necessários mais 
separadores no conjunto indexado. 
 Se temos menos blocos serão necessários menos 
separadores no índice. 
 As mudanças no índice da árvore B+ pré-fixada 
simples são manipuladas como em uma árvore B de 
memória principal. 
Pesquisa em Arquivos 
 Mudanças na Árvore B+ pré-fixada simples 
 Inserir em nodo cheio: 
 Divisão 
 Criação de um novo nó 
 Distribuição uniforme das chaves nos dois nós 
 Promoção 
 Escolha da maior chave do novo nó como chave 
separadora no nó pai 
 Ajuste do nó pai para apontar para o novo nó 
 Propagação de overflow 
 
Inserir AVERY no bloco 1 gera uma divisão e consequente adição do bloco 7 (metade das 
chaves). O bloco 7 é ligado corretamente no conjunto em sequencia. Para adicionar o 
bloco 7 no índice é necessário novo separador (AY). Ao inserir AY no nodo BO-CAM 
(overflow), ocorre divisão com promoção do maior separador do novo nó (BO) para a raiz. 
Árvore de ordem 
3, máximo de 2 
separadores 
Pesquisa em Arquivos 
 Mudanças na Árvore B+ pré-fixada simples 
 Remoção em nodo gerando underflow e a 
redistribuição não pode ser aplicada 
 Merge para formar novo nodo de: 
 Conteúdo do nó que sofreu underflow 
 Conteúdo de um nó irmão adjacente 
 Chave separadora do nó pai 
 Tratar o underflow no nó pai, caso necessário 
Remover CAEL do bloco 2 gera um underflow e consequente merge dos blocos 2 e 3. Com 
o merge, o bloco 3 não é mais necessário e o separador de 2 e 3 (CAM) deve ser removido 
do índice, gerando underflow no índice que resulta em novo nodo com irmão (AY) e 
separador dos nodos 2 e 3 no pai (BO). 
Árvore de ordem 
3, máximo de 2 
separadores 
Pesquisa em Arquivos 
 Mudanças na Árvore B+ pré-fixada simples 
 Nem sempre as divisões e merge de blocos no 
conjunto em sequencia resultam em ações 
correspondentes no índice. 
 
 As mudanças na árvore B+ ocorrem de baixo para 
cima, ou seja, as inserções e remoções de registros 
sempre ocorrem no conjunto em sequencia pois é lá 
que os registros estão. 
Pesquisa em Arquivos 
 Mudanças na Árvore B+ pré-fixada simples 
 Realizar as divisões, merge e redistribuições necessárias 
nos blocos como se não houvesse o índice. Após, fazer as 
mudanças necessárias no índice. 
 Se blocos são divididos, um novo separador deve ser 
inserido no índice. 
 Se é feito um merge de blocos, um separador deve ser 
removido do índice. 
 Se registros são redistribuídos entre blocos, o 
separador no índice deve mudar. 
 As divisões e merges se propagam até os níveis mais 
altos do índice (árvore) mas isso não ocorre no conjunto 
em sequencia que é uma lista linear, encadeada. 
Pesquisa em Arquivos 
 Nova árvore B+ pré-fixada simples: Carga sequencial 
 Ordenar os registros antes de colocar no conjunto em sequencia 
 Iniciar novo bloco quando o bloco atual estiver cheio 
 
 Determinar o separador mais curto entre o blocos 
 
 Colocar o separador em um nodo do índice mantido na RAM até 
que o nodo esteja cheio. Quando ele estiver cheio, escrever o 
nodo no disco e promover o novo separador (que não coube no 
nodo cheio) para o nodo pai. O nodo pai não deve apontar 
diretamente para os blocos de chaves e sim para os nodos de 
nível mais baixo da árvore. 
 Escrever o nodo do índice no mesmo arquivo após os 
“seus” blocos do conjunto em sequencia (descendentes) 
pode minimizar seeks na busca através da árvore. 
Pesquisa em Arquivos 
 Árvore B+ X Árvore B+ pré-fixada simples 
 Na árvore B+ pré-fixada simples são utilizados prefixos das 
chaves como separadores de blocos nos nodos do índice. 
 
 Na árvore B+ os separadores no índice são simplesmente 
cópias das chaves. 
 Ainda assim, as chaves nos nodos da árvore B+ têm papéis 
diferentes (são apenas separadores) das chaves no 
conjunto em sequencia. 
 Árvores B+ pré-fixada são frequentemente uma alternativa 
melhor que árvores B+ pois permitem colocar mais 
separadores nos nodos do índice que a árvore B+. 
 
 As operações realizadas em árvores B+ são as mesmas 
utilizadas em árvores B+ pré-fixadas. 
Pesquisa em Arquivos 
 Exercício 
 Considere uma árvore B+ pré-fixada simples de ordem 3 
(máximo 2 separadores e mínimo 1 separador) no índice e com 
máximo de 4 e mínimo de 2 registros por bloco no conjunto em 
sequencia. 
 (a) Quais são os separadores do conjunto em sequencia? 
 (b) Desenhe os ponteiros no conjunto. 
 (c) Construa a árvore B+ pré-fixada 
 (d) Insira o registro CAROL e mostre a estrutura resultante