Estudante

MINISTÉRIO DA EDUCAÇÃO
FUNDAÇÃO UNIVERSIDADE FEDERAL DA GRANDE DOURADOS
FACULDADE DE CIÊNCIAS EXATAS E TECNOLOGIAS
BACHARELADO EM SISTEMAS DE INFORMAÇÃO

Trabalho de Estrutura de Dados II

Dourados, 22 de Maio de 2014
1 – Altura, h=f(n,N) – Arvore com ocupação máxima.

2 - Resumo sobre Arvore B+.
As Arvores B+ são uma estrutura de dados, elas são uma variação das Arvores B, elas são a junção de uma arvore B com uma lista duplamente encadeada que liga as páginas folhas. Nesse tipo de arvore todos os registros são armazenados no ultimo nível (páginas folhas), os níveis acima do último nível constituem um índice cuja organização é a organização de uma árvore B. Esses tipo de estrutura são muito usadas em banco de dados, sistemas de arquivos como o NTFS. Elas visam reduzir as operações de leitura e escrita nas memórias secundarias. As chaves são duplicadas em nodos não folhas formando uma espécie de índice, as páginas folhas são ligadas oferecendo um caminho sequencial ordenado para percorrer as chaves. Cada nó folha contém apontadores para quais nós são seus predecessores ou sucessores na sequência de chaves, as chaves são organizadas que tal forma que fiquem ordenadas. Quando tentarmos pesquisar pela chave k e tentarmos encontra a chave k+1(a próxima chave) apenas verificamos se a chave ao lado de k está na mesma página ou passar para próxima página da lista de páginas para verificar qual a próxima chave na sequência. Isso torna uma das principais diferenças da Arvore B+ para a Arvore B, o aumento da eficiência de localização do próximo registro na árvore passa de O(log2N) para O(1).
Nas arvores B+ temos as páginas internas e as páginas folhas, as páginas internas são apenas as referências para a localização das chaves que buscamos, ou seja, elas são apenas o índice, elas são semelhantes a arvores B, ou seja, seu número mínimo de chaves é igual a (n/2)-1 e