arvore Binaria

Árvore de Pesquisa

●

são estruturas de dados eficientes quando se trabalha com tabelas que caibam inteiramente na memória ●

em memória secundária:
» utilizar árvores binárias onde os nodos são armazenados em disco
» os apontadores à esquerda e à direita se tornam endereços de discos
» utilizando o algoritmo para memória primária precisaríamos de log2 n acessos a discos

●

um arquivo com 106 registros faria log2 106 ≈ 20 buscas no disco

Diminuindo Acessos a Disco

●

agrupar os nodos de uma árvore em páginas

●

a forma de organizar os nodos é de extrema importância

●

podemos alocar seqüencialmente sem considerar o formato físico da árvore:
» armazena os nodos em posições consecutivas na página
» utiliza todo o espaço na página
» logo os nodos estão relacionados por ordem de entrada das chaves e não pela localidade dentro da árvore
↓
tempo de pesquisa muito pior que da árvore ótima ●

tentar otimizar a árvore
» problema de otimização muito complexo

Árvores B

●

Bayer e McCreight em 1972

●

Quando uma árvore possui mais de um registro por nodo ela passa a ser chamada n-árias
» passa a ter mais de dois descendentes por nó
» neste caso os nodos são comumente chamados de páginas

●

Uma árvore B é uma árvore n-ária onde:
» cada página contém no mínimo m registros com m+1 descendentes e
» no máximo 2m registros com 2m+1 descendentes
» todas as páginas folhas estão no mesmo nível

Uma Árvore B de ordem 2

10 20

3 4 8 9

11 13 17

chave1

p1

chave2

p2

...

p3

25 28

chave2m

p2m

Nodo de uma árvore B de ordem m

p2m

Implementação

#define mm 4 typedef struct {
TipoChave Chave;
/* outros componentes */
} Registro; typedef struct Página_str *Apontador; typedef struct Página_str { int n;
Registro r[mm];
Apontador p[mm + 1];
} Página; typedef Apontador

TipoDicionário;

Inicializando/Pesquisando void Inicializa(TipoDicionário