Informatica

Árvore B ou B – Tree
S
30 de setembro de 2011
Resumo:
Este trabalho irá retratar a criação das árvores B ou B-Tree criadas para otimizar o acesso ao armazenamento da memória secundária.
Palavras chaves: Árvore B, inserção, busca e remoção.
Abstract:

1 Conceitos Básicos A árvore B ou B-Tree é um tipo de estrutura de dados hierárquica muito conhecida e muito utilizada em sistemas de bancos de dados e sistemas de arquivos. Ela foi definida pelo pesquisador Rudolf Bayer. (1971). Esta criação foi motivada devido ao fato das memórias secundárias, utilizarem o acesso aos dados e gerarem altos custos. Conforme podemos verificar a uma grande distância entre o tempo de leitura das memórias secundárias para as memórias principais, podendo esta diferencia chegar a 104 a 105 relacionamentos entre elas. Pensando em agilizar o número de acessos à memória secundária, Rudolf Bayer criou este novo conceito, quando aumentou o número de valores e de filhos que um nós de sua árvore poderiam armazenar. Essa nova organização foi batizada com o nome de Árvore B. A construção da árvore B assegura que as folhas se encontrem todas em um mesmo nível, não importando a ordem de entrada dos dados. As árvores B são largamente utilizadas como forma de armazenamento em memória secundária. Diversos sistemas comerciais de bancos de dados, por exemplo, as empregam. Uma árvore B de ordem D (sendo este D um número natural) é uma árvore ordenada que vazia necessita satisfaz as opções:
- a raiz é uma folha ou tem no mínimo dois filhos;
- cada nó diferente da raiz e das folhas possui no mínimo D + 1 filho;
- cada nó tem no máximo 2 d + 1 filhos;
Chamamos o nó da árvore de página. Cada página armazena então diversos nós da tabela original. Neste caso mencionado, a estrutura apresentada satisfaz ainda as propriedades: a) Cada página possui entre d e 2 d chaves, exceto o nó raiz que possui entre 1 e 2d chaves. b) Seja m o número de chaves em uma página P não folha. Então P