Árvore B em Estrutura de Dados: Busca, Inserção, Exclusão

O que é uma árvore B?

Árvore B Uma árvore B é uma estrutura de dados auto-balanceada baseada em um conjunto específico de regras para buscar, inserir e excluir dados de forma mais rápida e eficiente em termos de memória. Para alcançar esse objetivo, as seguintes regras são seguidas para criar uma árvore B.

Uma árvore B é um tipo especial de árvore em uma estrutura de dados. Em 1972, esse método foi introduzido por McCreight e Bayer, que o denominaram Árvore de Busca m-way Balanceada por Altura. Ela ajuda a manter os dados ordenados e permite diversas operações, como inserção, busca e exclusão, em menos tempo.

Regras para árvore B

Aqui estão algumas regras importantes para criar uma árvore B:

• Todas as folhas serão criadas no mesmo nível.
• Uma árvore B é determinada por um número de graus, também chamado de "ordem" (especificado por um agente externo, como um programador), referido como m em diante. O valor de m depende do tamanho do bloco no disco no qual os dados estão localizados principalmente.
• A subárvore esquerda do nó terá valores menores que o lado direito da subárvore. Isso significa que os nós também são classificados em ordem crescente, da esquerda para a direita.
• O número máximo de chaves que um nó raiz, bem como seus nós filhos, podem conter é calculado por esta fórmula: m − 1. Por exemplo:

  m = 4
  max keys: 4 − 1 = 3

• Cada nó, exceto a raiz, deve conter um número mínimo de chaves de [m/2] − 1. Por exemplo:

  m = 4
  min keys: 4/2 − 1 = 1

• O número máximo de nós filhos que um nó pode ter é igual ao seu grau, que é m.
• O mínimo de filhos que um nó pode ter é metade da ordem, que é m/2 (é considerado o valor máximo).
• Todas as chaves em um nó são classificadas em ordem crescente.

Por que usar B-Tree

Aqui estão alguns motivos para usar uma árvore B:

• Reduz o número de leituras realizadas no disco.
• As árvores B podem ser facilmente otimizadas para ajustar seu tamanho (isto é, o número de nós filhos) de acordo com o tamanho do disco.
• É uma técnica especialmente projetada para lidar com uma grande quantidade de dados.
• É um algoritmo útil para bancos de dados e sistemas de arquivos.
• Uma boa opção para leitura e gravação de grandes blocos de dados.

História da Árvore B

• Os dados são armazenados no disco em blocos. Esses dados, quando carregados na memória principal (ou RAM), são chamados de estrutura de dados.
• No caso de grandes volumes de dados, a busca por um único registro no disco exige a leitura do disco inteiro; isso aumenta o tempo e o consumo de memória principal devido à alta frequência de acesso ao disco e ao tamanho dos dados.
• Para contornar esse problema, são criadas tabelas de índice que armazenam a referência dos registros com base nos blocos em que eles residem. Isso reduz drasticamente o tempo e o consumo de memória.
• Como temos dados enormes, podemos criar tabelas de índices multiníveis.
• Um índice multinível pode ser projetado usando uma árvore B para manter os dados.ping Os dados foram classificados de forma autoequilibrada.

Pesquisar Operação

A operação de busca é a operação mais simples em uma árvore B. O seguinte algoritmo é aplicado:

• Seja “k” a chave (o valor) a ser pesquisada.
• Comece a pesquisar a partir da raiz e percorra recursivamente para baixo.
• Se k for menor que o valor da raiz, procure na subárvore esquerda; se k for maior que o valor da raiz, procure na subárvore direita.
• Se o nó tiver o k encontrado, simplesmente retorne o nó.
• Se k não for encontrado no nó, vá até o filho com uma chave maior.
• Se k não for encontrado na árvore, retornamos NULL.

inserção Operação

Como uma árvore B é uma árvore auto-balanceada, você não pode forçar a inserção de uma chave em qualquer nó. O seguinte algoritmo se aplica:

• Execute a operação de pesquisa e encontre o local de inserção apropriado.
• Insira a nova chave no local apropriado, mas se o nó já tiver um número máximo de chaves:
• O nó, junto com uma chave recém-inserida, será dividido do elemento intermediário.
• O elemento do meio se tornará o pai dos outros dois nós filhos.
• Os nós devem reorganizar as chaves em ordem crescente.

No exemplo acima:

• Procure a posição apropriada no nó para encontrar a chave.
• Insira a chave no nó de destino e verifique as regras.
• Após a inserção, o nó possui um número de chaves igual ou superior ao mínimo, que é 1? Nesse caso, sim. Verifique a próxima regra.
• Após a inserção, o nó possui mais chaves do que o número máximo permitido, que é 3? Neste caso, não. Isso significa que a árvore B não viola nenhuma regra e a inserção foi concluída com sucesso.

No exemplo acima:

• O nó atingiu o número máximo de chaves.
• O nó se dividirá e a chave do meio se tornará o nó raiz dos outros dois nós.
• Caso haja um número par de chaves, o nó do meio será selecionado com base na preferência pela esquerda ou pela direita.

No exemplo acima:

