Estruturas de Dados Intermediário/B-Tree

Árvore B ou B-Tree são estruturas de dados muito utilizadas em banco de dados e sistema de arquivos.

Para inserir ou remover variáveis de um nó, o nó não poderá ultrapassar sua ordem e nem ser menor que sua ordem dividida por dois. Árvores B não precisam ser rebalanceadas como são freqüentemente as árvores de busca binária com Árvore AVL. Árvores B têm vantagens substanciais em relação a outros tipos de implementações quanto ao tempo de acesso e pesquisa aos nós.

O criador das árvores B, Rudolf Bayer, não definiu claramente de onde veio o B das árvores B. Ao que parece, o B vem de balanceamento onde todos os nós da árvore estão em um mesmo nível. Também é possível que o B tenha vindo de seu sobrenome Bayer, ou ainda do nome da empresa onde trabalhava Boeing, no Boeing Scientific Research Labs.

Estrutura do nó

Nós em árvores B, também denominado páginas, geralmente são representados por um conjunto de elementos apontando para seus filhos. Alguns autores consideram a ordem de uma árvore B como sendo a quantidade de registros que a página pode suportar. Outros consideram a ordem como a quantidade de campos apontadores. Todo nó da árvore tem um mínimo de registros definido pela sua ordem, que é a metade da ordem, arredondando-se para baixo, caso a árvore seja de ordem ímpar, exceto a raiz da árvore, que pode ter um mínimo de um registro. Por exemplo, os nós de uma árvore de ordem 5, podem ter, no mínimo $5/2$ registros, ou seja, dois registros. A quantidade de filhos que um nó pode ter é sempre a quantidade de registros do nó mais 1 (V+1). Por exemplo, se um nó tem 4 registros, este nó terá obrigatoriamente 5 apontamentos para os nós filhos.

Algoritmos

Inserção

Primeiro, pesquise a posição onde este nó será incluído. Então, insira o valor dentro do nó.
Se nenhum nó ficou errado, acima ou abaixo da ordem div 2, o processo é terminado.
Se algum nó ficar acima da ordem, dividimos o nó, o valor central do nó dividido sobe para a posição do pai, continuando assim recursivamente por toda a árvore. Se o nó estourar na raiz, então é criado um novo nó raiz (podendo ter um único elemento).

Exclusão

Primeiro, busque um valor a ser excluído. Então, remova-o de dentro de um nó.
Se nenhum nó teve problema, o processo é terminado.
Se algum nó estiver errado, então há duas possibilidades:
1. Se o nó ao lado do nó errado pode transferir um ou mais de seus nós filho ao nó atual, então o nó atual voltará ao normal. Após ter atualizado os valores da separação do pai e dos dois filhos, o processo é terminado.
2. Se o nó ao lado do nó errado não tem um filho extra porque está no limite mais baixo, então ambos os nós serão fundidos em um único nó. Continuando até que o nó atual esteja normal.

Ligações externas