Saltar para o conteúdo

Estruturas de Dados Intermediário/B-Tree

Fonte: Wikiversidade
Exemplo de Árvore B

Á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ó[editar | editar código-fonte]

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 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[editar | editar código-fonte]

Inserção[editar | editar código-fonte]

  1. Primeiro, pesquise a posição onde este nó será incluído. Então, insira o valor dentro do nó.
  2. Se nenhum nó ficou errado, acima ou abaixo da ordem div 2, o processo é terminado.
  3. 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[editar | editar código-fonte]

  1. Primeiro, busque um valor a ser excluído. Então, remova-o de dentro de um nó.
  2. Se nenhum nó teve problema, o processo é terminado.
  3. 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[editar | editar código-fonte]