Antes de entender Árvore B e Árvore B+ diferenças, devemos conhecer a árvore B e a árvore B+ separadamente.
Qual é a árvore B?
Árvore B é uma árvore de autoequilíbrio e é uma árvore m-way onde m define a ordem da árvore. Árvore B é uma generalização do Árvore de pesquisa binária em que um nó pode ter mais de uma chave e mais de dois filhos dependendo do valor de eu . Na árvore B, os dados são especificados em uma ordem de classificação, tendo valores mais baixos na subárvore esquerda e valores mais altos na subárvore direita.
exemplo de lista em java
Propriedades da árvore B
A seguir estão as propriedades da árvore B:
- Na árvore B, todos os nós folhas devem estar no mesmo nível, enquanto, no caso de uma árvore binária, os nós folhas podem estar em níveis diferentes.
Vamos entender essa propriedade através de um exemplo.
Na árvore acima, todos os nós folhas não estão no mesmo nível, mas têm no máximo dois filhos. Portanto, podemos dizer que a árvore acima é uma árvore binária mas não uma árvore B.
- Se a Btree tiver ordem m, então cada nó poderá ter no máximo eu No caso de filhos mínimos, os nós folhas possuem zero filhos, o nó raiz possui dois filhos e os nós internos possuem teto de m/2.
- Cada nó pode ter no máximo (m-1) chaves. Por exemplo, se o valor de m for 5, o valor máximo das chaves será 4.
- O nó raiz possui no mínimo uma chave, enquanto todos os outros nós, exceto o nó raiz, possuem (teto de m/2 menos - 1) chaves mínimas.
- Se realizarmos a inserção na árvore B, então o nó será sempre inserido no nó folha.
Suponha que queiramos criar uma árvore B de ordem 3 inserindo valores de 1 a 10.
Passo 1: Primeiro, criamos um nó com 1 valor conforme mostrado abaixo:
Passo 2: O próximo elemento é 2, que vem depois de 1 conforme mostrado abaixo:
Etapa 3: O próximo elemento é 3 e é inserido após 2 conforme mostrado abaixo:
Como sabemos que cada nó pode ter no máximo 2 chaves, dividiremos este nó pelo elemento do meio. O elemento do meio é 2, então ele se move para seu pai. O nó 2 não possui nenhum pai, portanto se tornará o nó raiz conforme mostrado abaixo:
Passo 4: O próximo elemento é 4. Como 4 é maior que 2 e 3, ele será adicionado após 3 conforme mostrado abaixo:
Etapa 5: O próximo elemento é 5. Como 5 é maior que 2, 3 e 4, será adicionado após 4 conforme mostrado abaixo:
Como sabemos que cada nó pode ter no máximo 2 chaves, dividiremos este nó pelo elemento do meio. O elemento do meio é 4, então ele se move para seu pai. O pai é o nó 2; portanto, 4 será adicionado após 2 conforme mostrado abaixo:
Etapa 6: O próximo elemento é 6. Como 6 é maior que 2, 4 e 5, 6 virá depois de 5 conforme mostrado abaixo:
Etapa 7: O próximo elemento é 7. Como 7 é maior que 2, 4, 5 e 6, então 7 virá depois de 6 conforme mostrado abaixo:
Como sabemos que cada nó pode ter no máximo 2 chaves, dividiremos este nó pelo elemento do meio. O elemento do meio é 6, então ele se move para seu pai conforme mostrado abaixo:
Porém, 6 não pode ser adicionado após 4 porque o nó pode ter no máximo 2 chaves, então dividiremos este nó pelo elemento do meio. O elemento do meio é 4, então ele se move para seu pai. Como o nó 4 não possui nenhum pai, o nó 4 se tornará um nó raiz conforme mostrado abaixo:
O que é uma árvore B+?
O Árvore B+ também é conhecida como árvore autoequilibrada avançada porque cada caminho da raiz até a folha da árvore tem o mesmo comprimento. Aqui, o mesmo comprimento significa que todos os nós folha ocorrem no mesmo nível. Não acontecerá que alguns dos nós folha ocorram no terceiro nível e alguns deles no segundo nível.
Um índice de árvore B+ é considerado um índice multinível, mas a estrutura da árvore B+ não é semelhante aos arquivos sequenciais de índice multinível.
Por que a árvore B+ é usada?
Uma árvore B+ é usada para armazenar os registros de forma muito eficiente, armazenando os registros de maneira indexada usando a estrutura indexada da árvore B+. Devido à indexação multinível, o acesso aos dados torna-se mais rápido e fácil.
Estrutura do nó da árvore B+
A estrutura do nó da árvore B+ contém ponteiros e valores-chave mostrados na figura abaixo:
Como podemos observar na estrutura do nó da árvore B+ acima, ela contém n-1 valores-chave (k1para kn-1) e n ponteiros (p1principaln).
Os valores da chave de pesquisa colocados no nó são mantidos em ordem de classificação. Assim, se eu
Restrição em vários tipos de nós
Seja 'b' a ordem da árvore B+.
Nó não folha
Deixe 'm' representar o número de filhos de um nó, então a relação entre a ordem da árvore e o número de filhos pode ser representada como:
Deixe k representar os valores da chave de pesquisa. A relação entre a ordem da árvore e a chave de pesquisa pode ser representada como:
Como sabemos que o número de ponteiros é igual aos valores da chave de pesquisa mais 1, então matematicamente pode ser escrito como:
Número de ponteiros (ou filhos) = Número de chaves de pesquisa + 1
Portanto, o número máximo de ponteiros seria 'b', e o número mínimo de ponteiros seria a função teto de b/2.
Nó da folha
Um nó folha é um nó que ocorre no último nível da árvore B+, e cada nó folha usa apenas um ponteiro para se conectar entre si para fornecer o acesso sequencial no nível folha.
No nó folha, o número máximo de filhos é:
O número máximo de chaves de pesquisa é:
função chr python
Nó raiz
O número máximo de filhos no caso do nó raiz é: b
O número mínimo de crianças é: 2
Casos especiais na árvore B+
Caso 1: Se o nó raiz for o único nó na árvore. Neste caso, o nó raiz torna-se o nó folha.
Neste caso, o número máximo de filhos é 1, ou seja, o próprio nó raiz, enquanto o número mínimo de filhos é b-1, que é igual ao de um nó folha.
Representação de um nó folha na árvore B+
Na figura acima, '.' representa o ponteiro, enquanto 10, 20 e 30 são os valores-chave. O ponteiro contém o endereço no qual o valor da chave está armazenado, conforme mostrado na figura acima.
Exemplo de árvore B+
Na figura acima, o nó contém três valores-chave, ou seja, 9, 16 e 25. O ponteiro que aparece antes de 9 contém os valores-chave menores que 9 representados por keu. O ponteiro que aparece antes de 16 contém os valores-chave maiores ou iguais a 9, mas menores que 16 representados por kj. O ponteiro que aparece antes de 25 contém os valores-chave maiores ou iguais a 16, mas menores que 25 representados por kn.
Diferenças entre árvore B e árvore B+
A seguir estão as diferenças entre a árvore B e a árvore B+:
| Árvore B | Árvore B+ |
|---|---|
| Na árvore B, todas as chaves e registros são armazenados tanto em nós internos quanto em nós folhas. | Na árvore B+, as chaves são os índices armazenados nos nós internos e os registros são armazenados nos nós folha. |
| Na árvore B, as chaves não podem ser armazenadas repetidamente, o que significa que não há duplicação de chaves ou registros. | Na árvore B+ pode haver redundância na ocorrência das chaves. Neste caso, os registros são armazenados nos nós folha, enquanto as chaves são armazenadas nos nós internos, portanto, chaves redundantes podem estar presentes nos nós internos. |
| No Btree, os nós folha não estão vinculados entre si. | Na árvore B+, os nós folha estão interligados para fornecer o acesso sequencial. |
| No Btree, a pesquisa não é muito eficiente porque os registros são armazenados em folhas ou em nós internos. | Na árvore B+, a pesquisa é muito eficiente ou mais rápida porque todos os registros são armazenados nos nós folha. |
| A exclusão de nós internos é muito lenta e demorada, pois precisamos considerar também o filho da chave excluída. | A exclusão na árvore B+ é muito rápida porque todos os registros são armazenados nos nós folha, portanto não precisamos considerar o filho do nó. |
| No Btree, o acesso sequencial não é possível. | Na árvore B+, todos os nós folhas estão conectados entre si através de um ponteiro, portanto o acesso sequencial é possível. |
| No Btree, quanto maior o número de operações de divisão são realizadas devido ao aumento da altura em comparação com a largura, | A árvore B+ tem mais largura em comparação com a altura. |
| No Btree, cada nó possui pelo menos duas ramificações e cada nó contém alguns registros, portanto, não precisamos percorrer até os nós folha para obter os dados. | Na árvore B+, os nós internos contêm apenas ponteiros e os nós folhas contêm registros. Todos os nós folha estão no mesmo nível, então precisamos percorrer até os nós folha para obter os dados. |
| O nó raiz contém pelo menos 2 a m filhos, onde m é a ordem da árvore. | O nó raiz contém pelo menos 2 a m filhos, onde m é a ordem da árvore. |