Artigo arvores b

Faculdades Integradas de Caratinga – FIC
Curso de Ciência da Computação – 3º Período
Disciplina: Ordenação e Pesquisa
Professora: Míriam de Souza Monteiro Acadêmicos: Camila F. de Freitas Andrade Lucas Vinicios Azevedo

ÁRVORES B

Introdução
Este estudo tem como objetivo apresentar o funcionamento da árvore B, uma estrutura de dados muito utilizada, pois foi projetada para otimizar o acesso e a manipulação de um número grande de informações armazenadas em memórias secundárias.

Palavras chave: Árvore B. Inicializar. Pesquisar. Inserir. Remover.

1- A Árvore B
O propósito de uma Árvore B é otimizar o acesso e a manipulação da informação armazenada em memórias secundárias. Serve geralmente como estrutura de índice a outros arquivos de registros no qual o índice pode se tornar muito grande para caber na memória.
Segundo Szwarcfiter; Markenzon (1994, p.166) ”[...] utilizando um recurso de manter mais de uma chave em cada nó da estrutura, proporciona uma organização de ponteiros tal que as operações mencionadas são executadas rapidamente”. Uma forte característica das árvores B, é que elas são simétricas, os nós folha sempre estão no mesmo nível. Possuem mais de um elemento (registro) dentro de um mesmo nó (página), fazendo assim com que a altura da árvore seja menor do que a de uma árvore binária, por exemplo, resultando numa quantidade menor de acesso a disco.
Em uma árvore B de ordem m temos que: cada página contém no mínimo m registros (e m + 1 descendentes) e no máximo 2m registros (e 2m + 1 descendentes), exceto a página raiz que pode conter entre 1 e 2m registros; todas as páginas folha aparecem no mesmo nível. (ZIVIANI,1999, p. 170).
Sendo definido o valor 2 para a o ordem(M), a quantidade mínima de registros que cada página deve ter será 2, a quantidade máxima será 4, já a quantidade de apontadores para os filhos variam de 3 a 5.
Com a raiz tendo de 1 a 4 registros e 2 a 5 descendentes.

Figura 1.1: Estrutura de uma