B TREE na estrutura de dados: exemplo de operação de pesquisa, inserção e exclusão

O que é uma árvore B?

Árvore B é uma estrutura de dados de autoequilíbrio baseada em um conjunto específico de regras para searching, inserindo e excluindo os dados de maneira mais rápida e eficiente em termos de memória. Para conseguir isso, o seguintewing 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 pela primeira vez por McCreight, e Bayer o nomeou Árvore de pesquisa m-way com equilíbrio de altura. Ele ajuda você a preservar os dados classificados e permitir várias operações como inserção, searching e exclusão em menos tempo.

Regras para árvore B

Aqui estão regras importantes para a criação de B_Tree

  • Todas as folhas serão criadas no mesmo nível.
  • A árvore B é determinada por um número de graus, também chamado de “ordem” (especificado por um ator externo, como um programador), conhecido 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 nós filhos que um nó raiz e seus nós filhos podem conter é calculado por esta fórmula:
    m – 1

    Por exemplo:

    m = 4
    max keys: 4 – 1 = 3
    

Regras para árvore B

  • Cada nó, exceto raiz, deve conter chaves mínimas 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 as razões para usar o B-Tree

  • Reduz o número de leituras feitas no disco
  • B As árvores podem ser facilmente otimizadas para ajustar seu tamanho (que é 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 quando se trata de ler e gravar grandes blocos de dados

História da Árvore B

  • Os dados são armazenados no disco em blocos; esses dados, quando trazidos para a memória principal (ou RAM), são chamados de estrutura de dados.
  • No caso de dados enormes, vejaarchicriar um registro no disco requer a leitura de todo o disco; 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 superar isso, são criadas tabelas de índice que salvam a referência dos registros com base nos blocos em que residem. Isso reduz drasticamente o tempo e o consumo de memória.
  • Como temos dados enormes, podemos criar tabelas de índices multiníveis.
  • O índice multinível pode ser projetado usando B Tree para manter os dados classificados de forma autobalanceada.

Operação de Pesquisa

A operação de busca é a operação mais simples na Árvore B.

O seguintewing algoritmo é aplicado:

  • Deixe a chave (o valor) a ser pesquisada por “k”.
  • Comecearching da raiz e percorre recursivamente para baixo.
  • Se k for menor que o valor da raiz, pesquise na subárvore esquerda, se k for maior que o valor da raiz, pesquise 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.

Inserir operação

Como a Árvore B é uma árvore com autoequilíbrio, você não pode forçar a inserção de uma chave em qualquer nó.

O seguintewing 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.
DICA O seguintewing não é verdade sobre o algoritmo de inserção:

Como o nó está cheio, ele será dividido e então um novo valor será inserido

Inserir operação

No exemplo acima:

  • Pesquise a posição apropriada no nó para a chave
  • Insira a chave no nó de destino e verifique as regras
  • Após a inserção, o nó possui um número mínimo de chaves maior que igual a 1? Neste caso, sim, acontece. Verifique a próxima regra.
  • Após a inserção, o nó possui mais do que o número máximo de chaves, que é 3? Neste caso, não, não importa. Isso significa que a Árvore B não está violando nenhuma regra e a inserção está completa.

Inserir operação

No exemplo acima:

  • O nó atingiu o número máximo de chaves
  • O nó será dividido e a chave do meio se tornará o nó raiz dos dois nós restantes.
  • No caso de número par de chaves, o nó do meio será selecionado por polarização para a esquerda ou para a direita.

Inserir operação

No exemplo acima:

  • O nó tem menos do que o máximo de chaves
  • 1 é inserido ao lado de 3, mas a regra de ordem crescente é violada
  • Para corrigir isso, as chaves são classificadas

Da mesma forma, 13 e 2 podem ser inseridos facilmente no nó, pois atendem à regra de chaves inferiores ao máximo para os nós.

Inserir operação

No exemplo acima:

  • O nó possui chaves iguais ao máximo de chaves.
  • A chave é inserida no nó de destino, mas viola a regra do 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.

Inserir operação

Excluir operação

A operação de exclusão possui mais regras do que as operações de inserção e pesquisa.

O seguintewing algoritmo se aplica:

  • Execute a operação de pesquisa e encontre a chave de destino nos nós
  • Três condições aplicadas com base na localização da chave de destino, conforme explicado a seguirwing seções

Se a chave de destino estiver no nó folha

  • O destino está no nó folha, mais do que as chaves mínimas.
  • Excluir isso não violará a propriedade da B Tree
  • O destino está no nó folha, possui nós-chave mínimos
  • Excluir isso violará a propriedade da Árvore B
  • O nó de destino pode pegar emprestada a chave do nó esquerdo imediato ou do nó direito imediato (irmão)
  • O irmão dirá sim se tiver mais do que o número mínimo de chaves
  • A chave será emprestada do nó pai, o valor máximo será transferido para um pai, o valor máximo do nó pai será transferido para o nó de destino e removerá o valor de destino
  • O destino está no nó folha, mas nenhum irmão tem mais do que o número mínimo de chaves
  • Procure por chave
  • Mesclar com irmãos e o mínimo de nós pais
  • O total de chaves agora será superior ao mínimo
  • A chave de destino será substituída pelo mínimo de um nó pai

Se a chave de destino estiver em um nó interno

  • Escolha, antecessor em ordem ou sucessor em ordem
  • No caso do antecessor em ordem, a chave máxima de sua subárvore esquerda será selecionada
  • No caso de sucessor em ordem, a chave mínima de sua subárvore direita será selecionada
  • Se o antecessor em ordem da chave de destino tiver mais do que as chaves mínimas, só então ele poderá substituir a chave de destino pelo máximo do predecessor em ordem
  • Se o antecessor em ordem da chave de destino não tiver mais do que chaves mínimas, 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 de min chaves, então o nó de destino pegará emprestado o valor máximo de seu irmão por meio do pai do irmão.
  • O valor máximo do pai será obtido por um alvo, mas com os nós do valor máximo do irmão.

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

Excluir operação

O diagrama acima exibe diferentes casos de 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 qualquer nó pode ter é 3, e o número máximo de nós filhos que qualquer nó pode ter é 5. Considerando que o número mínimo e máximo de chaves que qualquer nó pode ter são 2 e 4, respectivamente.

Excluir operação

No exemplo acima:

  • O nó de destino possui a chave de destino para excluir
  • O nó de destino possui mais chaves do que as chaves mínimas
  • Simplesmente exclua a chave

Excluir operação

No exemplo acima:

  • O nó de destino possui chaves iguais às chaves mínimas, portanto não é possível excluí-lo diretamente, pois isso violará as condições

Agora, o seguintewing O diagrama explica como excluir esta chave:

Excluir operação

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

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

Excluir operação

  • O nó de destino pegará emprestada uma chave do irmão imediato, neste caso, o sucessor em ordem (irmão direito) porque seu antecessor 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 irmão que possa fornecer sua chave ao nó de destino. Portanto, a fusão é necessária.

Veja o procedimento para excluir tal chave:

Excluir operação

  • Mesclar o nó de destino com qualquer um de seus irmãos imediatos junto com a chave pai
  • A chave do nó pai é selecionada para que os irmãos entre os dois nós mesclados
  • Exclua a chave de destino do nó mesclado

Excluir pseudocódigo da operação

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.

Resumo

  • B Tree é uma estrutura de dados com autoequilíbrio para melhor pesquisa, inserção e exclusão de dados do disco.
  • A árvore B é regulada pelo grau especificado
  • B As chaves e os nós da árvore são organizados em ordem crescente.
  • A operação de busca da Árvore B é a mais simples, que sempre parte da raiz e começa a verificar se a chave alvo é maior ou menor que o valor do nó.
  • A operação de inserção da Árvore B é bastante detalhada, que primeiro encontra uma posição apropriada de inserção para a chave de destino, insere-a, avalia a validade da Árvore B em relação a diferentes casos e, em seguida, reestrutura os nós da Árvore B de acordo.
  • A operação de exclusão da Árvore B primeiro procura a chave de destino a ser excluída, exclui-a e avalia a validade com base em vários casos, como chaves mínimas e máximas do nó de destino, irmãos e pai.