B+ Tree é uma extensão da B Tree que permite operações eficientes de inserção, exclusão e pesquisa.
Na árvore B, chaves e registros podem ser armazenados tanto nos nós internos quanto nos nós folhas. Considerando que, na árvore B+, os registros (dados) só podem ser armazenados nos nós folha, enquanto os nós internos podem armazenar apenas os valores-chave.
arquitetura linux
Os nós folha de uma árvore B+ são vinculados na forma de listas vinculadas individualmente para tornar as consultas de pesquisa mais eficientes.
Árvore B+ são usadas para armazenar uma grande quantidade de dados que não podem ser armazenados na memória principal. Devido ao fato de o tamanho da memória principal ser sempre limitado, os nós internos (chaves de acesso aos registros) da árvore B+ são armazenados na memória principal enquanto os nós folhas são armazenados na memória secundária.
Os nós internos da árvore B+ são frequentemente chamados de nós de índice. Uma árvore B+ de ordem 3 é mostrada na figura a seguir.
Vantagens da árvore B+
- Os registros podem ser buscados em igual número de acessos ao disco.
- A altura da árvore permanece equilibrada e menor em comparação com a árvore B.
- Podemos acessar os dados armazenados em uma árvore B+ de forma sequencial ou direta.
- As chaves são usadas para indexação.
- Consultas de pesquisa mais rápidas, pois os dados são armazenados apenas nos nós folha.
Árvore B VS Árvore B +
| SN | Árvore B | Árvore B+ |
|---|---|---|
| 1 | As chaves de pesquisa não podem ser armazenadas repetidamente. | Chaves de pesquisa redundantes podem estar presentes. |
| 2 | Os dados podem ser armazenados em nós folha, bem como em nós internos | Os dados só podem ser armazenados nos nós folha. |
| 3 | A busca por alguns dados é um processo mais lento, pois os dados podem ser encontrados tanto nos nós internos quanto nos nós folha. | A pesquisa é comparativamente mais rápida, pois os dados só podem ser encontrados nos nós folha. |
| 4 | A exclusão de nós internos é muito complicada e demorada. | A exclusão nunca será um processo complexo, pois o elemento sempre será excluído dos nós folha. |
| 5 | Os nós folha não podem ser vinculados. | Os nós folha são interligados para tornar as operações de pesquisa mais eficientes. |
Inserção na Árvore B+
Passo 1: Insira o novo nó como um nó folha
Passo 2: Se a folha não tiver espaço necessário, divida o nó e copie o nó do meio para o próximo nó do índice.
Etapa 3: Se o nó do índice não tiver espaço necessário, divida o nó e copie o elemento do meio para a próxima página do índice.
Exemplo :
Insira o valor 195 na árvore B+ de ordem 5 mostrada na figura a seguir.
195 será inserido na subárvore direita de 120 após 190. Insira-o na posição desejada.
O nó contém um número maior que o número máximo de elementos, ou seja, 4, portanto, divida-o e coloque o nó mediano até o pai.
chamando a função js de html
Agora, o nó do índice contém 6 filhos e 5 chaves que violam as propriedades da árvore B+, portanto precisamos dividi-lo, mostrado a seguir.
Exclusão na árvore B+
Passo 1: Exclua a chave e os dados das folhas.
Passo 2: se o nó folha contiver menos do que o número mínimo de elementos, mescle o nó com seu irmão e exclua a chave entre eles.
Etapa 3: se o nó do índice contiver menos do que o número mínimo de elementos, mescle o nó com o irmão e mova a chave entre eles.
Exemplo
Exclua a chave 200 da árvore B+ mostrada na figura a seguir.
200 está presente na subárvore direita de 190, após 195. exclua-o.
Mescle os dois nós usando 195, 190, 154 e 129.
Agora, o elemento 120 é o único elemento presente no nó que está violando as propriedades da Árvore B+. Portanto, precisamos mesclá-lo usando 60, 78, 108 e 120.
Agora, a altura da árvore B+ será diminuída em 1.
