O que é uma árvore B?
A Árvore B é uma estrutura de dados com autobalanceamento baseada em um conjunto específico de regras para pesquisar, inserir e excluir os dados de maneira mais rápida e eficiente em termos de memória. Para isso, as seguintes regras são seguidas para criar uma Árvore B.
Uma B-Tree é um tipo especial de árvore em uma estrutura de dados. Em 1972, esse método foi introduzido pela primeira vez por McCreight, e a Bayer o nomeou Árvore de busca m-way balanceada de altura. Ele ajuda você a preservar os dados classificados e permitir várias operações como inserção, pesquisa e exclusão em menos tempo.
Neste tutorial B-Tree, você aprenderá:
- O que é uma árvore B?
- Por que usar B-Tree
- História da Árvore B
- Operação de Pesquisa
- Operação de Inserção
- Excluir operação
Regras para B-Tree
Aqui, estão regras importantes para a criação de B_Tree
- Todas as folhas serão criadas no mesmo nível.
- B-Tree é determinada por um número de graus, que também é chamado de "ordem" (especificada por um ator externo, como um programador), conhecido como
m
em diante. O valor dem
depende do tamanho do bloco no disco no qual os dados estão localizados principalmente. - A subárvore esquerda do nó terá valores menores do 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, um nó raiz, bem como seus nós filhos podem conter são calculados por esta fórmula:
m - 1
Por exemplo:m = 4max keys: 4 - 1 = 3
- Cada nó, exceto raiz, deve conter chaves mínimas de
[m/2]-1
Por exemplo:m = 4min 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 é a metade da ordem, que é m / 2 (o valor do teto é considerado).
- 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 B-Tree
- Reduz o número de leituras feitas no disco
- Árvores B podem ser facilmente otimizadas para ajustar seu tamanho (ou seja, 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 muito grandes, pesquisar 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 de registro dos registros com base nos blocos em que residem. Isso reduz drasticamente o tempo e o consumo de memória.
- Como temos muitos dados, podemos criar tabelas de índice de vários níveis.
- O índice multinível pode ser projetado usando a Árvore B para manter os dados classificados de forma autobalanceada.
Operação de Pesquisa
A operação de pesquisa é 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 raiz, pesquise na subárvore direita.
- Se o nó tiver o k encontrado, basta retornar 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.
Operação de Inserção
Visto que a Árvore B é uma árvore de auto-equilí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 apropriado de inserção.
- Insira a nova chave no local adequado, mas se o nó já tiver um número máximo de chaves:
- O nó, junto com uma chave recém-inserida, se dividirá do elemento do meio.
- O elemento do meio se tornará o pai dos outros dois nós filhos.
- Os nós devem reorganizar as chaves em ordem crescente.
|
GORJETA |
O seguinte não é verdade sobre o algoritmo de inserção: Como o nó está cheio, ele será dividido e um novo valor será inserido |
No exemplo acima:
- Procure 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ó tem mais do que igual a um número mínimo de chaves, que é 1? Nesse caso, sim. Verifique a próxima regra.
- Após a inserção, o nó possui mais do que um número máximo de chaves, que é 3? Nesse caso, não, não é. 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 outros dois nós.
- No caso de um número par de chaves, o nó do meio será selecionado por polarização esquerda ou polarização direita.
No exemplo acima:
- O nó tem menos de chaves máximas
- 1 é inserido próximo a 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 eles atendem à regra de menos do que o máximo de chaves para os nós.
No exemplo acima:
- O nó possui chaves iguais a chaves máximas.
- A chave é inserida no nó de destino, mas viola a regra de chaves máximas.
- O nó de destino é dividido e a chave do meio pelo viés esquerdo 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 podem ser inseridos facilmente na Árvore B.
Excluir 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
- O destino está no nó folha, mais do que chaves mínimas.
- Excluir isso não violará a propriedade da Árvore B
- O destino está no nó folha, tem nós-chave mínimos
- Excluir isso violará a propriedade da Árvore B
- O nó alvo pode pedir emprestado a chave do nó esquerdo imediato ou do nó direito imediato (irmão)
- O irmão dirá que 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
- Pesquisar chave
- Fundir com irmãos e o mínimo de nós pais
- O total de chaves será agora superior a min
- 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, predecessor em ordem ou sucessor em ordem
- No caso do predecessor 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 predecessor 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 predecessor em ordem da chave de destino não tiver mais do que chaves mín., Procure a chave mínima do sucessor em ordem.
- Se o predecessor e o sucessor em ordem da chave de destino tiverem menos do que chaves mínimas, mescle o predecessor 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 que chaves mínimas, o nó de destino tomará emprestado o valor máximo de seu irmão via 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 B-Tree. Esta B-Tree é 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 de qualquer nó pode ter são 2 e 4, respectivamente.
No exemplo acima:
- O nó de destino tem a chave de destino para excluir
- O nó de destino tem 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 pode excluí-lo diretamente, pois violará as condições
Agora, o diagrama a seguir explica como excluir essa chave:
- O nó de destino pegará emprestada uma chave do irmão imediato, neste caso, predecessor em ordem (irmão esquerdo) porque não tem nenhum sucessor em ordem (irmão direito)
- O valor máximo do predecessor inorder será transferido para o pai, e o pai irá 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 predecessor em ordem (irmão esquerdo) tem chaves iguais às chaves mínimas.
- O valor mínimo do sucessor em ordem será transferido para o pai, e o pai irá transferir o valor máximo para o nó de destino.
No exemplo abaixo, o nó de destino não tem nenhum irmão que possa fornecer sua chave para o nó de destino. Portanto, a fusão é necessária.
Veja o procedimento de exclusão de 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 que se fundem
- Exclua a chave de destino do nó mesclado
Excluir Pseudo Código de Operação
private int removeBiggestElement(){if (root has no child)remove and return the last elementelse {answer = subset[childCount-1].removeBiggestElement()if (subset[childCount-1].dataCount < MINIMUM)fixShort (childCount-1)return answer}}
Produto :
O maior elemento é excluído da B-Tree.
Resumo:
- B Tree é uma estrutura de dados de auto-equilíbrio para melhor pesquisa, inserção e exclusão de dados do disco.
- A Árvore B é regulada pelo grau especificado
- B As chaves e nós da árvore são organizados em ordem crescente.
- A operação de busca da Árvore B é a mais simples, que sempre começa na raiz e começa a verificar se a chave de destino é maior ou menor que o valor do nó.
- A operação de inserção da Árvore B é bastante detalhada, o que primeiro encontra uma posição apropriada de inserção para a chave de destino, a insere, avalia a validade da Árvore B contra casos diferentes 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 pais.