Arvores B B tree

Arvores B (B-tree)
Na ciência da computação uma árvore B é uma estrutura de dados projetada para funcionar especialmente em memória secundária como um disco magnético ou outros dispositivos de armazenamento secundário. Dentre suas propriedades ela permite a inserção, remoção e busca de chaves numa complexidade de tempo logarítmica e, por esse motivo, é muito empregada em aplicações que necessitam manipular grandes quantidades de informação tais como um banco de dados ou um sistema de arquivos.
Se analisarmos as árvores B, elas são uma generalização das árvores binária de busca, pois cada nó de uma árvore binária armazena uma única chave de busca, enquanto as árvores B armazenam um número maior do que um de chaves de busca em cada nó, ou no termo mais usual para essa árvore, em cada página. Como a idéia principal das árvores B é trabalhar com dispositivos de memória secundária, quanto menos acessos a disco a estrutura de dados proporcionar, melhor será o desempenho do sistema na operação de busca sobre os dados manipulados.
B-Trees generalizam árvores de pesquisa binária de uma melhor maneira. Se um nodo x de uma B-Tree contém n[x] elementos, então x tem n[x]+1 filhos. Os elementos em um nodo x são usados como pontos de divisão separando a área dos elementos manuseados por x em n[x] + 1 sub-áreas, cada manuseio por um filho de x. Quando procuramos por um elemento em uma B-Tree, nós fazemos em (n[x] + 1) modos de decisão baseados em comparações com n[x] elementos armazenados no nodo x.

Estrutura da página
Uma possível estrutura de dados para uma página de árvore B na linguagem C:
#define D 5 //árvore de ordem 5 typedef struct BTPage{ //armazena numero de chaves na pagina short int totalChaves; //vetor de chaves int chaves[D-1]; //Ponteiros das paginas filhas, -1 aponta para NULL struct BTPage filha[D]; }Page;
Busca
A busca de uma chave k em uma árvore B é muito parecido com uma busca em árvore binária, porém, agora a cada