Arvore B

Árvores B+

Grupo:
Renan de Sousa
Francisco Antônio
Liniker Alves

Á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
2
chaves.

Á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

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;
– Não é necessário manter nenhum ponteiro de registro em nós não-folha.

4

Árvore B+


Utilização
– Muitos Bancos de Dados são construídos usando o mecanismo de
Árvores B+: SQLServer e Oracle;

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;
6
• Se, após a inserção, a folha estiver completa,

Á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

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 na folha direita;
• A maior chave da esquerda é copiada para o nó pai.
8

Árvore B+


Inserção (Exemplo cont.)
– Inserir chave 70 (antes)

52 | 60 |85 |

– Inserir chave 70 (depois)
60 |
|
52 |60 | ||

70 | 85 |

|
9

Árvore B+


Inserção (Exemplo - cont.)
– Inserir chave 58
60 |

52 |58 |60 |

|
|
70 | 85 |

|

– Inserir chave 37  Realizar cisão
10

Árvore B+


Inserção (Exemplo cont.)
– Inserir chave52
37|60(depois)
| |

37 |52 |

|

58 |60 |

|

70 | 85 |

|

11