Arvores B, B+, B*

ÁRVORES
B B+ B*
Bruno Damasceno

88907

Franco Leonardi

85722

Lucas Gabriel A. Rosa

81714

Rafaela Abrão

83066

Rodrigo Flausino Peron

39652

ÁRVORES
• Estruturas de dados que herdam as características das topologias em árvores
(um nó central constituído por repetidores que interconectam outras redes);
• Listas encadeadas em sequência;

Compostas por:
• Elemento principal (raiz)
• Ramos ou filhos
• Folha ou nó terminal

ORDEM (m)

Definição
[Bayer e McCreight] o número mínimo de chaves que uma página pode conter, ou seja, com exceção da raiz todas devem conter esse número mínimo de chaves; [Knuth]* o número máximo de páginas filhas que toda página pode conter.

ÁRVORES B

Motivação
Cenário até então:
• Acesso a disco é lento;

• Pesquisa binária é útil em índices ordenados, porém, com índice grande que não cabe em memória principal, pesquisa binária exige muitos acessos a disco.

Criar um método no qual as inserções

e remoções tenham apenas efeitos locais, ou seja, um método que não exija a reorganização total do índice

Árvore B
Visam reduzir as operações de escrita e leitura em memória secundária.

Dentre suas propriedades ela permite a inserção, remoção e busca de chaves numa complexidade de tempo logarítmica e, por esse

motivo, é muito empregada em aplicações que necessitam manipular grandes quantidades de informação tais como um banco de dados ou

um sistema de arquivos.

Árvore B
Como a ideia principal das árvores B é trabalhar com

dispositivos

de

memória

secundária, quanto menos acessos a disco a estrutura de dados proporcionar, melhor será o desempenho do sistema na operação de busca

sobre os dados manipulados.

Árvore B
• Exemplo de árvore B:

Árvore B
• Ordem
A definição atual de B-Tree vincula a ordem de uma árvore B ao número de descendentes de um nó (isto é, de ponteiros). Deste modo, numa árvore
B de ordem m, o número máximo