Árvore B+: Pesquisar, Inserir e Excluir Operações

O que é uma árvore B+?

A Árvore B+ É utilizada principalmente para implementar indexação dinâmica em múltiplos níveis. Comparada a uma árvore B, a árvore B+ armazena os ponteiros de dados apenas nos nós folha da árvore, o que torna o processo de busca mais preciso e rápido.

Regras para árvore B+

Aqui estão as regras essenciais para uma árvore B+.

• As folhas são usadas para armazenar registros de dados.
• Os registros são armazenados nos nós internos da árvore.
• Se o valor da chave de destino for menor que o nó interno, o ponteiro imediatamente à sua esquerda será seguido.
• Se o valor da chave de destino for maior ou igual ao nó interno, o ponteiro imediatamente à sua direita será seguido.
• A raiz tem no mínimo dois filhos.

Por que usar a Árvore B+

Aqui estão alguns motivos para usar uma árvore B+:

• As chaves são utilizadas principalmente para auxiliar na busca, direcionando o visitante para a folha correta.
• Uma árvore B+ utiliza um "fator de preenchimento" para gerenciar o crescimento 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 de todos os elementos requer apenas uma passagem linear, pois todos os nós folha de uma árvore B+ estão interligados.

Árvore B + vs. Árvore B

Aqui estão as principais diferenças entre uma árvore B+ e uma árvore B.

Pesquisar Operação

Em uma árvore B+, a busca é um dos procedimentos mais fáceis de executar e fornece 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 nó pai da nova folha é vinculado corretamente com o valor da chave mínima e a uma nova localização na árvore.
• Divida o nó pai em mais locais, caso ele seja totalmente utilizado.
• Agora, para melhores resultados, a chave central é 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. If 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 3 primeiros 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 ser adicionado à á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 pelo kee.ping levando em consideração as regras aplicáveis ​​de igualdade ou superior a valores em relação aos nós de chave-valor à 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 na árvore uma entrada folha que contenha a chave e o ponteiro e, em seguida, excluir essa entrada da árvore se ela atender às condições exatas de exclusão de registro.
• Caso o nó folha atinja apenas o fator satisfatório de estar meio cheio, a operação é concluída; caso contrário, o nó folha possui o número mínimo de entradas e não pode ser excluído.
• Os outros nós ligados à direita e à esquerda podem desocupar quaisquer 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ó ligado na hierarquia da árvore.
• Ao fundir um nó folha com seus vizinhos à direita ou à esquerda, as entradas de valores no nó folha ou no vizinho vinculado que apontam para o nó de nível superior são excluídas.

O exemplo acima ilustra o procedimento para remover um elemento de uma árvore B+ de uma ordem específica.

• Primeiramente, as localizações exatas do elemento a ser excluído são identificadas na Árvore.
• Neste caso, o elemento a ser excluído só pode ser identificado com precisão no nível da folha e não no nível do índice. Portanto, o elemento pode ser excluído sem afetar as regras de exclusão, que é o valor da chave mínima necessária.

• No exemplo acima, temos que deletar 31 da Árvore.
• Precisamos localizar as ocorrências de 31 no Índice e na Folha.
• Podemos ver que o valor 31 está disponível tanto no nível do nó de índice quanto no nível do nó folha. Portanto, o excluímos de ambas as instâncias.
• Mas precisamos preencher o índice que aponta para 42. Agora, vamos observar o filho direito com menos de 25 anos, pegar o menor valor e usá-lo como índice. Portanto, como 42 é o único valor presente, ele se tornará o índice.

Apagar OperaAlgoritmo de ção

1) Start at the root and go up to the 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 dos nós irmãos para ajustar os valores em n e em seus nós pais, se necessário.

Perguntas Frequentes