ÁRVORE B+: Pesquisar, Inserir e Excluir OperaExemplo de ções
Sarah Chen
O que é uma árvore B+?
A Árvore B+ é utilizado principalmente para implementar indexação dinâmica em vários níveis. Comparada à Árvore B, a Árvore B+ armazena os ponteiros de dados apenas nos nós folhas da Árvore, o que torna o processo de pesquisa mais preciso e rápido.
Regras para árvore B+
Aqui estão as regras essenciais para a Árvore B+.
- As folhas são usadas para armazenar registros de dados.
- É armazenado nos nós internos da Árvore.
- Se um valor de chave de destino for menor que o nó interno, o ponto logo à sua esquerda será seguido.
- Se um valor de chave de destino for maior ou igual ao nó interno, o ponto logo à direita será seguido.
- A raiz tem no mínimo dois filhos.
Por que usar a Árvore B+
Aqui estão as razões para usar a Árvore B+:
- As chaves são utilizadas principalmente para auxiliar na busca, direcionando para a Folha adequada.
- A árvore B+ usa um “fator de preenchimento” para gerenciar o aumento e a diminuição em uma árvore.
- Nas árvores B+, inúmeras chaves podem ser facilmente colocadas na página da memória porque não possuem 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 folhas de uma árvore B+ estão interligados.
Árvore B + vs. Árvore B
Aqui estão as principais diferenças entre Árvore B + e Á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. | Tanto os nós folha quanto os 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 no Leaf e nos nós internos. |
| A exclusão não é difícil porque um elemento só é removido de um nó folha. | A exclusão de elementos é um processo complicado e demorado. |
| Os nós folha vinculados tornam a pesquisa eficiente e rápida. | Você não pode vincular nós folha. |
Pesquisar Operação
Na Árvore B+, a 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 o busca binária nos registros disponíveis na Árvore.
- No caso de correspondência exata com a chave de pesquisa, o registro correspondente é retornado ao usuário.
- Caso a chave exata não seja localizada pela pesquisa no nó pai, atual ou folha, uma “mensagem não encontrada” será exibida ao usuário.
- O processo de pesquisa pode ser executado novamente para obter resultados melhores e mais precisos.
Pesquisar OperaAlgoritmo de ção
1. Call the binary search method on the records in the B+ Tree.
2. If the search parameters match the exact key
The accurate result is returned and displayed to the user
Else, if the node being searched is the current and the exact key is not found by the algorithm
Display the statement "Recordset cannot be found."
saída:
O conjunto de registros correspondente à chave exata é exibido ao usuário; caso contrário, uma tentativa falhada será mostrada ao usuário.
inserção Operação
O seguinte algoritmo é aplicável para a operação de inserção:
- 50% dos elementos nos nós são movidos para uma nova folha para armazenamento.
- O pai da nova Folha está vinculado precisamente ao valor mínimo da chave e a um novo local na Árvore.
- Divida o nó pai em mais locais, caso ele 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.
inserção OperaAlgoritmo de ção
1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record
2. 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 tree
b. 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.
saída:
O algoritmo determinará o elemento e o inserirá com sucesso no nó folha necessário.
O exemplo de amostra da árvore B+ acima é explicado nas etapas abaixo:
- Primeiramente, 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ó e adicione 6 como elemento ponteiro.
- Agora, uma hierarquia à direita de uma árvore é criada e os valores de dados restantes são ajustados de acordo, tendo em mente as regras aplicáveis de valores iguais ou maiores em relação aos nós de valor-chave à direita.
Apagar Operação
A complexidade do procedimento de exclusão na Árvore B+ supera a da funcionalidade de inserção e pesquisa.
O seguinte algoritmo é aplicável ao excluir um elemento da árvore B+:
- Primeiramente, precisamos localizar uma entrada folha na Árvore que contém a chave e o ponteiro. , exclua a entrada da folha da Árvore se a Folha atender às condições exatas de exclusão do registro.
- Caso o nó folha atenda apenas ao fator satisfatório de estar meio cheio, a operação é concluída; caso contrário, o nó Folha possui entradas mínimas e não pode ser excluído.
- Os outros nós vinculados à direita e à esquerda podem desocupar quaisquer entradas e movê-las para a Folha. Se esses critérios não forem atendidos, eles deverão 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.
- Primeiramente, as localizações exatas do elemento a ser excluído são identificadas na Árvore.
- Aqui, o elemento a ser excluído só pode ser identificado com precisão no nível folha e não na colocação do índice. Conseqüentemente, 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 nos níveis de nó Índice e Folha. Portanto, nós o excluímos de ambas as instâncias.
- Mas temos que preencher o índice apontando para 42. Vamos agora olhar para o filho certo com menos de 25 anos e pegar o valor mínimo e colocá-lo como índice. Então, sendo 42 o único valor presente, ele se tornará o índice.
Apagar OperaAlgoritmo de ção
1) Start at the root and go up to leaf node containing the key K
2) Find the node n on the path from the root to the leaf node containing K
A. If n is root, remove K
a. if root has more than one key, done
b. if root has only K
i) if any of its child nodes can lend a node
Borrow key from the child and adjust child links
ii) Otherwise merge the children nodes. It will be a new root
c. If n is an internal node, remove K
i) 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 node
Adjust child links
Else
Merge n with its sibling
Adjust child links
d. If n is a leaf node, remove K
i) If n has at least ceil(M/2) elements, done!
In case the smallest key is deleted, push up the next key
ii) If n has less than ceil(m/2) elements
If the sibling can lend a key
Borrow key from a sibling and adjust keys in n and its parent node
Else
Merge n and its sibling
Adjust keys in the parent node
saída:
A chave “K” é excluída e as chaves são emprestadas de irmãos para ajustar valores em n e seus nós pais, se necessário.
Resumo
- B+ Tree é um autoequilíbrio estrutura de dados para executar procedimentos precisos e mais rápidos de pesquisa, inserção e exclusão de dados
- Podemos recuperar facilmente dados completos ou parciais porque passar pela estrutura de árvore vinculada o torna eficiente.
- A estrutura da árvore B+ cresce e diminui com o aumento/diminuição do número de registros armazenados.
- O armazenamento de dados nos nós folha e a 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, em última análise, muito menos espaço nos dispositivos de armazenamento.
