Trabalho Aula 7
1703 palavras
7 páginas
Árvores B+As operações nas árvores B+ não são muito diferentes das operações das árvores
B.
Inserir uma chave em uma folha que ainda tenha algum espaço exige que se coloque as chaves desta folha em ordem. Nenhuma mudança é feita no conjunto de índices. Se uma chave é inserida em uma folha cheia, a folha é dividida, o novo nó folha é incluído no conjunto de seqüência, as chaves são distribuídas homogeneamente entre a folha velha e a nova folha e a primeira chave do novo nó é copiada (não movida, como na árvore B) para o ascendente. Veja o slide a
149seguir.
29
11 19
1
2
8
10
11 13 15
19 26
A inserção da chave 6 da árvore acima resulta na árvore abaixo.
29
6
1
2
6
8
11 19
10
11 13 15
19 26
Se o ascendente não está cheio, isso pode exigir reorganização local das chaves do ascendente como no caso acima.
Se o ascendente está cheio, o processo de divisão é realizado do mesmo modo que nas árvore B. Depois de tudo, o conjunto de índices
150 é uma árvore B.
Árvores B+
Remover uma chave de uma folha sem subaproveitamento exige colocar as chaves remanescentes em ordem, nenhuma mudança é feita ao conjunto de índices. Em particular, se uma chave que não ocorre somente em uma folha é removida, ela é simplesmente removida da folha, mas pode permanecer no nó interno.
A razão é que ele ainda serve como guia apropriado quando se navega para baixo na árvore B+, porque ainda separa apropriadamente as chaves entre dois filhos adjacentes mesmo se o próprio separador não ocorre em nenhum dos filhos. Observe o processo no próximo slide.
151
Árvores B+
29
6
1
2
6
8
11 19
10
19 26
11 13 15
A remoção da chave 6 da árvore acima resulta na árvore abaixo. Note que o número
6 não é removido de um nó interno.
29
6
1
152
2
8
10
11 19
11 13 15
19 26
Árvores B+
Quando a remoção de uma chave causa subaproveitamento, ambas as chaves dessa folha e as chaves de um irmão são redistribuídas entre a folha e seu irmão, ou a folha é removida e as chaves remanescentes
são