Diferença chave: Em computadores, as árvores binárias são estruturas de dados em árvore que armazenam os dados e permitem que o usuário acesse, pesquise, insira e exclua os dados no momento do algoritmo. A diferença entre uma árvore B e B + é que, em uma árvore B, as chaves e os dados podem ser armazenados nos nós internos e folha, enquanto que em uma árvore B +, os dados e chaves podem ser armazenados apenas nos nós folha .
As árvores binárias são árvores de pesquisa balanceadas projetadas para funcionar bem em dispositivos de armazenamento secundário de acesso direto, como discos magnéticos. Rudolf Bayer e Ed McCreight inventaram o conceito de uma árvore B.
Uma árvore B é uma árvore de busca binária generalizada, na qual qualquer nó pode ter mais de dois filhos. Cada nó interno em uma árvore B contém várias chaves. Essas chaves separam os valores e formam ainda as subárvores. Os nós internos em uma árvore B podem ter números variáveis de nós filhos, organizados em um intervalo predefinido. No momento em que qualquer dado é inserido ou removido de qualquer nó, há uma mudança no número de nós filhos. Para manter o intervalo predefinido, os nós internos podem ser unidos ou divididos. Em uma árvore B, é permitido um intervalo de nós filhos, devido ao qual o intervalo predefinido deve ser mantido.
As árvores B não precisam ser reequilibradas freqüentemente, ao contrário de outras árvores de pesquisa de autoequilíbrio. Os nós nessas árvores nem sempre estão cheios; Portanto, os espaços são consumidos desnecessariamente nessas árvores, levando ao desperdício de espaço. Somente os limites inferior e superior do número de nós filhos são normalmente fixados para uma implementação específica. Por exemplo, em uma árvore B 2-3 (geralmente chamada simplesmente de árvore 2-3), cada nó interno pode ter apenas 2 ou 3 nós filhos.
Além disso, a árvore B é otimizada para sistemas que lêem e escrevem grandes blocos de dados. É comumente usado em bancos de dados e sistemas de arquivos. Na árvore B, todos os nós são mantidos nas mesmas profundidades de balanceamento dos nós raiz. Essas profundidades aumentam lentamente à medida que o número de elementos aumenta; Isso resulta em todos os nós da folha sendo mais um nó mais distante da raiz. Além disso, as árvores B são mais vantajosas quando comparadas com outras implementações no que diz respeito ao tempo necessário para acessar os dados.
Uma árvore B + é uma árvore n-array com um nó, que consiste em um grande número de filhos por nó. A raiz pode ser uma folha ou um nó que contém mais de dois filhos. Uma árvore B + consiste em uma raiz, nós internos e folhas.
Uma árvore B + é a mesma que uma árvore B; A única diferença é que, na árvore B +, há um nível adicional adicionado na parte inferior com folhas vinculadas. Além disso, ao contrário da árvore B, cada nó em uma árvore B + contém apenas chaves e não pares de valores-chave.
Além disso, o fator de balanceamento ou a ordem de uma árvore B + mede a capacidade dos nós internos em uma árvore, ou seja, o número de nós que eles podem ter. O número real de filhos para um nó é limitado para nós internos. No entanto, a raiz é uma exceção, pois é permitido ter mais de dois números de filhos. Por exemplo, se a ordem de uma árvore B + for 7, cada nó interno (com exceção da raiz) poderá ter entre 4 e 7 filhos; enquanto a raiz pode ter entre 2 e 7. O valor primário da árvore B + está no armazenamento de dados para recuperação eficiente em um contexto de armazenamento orientado a bloco e em sistemas de arquivos específicos.
O valor primário da árvore B + é armazenar e manter os dados, para que os dados não sejam perdidos. Essa abordagem é aplicada especialmente no contexto de armazenamento orientado a blocos e em alguns sistemas de arquivos específicos. As folhas, que são os blocos de índice mais abaixo, da árvore B + são frequentemente ligadas umas às outras em uma lista encadeada; Portanto, isso torna as consultas de intervalo ou uma iteração ordenada pelos blocos mais simples e eficiente. Além disso, o fator espaço não é desperdiçado em árvores B +. A árvore B + fornece um formato de estrutura de dados de alojamento eficiente, o que os torna simples no acesso e armazenamento. As árvores B + são particularmente úteis como um índice do sistema de banco de dados, em que os dados geralmente residem em um disco.
Comparação entre Árvore B e Árvore B +:
Árvore B | Árvore B + | |
Descrições curtas da web | A árvore AB é uma estrutura organizacional para armazenamento e recuperação de informações na forma de uma árvore na qual todos os nós terminais estão à mesma distância da base e todos os nós não-terminais têm entre n e 2 n subárvores ou ponteiros (onde n é um inteiro). | B + tree é uma árvore n-array com uma variável, mas muitas vezes grande número de filhos por nó. Uma árvore B + consiste em uma raiz, nós internos e folhas. A raiz pode ser uma folha ou um nó com dois ou mais filhos. |
Também conhecido como | Árvore equilibrada. | B mais árvore. |
Espaço | Em) | Em) |
Procurar | O (log n) | O (log b n) |
Inserir | O (log n) | O (log b n) |
Excluir | O (log n) | O (log b n) |
Armazenamento | Em uma árvore B, pesquise chaves e dados armazenados em nós internos ou folha. | Em uma árvore B +, os dados são armazenados apenas nos nós folha. |
Dados | Os nós de folha dos três indicadores de armazenamento para registros em vez de registros reais. | Os nós de folha da árvore armazenam o registro real em vez de ponteiros para registros. |
Espaço | Essas árvores desperdiçam espaço | Lá as árvores não perdem espaço. |
Função dos nós foliares | Na árvore B, o nó folha não pode armazenar usando a lista vinculada. | Na árvore B +, os dados do nó da folha são ordenados em uma lista vinculada sequencial. |
Procurando | Aqui, a busca torna-se difícil na B-tree, pois os dados não podem ser encontrados no nó da folha. | Aqui, pesquisar qualquer dado em uma árvore B + é muito fácil, porque todos os dados são encontrados em nós de folhas. |
Acessibilidade de pesquisa | Aqui na árvore B, a busca não é tão fácil quando comparada a uma árvore B +. | Aqui na árvore B +, a busca fica fácil. |
Chave redundante | Eles não armazenam chave de pesquisa redundante. | Eles armazenam chave de pesquisa redundante. |
Aplicações | Eles são uma versão mais antiga e não são tão vantajosas em comparação com as árvores B +. | Muitos implementadores de sistemas de banco de dados preferem a simplicidade estrutural de uma árvore B +. |
