O que é uma árvore B +?
Uma árvore B + é utilizada principalmente para implementar a indexação dinâmica em vários níveis. Comparado com a Árvore B, a Árvore B + armazena os ponteiros de dados apenas nos nós folha da Árvore, o que torna o processo de pesquisa mais preciso e rápido.
Neste tutorial B + Tree, você aprenderá:
- O que é uma árvore B +?
- Regras para árvore B +
- Por que usar B + Tree
- Árvore B + vs. Árvore B
- Operação de Pesquisa
- Operação de Inserção
- Excluir operação
Regras para árvore B +
Aqui estão as regras essenciais para a Árvore B +.
- As folhas são usadas para armazenar registros de dados.
- Ele é armazenado nos nós internos da Árvore.
- Se um valor-chave de destino for menor que o nó interno, o ponto logo à esquerda é seguido.
- Se um valor de chave de destino for maior ou igual ao nó interno, o ponto logo à direita é seguido.
- A raiz tem no mínimo dois filhos.
Por que usar B + Tree
Aqui estão as razões para usar B + Tree:
- As chaves são utilizadas principalmente para auxiliar na pesquisa, direcionando para a Folha adequada.
- A árvore B + usa um "fator de preenchimento" para gerenciar o aumento e a diminuição em uma árvore.
- Em árvores B +, várias chaves podem ser facilmente colocadas na página da memória porque elas não têm os dados associados aos nós internos. Portanto, ele acessará rapidamente os dados da árvore que estão no nó folha.
- Uma varredura completa e abrangente de todos os elementos é uma árvore que precisa de apenas uma passagem linear porque todos os nós folha de uma árvore B + estão vinculados uns aos outros.
Árvore B + vs. Árvore B
Aqui estão as principais diferenças entre a Árvore B + e a Árvore B
| Árvore B + | Árvore B |
| As chaves de pesquisa podem ser repetidas. | As chaves de pesquisa não podem ser redundantes. |
| Os dados são salvos apenas nos nós folha. | Ambos os nós folha e nós internos podem armazenar dados |
| Os dados armazenados no nó folha tornam a pesquisa mais precisa e rápida. | A pesquisa é lenta devido aos dados armazenados na Folha e nos nós internos. |
| A exclusão não é difícil, pois um elemento é removido apenas de um nó folha. | A exclusão de elementos é um processo complicado e demorado. |
| Os nós folha vinculados tornam a pesquisa rápida e eficiente. | Você não pode vincular nós folha. |
Operação de Pesquisa
No B + Tree, uma pesquisa é um dos procedimentos mais fáceis de executar e obter resultados rápidos e precisos.
O seguinte algoritmo de pesquisa é aplicável:
- Para encontrar o registro necessário, você precisa executar a pesquisa binária nos registros disponíveis na Árvore.
- Em caso de correspondência exata com a chave de pesquisa, o registro correspondente é devolvido ao usuário.
- Caso a chave exata não seja localizada pela pesquisa no nó pai, atual ou folha, uma "mensagem não encontrada" é exibida para o usuário.
- O processo de pesquisa pode ser executado novamente para resultados melhores e mais precisos.
Algoritmo de operação de pesquisa
1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."
Produto :
O conjunto de registros correspondente à chave exata é exibido para o usuário; caso contrário, uma tentativa falhada é mostrada ao usuário.
Operação de Inserção
O seguinte algoritmo é aplicável para a operação de inserção:
- 50 por cento dos elementos nos nós são movidos para uma nova folha para armazenamento.
- O pai da nova Folha é vinculado com precisão ao valor mínimo da chave e a um novo local na Árvore.
- Divida o nó pai em mais locais, caso seja totalmente utilizado.
- Agora, para melhores resultados, a chave central está associada ao nó de nível superior dessa Folha.
- Até que o nó de nível superior não seja encontrado, continue iterando o processo explicado nas etapas acima.
Inserir Algoritmo de Operação
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.
Produto :
O algoritmo irá determinar o elemento e inseri-lo com sucesso no nó folha necessário.
O exemplo de amostra B + Tree acima é explicado nas etapas abaixo:
- Em primeiro lugar, temos 3 nós, e os primeiros 3 elementos, que são 1, 4 e 6, são adicionados em locais apropriados nos nós.
- O próximo valor na série de dados é 12, que precisa fazer parte da Árvore.
- Para conseguir isso, divida o nó, adicione 6 como um elemento de ponteiro.
- Agora, uma hierarquia direita de uma árvore é criada e os valores de dados restantes são ajustados de acordo, mantendo em mente as regras aplicáveis de valores iguais ou maiores do que contra os nós de valor-chave à direita.
Excluir operação
A complexidade do procedimento de exclusão na árvore B + ultrapassa a da funcionalidade de inserção e pesquisa.
O seguinte algoritmo é aplicável ao excluir um elemento da Árvore B +:
- Em primeiro lugar, precisamos localizar uma entrada de folha na Árvore que contém a chave e o ponteiro. , exclua a entrada folha da Árvore se a Folha atender às condições exatas de exclusão do registro.
- Caso o nó folha apenas atenda ao fator satisfatório de estar meio cheio, a operação é concluída; caso contrário, o nó Folha tem entradas mínimas e não pode ser excluído.
- Os outros nós vinculados à direita e à esquerda podem desocupar todas as entradas e, em seguida, movê-las para a Folha. Se esses critérios não forem atendidos, eles devem combinar o nó folha e seu nó vinculado na hierarquia da árvore.
- Após a fusão do nó folha com seus vizinhos à direita ou esquerda, as entradas de valores no nó folha ou vizinho vinculado apontando para o nó de nível superior são excluídas.
O exemplo acima ilustra o procedimento para remover um elemento da Árvore B + de uma ordem específica.
- Em primeiro lugar, os locais exatos do elemento a ser excluído são identificados na Árvore.
- Aqui, o elemento a ser excluído só pode ser identificado com precisão no nível da folha e não no posicionamento do índice. Portanto, o elemento pode ser excluído sem afetar as regras de exclusão, que é o valor da chave mínima.
- No exemplo acima, temos que deletar 31 da Árvore.
- Precisamos localizar as instâncias de 31 em Index e Leaf.
- Podemos ver que 31 está disponível em nível de nó de índice e folha. Portanto, o excluímos de ambas as instâncias.
- Mas, temos que preencher o índice apontando para 42. Agora vamos olhar para a criança certa com menos de 25 anos e pegar o valor mínimo e colocá-lo como um índice. Portanto, sendo 42 o único valor presente, ele se tornará o índice.
Excluir Algoritmo de Operação
1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node
Produto :
A chave "K" é excluída e as chaves são emprestadas de irmãos para ajustar os valores em n e seus nós pais, se necessário.
Resumo:
- B + Tree é uma estrutura de dados de auto-equilíbrio para a execução de pesquisas precisas e rápidas, inserção e exclusão de procedimentos nos dados
- Podemos facilmente recuperar dados completos ou dados parciais, porque passar pela estrutura de árvore vinculada torna-a eficiente.
- A estrutura da árvore B + aumenta e diminui com um aumento / diminuição no número de registros armazenados.
- O armazenamento de dados nos nós folha e subsequente ramificação dos nós internos evidentemente encurta a altura da árvore, o que reduz as operações de entrada e saída do disco, consumindo muito menos espaço nos dispositivos de armazenamento.