Estrutura de arquivo Arvores

ST562 – Estruturas de Arquivos

Aula 10
●

Assuntos:
–

1

Árvores B (cont.), Árvores B* e Árvores B+

ST562 – Estruturas de Arquivos

De aulas passadas
●

●

Árvores binárias de busca
–

1ª tentativa de usar árvore como índice

–

Permitem busca binária mesmo com arquivo de registros desordenados Árvores AVL
–

●

Árvores paginadas
–

2

Introduzem ideia de balanceamento em altura para reduzir quantidade de acessos a disco
Introduzem ideia de paginação para reduzir quantidade de acessos a disco

ST562 – Estruturas de Arquivos

De aulas passadas
●

Árvores B
–

3

Utilizam paginação e balanceamento em altura para reduzir drasticamente a quantidade de seeks necessários para encontrar uma determinada chave no índice.

ST562 – Estruturas de Arquivos

Objetivos desta aula
●

●

4

Continuar o estudo sobre o uso de árvores B para indexação Apresentar variações sobre árvores B; em especial:
–

Árvores B*

–

Árvores B+

–

... e suas otimizações com relação a árvores B.

ST562 – Estruturas de Arquivos

Árvores B
●

Operações
–

Inserção
●

●

–

Promoção: chave é promovida para página superior

Remoção
●

●

5

Divisão: página com overflow (mais chaves que o possível) se divide em duas

Redistribuição: página em underflow (menos chaves que o necessário) pede chave emprestada para páginas pai e vizinha
Concatenação: chave de página superior concatena-se com chave de duas páginas inferiores vizinhas.

ST562 – Estruturas de Arquivos

Árvores B
●

Operações
–

Redistribuição na inserção
●

●

●

Inserção já cuida de overflow em nós;
Redistribuição não é necessária na inserção, mas é desejada, pois adia a criação de novas páginas

Preenchimento da árvore B no pior caso:
–

Sem redistribuição na inserção: 50% (Folk e Zoellick, 1992)

–

Com redistribuição na inserção: 69% (Yao, 1978, apud Folk e Zoellick,
1992)

6

ST562 – Estruturas de Arquivos

Árvores B
●

●

Pode-se calcular qual a profundidade (d) de uma árvore B de ordem m para armazenar N chaves em seu pior caso