aaaa

ACESSO À MEMÓRIA
SECUNDÁRIA - ÁRVORES
ORI – Prof. Dr. Ednaldo Pizzolato

Árvores
• Motivação
– Quando não conseguimos trabalhar na memória principal (ou primária), temos que usar a memória secundária...
– Sabemos que o acesso aos dados em memória secundária é muito lento.
– Precisamos de meios eficientes de acesso aos dados (provavelmente na forma de
‘’índices”)

Árvores
• Motivação (recordando...):
– Assuma que um disco gire a 3600 RPM
– Em 1 minuto faz 3.600 rotações, portanto uma rotação leva 1/60 de segundo, ou 16.7ms
– Na média cada acesso gastaria 8ms
– Parece ok até nos darmos conta que 120 acessos a disco consomem um segundo – o mesmo que 25 millhões de instruções
– Ou seja, um acesso a disco é equivalente a 200.000 instruções Árvores
• Soluções?
– Árvores... (AVLs, Árvores-B,...)

Árvores
• Para árvores balanceadas com n itens, as operações na árvore (inserção etc) são
O(log n) porque a altura da árvore é aproximadamente log n.
Exemplos:
binary tree c/ 1000 itens: h ~= log2 1000 ~= 10
10-ary tree c/ 1000 itens: h ~= log10 1000 ~= 3

Árvores
• Assuma que usaremos uma AVL para armazenar dados de motoristas (+/- 20 milhões de registros)
• Teríamos uma árvore bem alta (vários acessos a disco); • log2 20.000.000 é +/- 24, o que consome +/- 0.2 segundos • A solução é aumentar o número de ramificações na árvore diminuindo, assim, a altura!

Árvores
TRADEOFF
Fator de ramificação
• Complexidade de comparações
• Tamanho do nó

Árvores
•

Árvores binárias são o caso extremo:
– Fator mínimo de ramificação (2)
– Máxima profundidade (muitos acessos)

•

Se os acessos são caros (armazenamento secundário), o desempenho cai… Árvores

Árvore binária com 127 nós em 7 níveis.

Árvores

Árvore 10-aria com 127 nós em 3 níveis.

Árvores n-árias
• n ponteiros
• n-1 chaves

Árvores n-árias
10 20 30 40