• O nó possui menos chaves do que o número máximo permitido.
• O número 1 é inserido ao lado do 3, mas a regra da ordem crescente é violada.
• Para corrigir isso, as chaves são ordenadas.

Da mesma forma, 13 e 2 podem ser inseridos facilmente no nó, pois atendem à regra de "número menor de chaves" para os nós.

No exemplo acima:

• O nó possui chaves iguais ao máximo de chaves.
• A chave é inserida no nó de destino, mas viola a regra de número máximo de chaves.
• O nó de destino é dividido e a chave do meio por tendência à esquerda é agora o pai dos novos nós filhos.
• Os novos nós são organizados em ordem crescente.

Da mesma forma, com base nas regras e casos acima, o restante dos valores pode ser facilmente inserido na Árvore B.

Apagar Operação

A operação de exclusão possui mais regras do que as operações de inserção e busca. O seguinte algoritmo se aplica:

• Execute a operação de busca e encontre a chave alvo nos nós.
• Três condições são aplicadas com base na localização da chave alvo, conforme explicado nas seções seguintes.

Se a chave de destino estiver no nó folha

• Target Está no nó folha, com mais de min keys (chaves). Excluir isso não violará a propriedade da Árvore B.
• Target Está no nó folha e possui o número mínimo de nós-chave. Excluir isso violará a propriedade da Árvore B.
• O nó de destino pode obter uma chave emprestada do nó imediatamente à esquerda ou do nó imediatamente à direita (nó irmão).
• O irmão dirá sim se tiver mais chaves do que o número mínimo exigido.
• A chave será emprestada do nó pai, o valor máximo será transferido para o pai, o valor máximo do nó pai será transferido para o nó de destino e o valor de destino será removido.
• Target Está no nó folha, mas nenhum dos irmãos tem mais do que o número mínimo de chaves: procure a chave, mescle com os irmãos e com o mínimo de nós pais, o total de chaves agora será maior que o mínimo, e a chave alvo será substituída pelo mínimo de um nó pai.

Se a chave de destino estiver em um nó interno

• Você pode escolher um predecessor em ordem ou um sucessor em ordem.
• No caso de um predecessor em ordem, a chave máxima de sua subárvore esquerda será selecionada.
• No caso de um sucessor em ordem, a chave mínima de sua subárvore direita será selecionada.
• Se o predecessor em ordem da chave de destino tiver mais chaves do que o mínimo exigido, somente então a chave de destino poderá ser substituída pelo maior dos predecessores em ordem.
• Se o predecessor em ordem da chave de destino não tiver mais do que o número mínimo de chaves, procure a chave mínima do sucessor em ordem.
• Se o antecessor e o sucessor em ordem da chave de destino tiverem menos que min chaves, então mescle o antecessor e o sucessor.

Se a chave de destino estiver em um nó raiz

• Substitua pelo elemento máximo da subárvore predecessora em ordem.
• Se, após a exclusão, o destino tiver menos chaves do que o número mínimo, o nó de destino obterá o valor máximo de seu irmão por meio do pai deste.
• O valor máximo do elemento pai será considerado pelo elemento alvo, mas juntamente com os nós de valor máximo do elemento irmão.

Agora, vamos entender a operação de exclusão com um exemplo.

O diagrama acima exibe diferentes casos da operação de exclusão em uma árvore B. Esta árvore B é de ordem 5, o que significa que o número mínimo de nós filhos que um nó pode ter é 3 e o número máximo é 5. Já o número mínimo e máximo de chaves que um nó pode ter são 2 e 4, respectivamente.

No exemplo acima:

• O nó de destino possui a chave que deseja excluir.
• O nó de destino possui mais chaves do que o número mínimo de chaves.
• Basta apagar a chave.

No exemplo acima:

• O nó de destino possui chaves iguais às chaves mínimas, portanto não podemos excluí-lo diretamente, pois isso violaria as condições.

Agora, o diagrama a seguir explica como excluir esta chave:

• O nó de destino irá tomar emprestada uma chave de um irmão imediato, neste caso, o predecessor em ordem (irmão esquerdo), porque não possui nenhum sucessor em ordem (irmão direito).
• O valor máximo do predecessor em ordem será transferido para o nó pai, e o nó pai transferirá o valor máximo para o nó de destino (veja o diagrama abaixo).

O exemplo a seguir ilustra como excluir uma chave que precisa de um valor de seu sucessor em ordem.

• O nó de destino irá tomar emprestada uma chave de um irmão imediato, neste caso, o sucessor em ordem (irmão direito), porque seu predecessor em ordem (irmão esquerdo) possui chaves iguais às chaves mínimas.
• O valor mínimo do sucessor em ordem será transferido para o pai, e o pai transferirá o valor máximo para o nó de destino.

No exemplo abaixo, o nó de destino não possui nenhum nó irmão que possa fornecer sua chave para ele. Portanto, é necessário realizar uma mesclagem. Veja o procedimento para excluir essa chave:

• Mescle o nó de destino com qualquer um de seus irmãos imediatos, juntamente com a chave pai.
• A chave do nó pai que se encontra entre os dois nós de fusão é selecionada.
• Exclua a chave de destino do nó mesclado.

Apagar Operação Pseudo Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Saída: O maior elemento é excluído da árvore B.

Perguntas Frequentes