Teste

Disponível somente no TrabalhosFeitos
  • Páginas : 12 (2833 palavras )
  • Download(s) : 0
  • Publicado : 8 de novembro de 2012
Ler documento completo
Amostra do texto
| FACULDADE ANHANGUERA EDUCACIONAL LTDACurso: Ciência da Computação - 4º PeríodoDisciplina: Estrutura de DadosProfessor: Rudimar MouraAluno: Jefferson Pereira da Silva - RA: 111276721 |

ÁRVORES
B e B+

Cascavel/PR
2012

SUMÁRIO:

INTRODUCAO 3
ARVORES B 4
DEFINIÇÃO: 4
INSERÇÃO EM UMA ÁRVORE B: 5
BUSCA EM UMA ÁRVORE B: 6
REMOÇÃO EM UMA ÁRVORE B: 6
APLICAÇÕES DE ARVORES B: 7AS PRINCIPAIS VANTAGENS DAS ÁRVORES B: 8
ARVORES B+: 8
CARACTERÍSTICAS: 9
DEFINIÇÃO: 9
INSERÇÃO EM UMA ÁRVORE B+: 9
BUSCA EM UMA ÁRVORE B+: 10
REMOÇÃO EM UMA ÁRVORE B+: 10
APLICAÇÕES EM UMA ÁRVORE B+: 11
CÓDIGO EM C++ BASE PARA COMPREENSÃO DA MANIPULAÇÃO EM ÁRVORE: 11
CONCLUSÃO 13
BIBLIOGRAFIAS: 14

INTRODUCAO

Esta documentação visa dar o embasamento teórico sobreárvores B e B+, descrevendo de forma objetiva os passos necessários à implementação de um banco de dados hipotético estruturado na forma de arvores, suas vantagens e noções básicas do custo das operações envolvidas, tanto em relação ao uso de processador quanto a acessos a disco.

ARVORES B

Árvores-B são árvores balanceadas projetadas para trabalhar com dispositivos de armazenamento secundário comodiscos magnéticos. Elas visam aperfeiçoar as operações de entrada e saída nos discos. O tempo de acesso a informações em um disco é prejudicado principalmente pelo tempo de posicionamento do braço de leitura. Uma vez que o braço esteja posicionado no local correto, a leitura pode ser feita de forma bastante rápida. Desta forma, devemos minimizar o número de acessos ao disco. Diferente das árvoresbinárias, cada nó em uma Árvore-B pode ter muitos filhos, isto é, o grau de um nó pode ser muito grande.

A árvore B é uma estrutura popular para organizar e manter grandes índices. Como as buscas em árvore binária, ela oferece recuperação e performance de atualização muita boas, permitindo processamento sequencial ocasional sem ter que reorganizar os dados. As árvores B estão na categoria deárvores de múltiplos caminhos, aquelas que permitem mais de dois ramos de qualquer nó. O método de acesso sequencial indexado é outra forma de árvore de múltiplos caminhos dos quais cada índice pode ser considerado um nó com um ramo para cada valor de chave (bloco) armazenado no índice.

Definição:

Uma Árvore-B é uma árvore tendo as seguintes propriedades:

1 - Todo nó X possui os seguintescampos
a) n, o número de chaves armazenadas em X
b) as n chaves k1, k2,...kn são armazenadas em ordem não decrescente
c) folha que indica se X é uma folha ou um nó interno.

2 - Se X é um nó interno então ele possui n+1 ponteiros f1, f2,...fn para seus filhos (podendo alguns serem nulos).

3 - Se ki é alguma chave na sub-árvore apontada por fi então k1 < X -> k1 < k2 <k2 < k2<... < X -> kn < Kn+1.

4 - Todas as folhas da árvore estão na mesma altura (que é a altura da árvore);

5 - Existe um número máximo e mínimo de chaves em um nó. Este número pode ser descrito em termos de um inteiro fixo t maior ou igual a dois chamados graus mínimo.

A. Todo nó diferente da raiz deve possuir pelo menos t-1 chaves. Todo nó interno diferente da raiz devepossuir pelo menos t filhos. Se a árvore é não vazia então a raiz deve possui pelo menos uma chave.

B. Todo nó pode conter no máximo 2t-1 chaves. Logo um nó interno pode ter no máximo 2t filhos. Dizemos que um nó é cheio se ele contém 2t-1 chaves.

Arvore B com t=3
De acordo com a definição acima, a Árvore-B mais simples ocorre quando t=2. Neste caso todo nó interno possui 2,3 ou 4 filhos, estetipo de árvore é chamado 2-3-4 árvore.

Obs: Alguns autores utilizam a palavra “ordem” de uma Árvore-B para indicar o número máximo de chaves num nó. Outros autores utilizam a palavra “ordem” para indicar o número máximo de filhos.

Inserção em uma Árvore B:

Para inserirmos um novo elemento em uma Árvore-B, basta localizar o nó folha X onde o novo elemento deva ser inserido. Se o nó X...
tracking img