Arvoreb

UNIVERSIDADE SANTA CECILIA
UNISANTA
SANTOS

ESTRUTURA DE DADOS
ARVORE B+

NOME: MATEUS BELTRAME PADOVANI

RA 076447

1. ÁRVORES-B+
Uma das maiores deficiências da árvore-B é a dificuldade de percorrer as chaves sequencialmente. Uma variação da estrutura básica da árvore-B é a árvore-B + . Nesta estrutura, todas as chaves são mantidas em folhas, e algumas chaves são repetidas em nós não-folha para definir caminhos para localizar registros individuais.
As folhas são ligadas através de uma lista duplamente encadeada, de modo a oferecer um caminho sequencial para percorrer as chaves na árvore. Esta lista é chamada de Conjunto de
Sequência (Sequence Set).
É importante esta separação lógica da árvore-B + em Conjunto de Índices (Index Set) e
Conjunto de Sequência, pois podemos fazer a maioria das inclusões e exclusões no conjunto de sequência sem alterar o índice (árvore-B). Quando houver necessidade de inclusão ou exclusão do referido índice, usamos os algoritmos já conhecidos da árvoreB.
A inserção numa árvore-B + ocorre praticamente da mesma forma que numa árvore-B, exceto pelo fato de que, quando um nó é dividido, a chave do meio é retida no meio nó esquerdo, além de ser promovida a pai. Quando uma chave é eliminada de uma folha, ela pode ser retida nas não-folhas porque ela ainda é um separador válido entre as chaves nos nós abaixo dela.
A árvore-B + mantém o baixo custo das operações de pesquisa, inclusão e exclusão e adquire a vantagem de requerer no máximo um acesso para satisfazer a operação da próxima chave.
Além disso, para um processamento sequencial nenhum nodo precisará ser acessado mais de uma vez como acontece no caminhamento in-order que precisamos fazer numa árvore -B. Portanto, enquanto a eficiência de localização do registro seguinte em um árvore-B é O(log n), numa árvoreB + é aumentada para O(1).
A árvore-B+ é ideal para aplicações que requerem tanto acesso seqüencial quanto aleatório.
Por isso e pelas vantagens citadas anteriormente, a árvore -B+