Aula 6_Arvore B

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Árvores B
Lívia N. Andrade
Árvores B
As árvores B são árvores balanceadas projetadas para trabalhar com dispositivos de armazenamento secundário.
Por exemplo: discos magnéticos. 
Visam otimizar as operações de entrada e saída (escrita/leitura) nos dispositivos. 
Diferente das árvores binárias, cada nó em uma árvore B pode ter muitos filhos, isto é, o grau de um nó pode ser muito grande.
2
Árvores B
Rudolf Bayer, criador das árvores B, não definiu claramente de onde veio o B das árvores B. 
B vem de balanceamento onde todos os nós folhas da árvore estão em um mesmo nível;
B pode ter vindo de seu sobrenome Bayer;
 O nome da empresa onde trabalhava, a Boeing Scientific Research Labs.
3
Árvores B - Um bloco por nó
O acesso a disco é mais eficiente quando o dado é lido ou escrito em um bloco de uma só vez.
Em uma árvore, a entidade que contêm dados é o nó.
Ideal: armazenar um bloco inteiro de dados em cada nó da árvore.
Deste modo, ler um nó acessa um conjunto máximo de dados em um curto espaço de tempo.
4
Árvores B - Características
Dentro de cada nó os dados são ordenados seqüencialmente pela chave, em ordem crescente, da esquerda para a direita;
Uma folha não tem filhos;
Todas as folhas estão no mesmo nível (balanceamento)
5
Árvores B - Características
Em uma árvore B de ordem m:
A raiz (se não for folha) tem no mínimo 1 e no máximo 2m registros;
Cada nó (exceto a raiz e as folhas) tem no mínimo m registros e m + 1 descendentes e no máximo 2m registros e 2m + 1 descendentes;
6
Estrutura do nó
Nós, também chamados de páginas
são representados por um conjunto de elementos apontando para seus filhos (também chamados como folhas); 
typedef struct TipoRegistro {
 long Chave;
 /*outros componentes */
} TipoRegistro;
typedef struct Pagina* TipoApontador;
typedef struct Pagina {
 short n;
 TipoRegistro r [MM] ;
 TipoApontador p[MM + 1] ;
} TipoPagina;
7
Operações em Árvore B
Pesquisa
Inserção
Remoção
8
Ideia básica para a pesquisa...
Indique a chave que será procurada.
Pesquise desde a raiz até encontrá-la, e então retorne o nó e a posição desta.
Se a chave não for encontrada, continue o laço até encontrar um nil das folhas.
9
Pesquisa - pseudocódigo
Primeiro, o bloco contendo a raiz é lido.
O algoritmo de pesquisa então inicia a verificação de cada um dos registros (se ele não estiver cheio, tantos quantos o nó atualmente armazena) iniciando pelo registro 0.
Quando ele encontra um registro com chave maior, ele sabe que deve ir para o filho que reside entre este registro e o precedente.
Este processo continua até o nó correto ser encontrado.
Se uma folha é alcançada sem encontrar a chave específica, a pesquisa não obteve sucesso.
10
Pesquisa – código C
11
Exemplo de Pesquisa
50 
10 30
8
80 100
20
35 40
70
90
102
Ordem = 2
Pesquisar pela chave 20
12
Ideia básica para a inserção
Localizar a página apropriada aonde o registro deve ser inserido.
Se o registro a ser inserido encontra uma página com menos de 2m registros, o processo de inserção fica limitado àquela página.
Se o registro a ser inserido encontra uma página cheia, o processo de inserção provoca a criação de uma nova página (a página cheia será dividida e o elemento central da página cheia será a página pai da nova página). 
13
Exemplo de Inserção
Inserir chave 14 na árvore abaixo
O processo é composto pelas etapas:
1- o registro 14 não existe na árvore, e a página 3 está cheia.
2 - a página 3 é dividida em 2 páginas (página 4 é criada).
14
Exemplo de Inserção
Inserir chave 14 na árvore abaixo
O processo é composto pelas etapas:
1- o registro 14 não existe na árvore, e a página 3 está cheia.
2 - a página 3 é dividida em 2 páginas (página 4 é criada).
15
Exemplo de Inserção
Inserir chave 14 na árvore abaixo
O processo é composto pelas etapas:
1- o registro 14 não existe na árvore, e a página 3 está cheia.
2 - a página 3 é dividida em 2 páginas (página 4 é criada).
3 - os 2m+1 registros são distribuídos igualmente entre as páginas 3 e 4, e o registro do meio (20) é movido para a página pai.
16
Inserção 
Na inserção mostrada anteriormente, a página pai tem de acomodar um novo registro.
E se a página pai estivesse cheia????
O mesmo processo de divisão tem que ser aplicado.
No pior caso, o processo de divisão se propaga até a raiz da árvore, e nesse caso, a árvore aumenta sua altura em um nível.
Importante: a árvore B somente aumenta sua altura com a divisão da raiz.
17
Exemplo de Inserção
Árvore de ordem 1.
Inserir as seguintes chaves:
1, 2, 3, 4, 5, 6 e 7
18
Exemplo de Inserção
Inserir chave 86 na árvore de ordem 2 abaixo
20 35 60 80
70 75
40 50
25 30
10 15
85 90 95 99
19
Exemplo de Inserção
20 35 60 80
70 75
40 50
25 30
10 15
85 90 95 99
20 35
70 75
40 50
25 30
10 15
80 90
60
85 86
95 99
Inserir chave 86 na árvore de ordem 2 abaixo
20
Inserção - pseudocódigo
Primeiro pesquise a chave, para ter a certeza de que esta não existe na árvore.
Depois, busque a posição onde esta será inserida. Teste para ver se o nó está cheio.
Se o nó estiver vazio, insira o valor dentro dele, senão execute uma subdivisão do nó da seguinte forma:
Verifique se o nó-pai está cheio, se não execute:
Passe o elemento do meio do nó para seu pai.
Divida o nó em dois nós iguais.
Se o nó pai estiver cheio, repita as duas linhas acima recursivamente.(Caso todos os nós-pai estiverem cheios, inclusive a raiz, deve ser criada uma nova raiz aumentando assim a altura da árvore.
Somente após satisfazer todas divisões necessárias, insira nova chave.
21
Exercício de Inserção
Inserir as seguintes chaves em um árvore B de ordem 2: 20, 10, 40, 50, 30, 55, 3, 11, 4, 28, 36, 33, 52, 17, 25, 13, 45, 9, 43, 8 e 48
22
Primeiro refinamento do algoritmo Insere
A função Insere chama 
Ins e passa como parametro o registro a ser inserido e *Ap
23
Primeiro refinamento do algoritmo Insere
&Cresceu, &RegRetorno, &ApRetorno 
A função é que vai me retornar estes valores.
24
Primeiro refinamento do algoritmo Insere
Quando apontador nulo é encontrado, significa que o ponto de inserção foi localizado
25
Primeiro refinamento do algoritmo Insere
Cresceu informa que um registro vai ser passado para cima por meio do parâmetro RegRetorno, que será inserido na próxima página que contenha espaço para acomodá-lo.
26
Primeiro refinamento do algoritmo Insere
While está percorrendo o vetor da página
27
Primeiro refinamento do algoritmo Insere
Se tem espaço na página, chama o procedimento InsereNaPagina
28
Procedimento InsereNaPágina
O procedimento vai inserir a nova chave no local correto...
29
Primeiro refinamento do algoritmo Insere
A nova página ApTemp recebe metade dos registros e a outra metade permanece em Ap.
O registro central sobe para a página pai pela RegRetorno.
30
Primeiro refinamento do algoritmo Insere
Se Cresceu = TRUE, significa que a página raiz deve ser criada para acomodar o registro emergente, fazendo com que a árvore cresça na altura.
31
Refinamento final do algoritmo Insere
32
Refinamento final do algoritmo Insere
33
Idéia básica de Exclusão 
Primeiro pesquise a chave para ter a certeza de que esta existe na árvore.
Se existir, verifique se está em folha, e faça a exclusão.
Se existir e não estiver em folha, substitua esta chave, ou pela menor chave do filho a direita, ou pela maior chave do filho a esquerda.
As propriedades de árvore B não devem ser violadas.
50 
10 30
80 100
Árvore de ordem 1
Remover chave 100
50 
10 30
80
34
Exemplo de Exclusão 
20 35 60 80
70 75 79
40 50
25 30
10 15
85 90 95 99
Remover chave 80.
20 35 60 79
70 75 
40 50
25 30
10 15
85 90 95 99
Maior chave do filho a esquerda
35
Exemplo de Exclusão 
20 35 60 80
70 75 79
40 50
25 30
10 15
85 90 95 99
Remover chave 80.
20 35 60 79
70 75 
40 50
25 30
10 15
 85 90 95 99
Menor chave do filho a direita
20 35 60 85
70 75 79 
40 50
25 30
10 15
 90 95 99
36
Importante - Exclusão 
Após a exclusão, as páginas da árvore B continuam atendendo a propriedade dessas árvores?
 As páginas (exceto a raiz) tem que ter no mínino m registros, e no máximo 2m registros.
Se a propriedade da árvore B é violada (página não possui mínimo de m registros):
Se a página vizinha possui mais de m registros, pega-se um registro emprestado da página vizinha. 
Se a página vizinha não possui mais de m registros, as duas páginas devem ser fundidas em uma só.
37
Exemplo de Exclusão 
Árvore de ordem 1. Remover chave 3.
Página vizinha possui mais de m registros:
Pegar um registro emprestado e trazê-lo para a página em questão via página pai.
38
Exemplo de Exclusão 
Árvore de ordem 1. Remover chave 3.
Página vizinha possui exatamente m registros:
As duas páginas tem de ser fundidas em uma só, tomando emprestado da página pai o registro do meio.
39
Exemplo de Exclusão 
Árvore de ordem 1. Remover chave 3.
Página vizinha possui exatamente m registros:
As duas páginas tem de ser fundidas em uma só, tomando emprestado da página pai o registro do meio.
O processo pode propagar-se até a raiz. Se a raiz for reduzido a zero, ela é eliminada, reduzindo a altura da árvore.
40
Exclusão - pseudocódigo
Página com o registro a ser retirado é folha: 
retira-se o registro;
se a página não possui pelo menos m registros, a propriedade da árvore B é violada. Pega-se um registro emprestado da página vizinha. Se não existir registros suficientes na página vizinha, as duas páginas devem ser fundidas em uma só.
Pagina com o registro não é folha:
o registro a ser retirado deve ser primeiramente substituído por um registro contendo uma chave adjacente.
41
Exercício de Exclusão
Remover as seguintes chaves na árvore B de ordem 2 abaixo: 45, 30, 28, 50, 8, 10, 4, 20, 40, 55, 17, 33, 11, 36, 3, 9, 52;
42
Resolvendo o Exercício...
Remover as chaves 45, 30, 28;
43
Resolvendo o Exercício...
Remover as chaves 50, 8, 10, 4, 20, 40, 55, 17, 33, 11, 36;
44
Resolvendo o Exercício...
Remover as chaves 3, 9, 52;
45
Procedimento Retira
{ -- Continua na próxima transparência -- }
46
Procedimento Retira
47
Procedimento Retira
48
Procedimento Retira
{ -- Continua na próxima transparência -- }
49
Procedimento Retira
50
Vantagens das Árvores B
Melhor desempenho por ter um número menor de nós do que uma árvore binária, por exemplo. Menos nós, significa menos altura que resulta em menos acessos ao disco.
Por garantir poucos ponteiros entre os nós, há uma economia de espaço.
Maior rapidez em buscas pela utilização de chaves primárias.
Sua estrutura é dinâmica, ajustando automaticamente o balanceamento da árvore, a cada inclusão/exclusão.
Permite um tempo de acesso de dados menor, em uma busca aleatória, por causa de suas ramificações.
51
Desvantagens das Árvores B
Nó não folha com n chaves, é visitado n vezes, portanto o processo de busca às vezes pode se tornar lento.
As árvores B+ sempre mantém uma cópia de todos os dados nas folhas, o que em caso de necessidade de imprimir toda ela, por exemplo, permite uma rápida busca linear, fazendo com que a Árvore B, em comparação, tenha menor performance.
52
Considerações Finais
Algoritmos de pesquisa são bem simples
Algoritmos de inserção e exclusão podem ser complicados, dependendo da ocasião.
Não se aprende árvores B sem praticar!!!
No link abaixo existe um executável que simula essas operações. Pegue um conjunto de dados e aplique as operações e depois verifique nesse executável se a operação foi feita corretamente.
http://www.ic.unicamp.br/%7Erezende/Astral.htm, 
53
Referências Utilizadas
Livro:
	
ZIVIANI, Nivio, Projeto de algoritmos com implementação em Pascal e C, 3a. edição, Editora Thomson, 2011
Notas de aula da disciplina, disponível no Moodle.
54