trabalho

Árvore B

As árvores B são árvores balanceadas projetadas para trabalhar com dispositivos de armazenamento secundário, como discos magnéticos. Elas visam a aperfeiçoar as operações de entrada e saída nos dispositivos. O tempo de acesso às 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. Dessa forma, deve-se minimizar o número de acessos ao disco.

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.

Definição: Uma árvore B possui as seguintes propriedades:
1. Todo o nó N possui os seguintes campos:
a. n, o número de chaves armazenadas em X;
b. as n chaves k1, k2...kn são armazenadas em ordem crescente;
c. folha, que indica se X é uma folha ou um nó interno.
2. Se X é um nó interno então ele possui n+1 referências f1, f2...fn+1 para seus filhos (podendo alguns serem nulos);
3. Se ki é alguma chave na sub-árvore apontada por fi, então, k1 ≤ X  k1 ≤ k2 ≤ X  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 2 chamado grau mínimo.
a. Todo o nó diferente da raiz deve possuir pelo menos t-1 chaves. Todo o nó interno diferente da raiz deve possuir pelo menos t filhos. Se a árvore não é vazia, então a raiz possui pelo menos uma chave.
b. Todo o nó pode conter no máximo 2t - 1 chaves. Logo, um nó interno pode ter no máximo 2t filhos. Diz-se que um nó é cheio se ele contém 2t - 1 chaves.

const t = 2;

typedef struct no_arvoreB arvoreB;

struct no_arvoreB { int num_chaves; int chaves[2*t-1]; arvoreB *filhos[2*t]; bool folha;
};

De acordo com a definição acima a árvore B mais simples ocorre quando