programação
1057 palavras
5 páginas
Árvores+
B
Prof Márcio Bueno ed2tarde@marciobueno.com / ed2noite@marciobueno.com
Material da Profa Ana Eliza Lopes Moura
Árvore
+
B
A árvore B+ é uma variação da estrutura básica da árvore B.
Características:
– Todas as chaves são mantidas em folhas;
– As chaves são repetidas em nós não-folha formando um índice;
– As folhas são ligadas oferecendo um caminho seqüencial para percorrer as chaves. Estrutura de Dados II - Márcio Bueno
2
Árvore
+
B
Exemplo
98
36 53 81
8 17 36 43 53 56 65 72 81
104 119
85 90
102 104 107 112 119 125 127
Estrutura de Dados II - Márcio Bueno
3
Árvore
+
B
Vantagem
– Mantém a eficiência da busca e da inserção da árvore B;
– Aumenta a eficiência da localização do próximo registro na árvore de O(log2N) para O(1);
– Não é necessário manter nenhum ponteiro de registro em nós não-folha.
Estrutura de Dados II - Márcio Bueno
4
Árvore
+
B
Utilização
– Muitos Bancos de Dados são construídos usando o mecanismo de Árvores B+:
SQLServer e Oracle;
Estrutura de Dados II - Márcio Bueno
5
Árvore B+
Inserção
– A inserção de uma nova chave em uma árvore B+ é semelhante a inserção em uma árvore B: ocorre sempre em um nó folha. – Passos:
• Localizar a folha dentro da qual a chave deve ser inserida;
• Localizar a posição de inserção dentro da folha; • Inserir a chave;
• Se, após a inserção, a folha estiver completa, realizar a cisão da página.
Estrutura de Dados II - Márcio Bueno
6
Árvore B+
Inserção (Exemplo) – ordem M = 5
– Inserir chave 85
85 | | |
– Inserir chave 60
60 | 85 | |
– Inserir chave 52
52 | 60 |85 |
– Inserir chave 70 Realizar cisão
Estrutura de Dados II - Márcio Bueno
7
Árvore B+
Inserção -> Cisão de Página
– As M-1 chaves serão divididas em dois grupos: • as (M-1 div 2) chaves menores ficam na folha esquerda; • as (M-1 div 2) chaves maiores ficam