B TREE na estrutura de dados: pesquisar, inserir, excluir Operaexemplo de ação

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
  

• 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, a busca de 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.

Pesquisar Operação

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

O seguinte algoritmo é aplicado:

• Deixe a chave (o valor) a ser pesquisada por “k”.
• Comece a pesquisar a partir da raiz e percorra 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.

inserção 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 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.

DICA	O seguinte 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

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.

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.

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.

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.

Apagar Operação

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

O seguinte 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 nas seções a seguir

Se a chave de destino estiver no nó folha

• Target está no nó folha, mais do que chaves mínimas.
• Excluir isso não violará a propriedade da B Tree
• Target está no nó folha, possui nós-chave mínimos
• Excluir isso violará a propriedade da Árvore B
• Target o nó 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
• Target 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.

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.

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

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 diagrama a seguir explica como excluir esta chave:

• 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 exemplo a seguir ilustra como excluir uma chave que precisa de um valor de seu sucessor em ordem.

• 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:

• 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

Apagar OperaPseudocódigo da çã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.