5COP096 Teoria da Computação - · PDF file5COP096 –Teoria da Computação Aula 9 –Pesquisa em Memória Secundária Sumário 1) Introdução à Pesquisa em Memória Secundária

5COP096 – Teoria da ComputaçãoAula 9 – Pesquisa em Memória Secundária

5COP096 Teoria da ComputaçãoTeoria da Computação

Aula 9

Prof. Dr. Sylvio Barbon Junior

Sylvio Barbon Jr – [email protected] 1


Sumário

1) Introdução à Pesquisa em Memória Secundária

2) Modelo de Computação para Memória Secundária

3) Acesso Sequencial Indexado

4) Árvore de Pesquisa

5) Considerações Práticas



Introdução à Pesquisa em Memória Secundária

1) Introdução à Pesquisa em Memória Secundária:

- A pesquisa em M.S. é utilizada quando a quantidade de memória interna não é capaz de armazenar os registros do arquivo base.

Memória Primária Memória Secundária


Memória Primária Memória Secundária

Custo principal: processamento Custo principal: acesso

Preocupação: Operações Preocupação: Transferência

Acesso a qualquer registro com custo uniforme.

Apenas um registro a cada momento, de forma sequencial


Modelo de Computação para Memória Secundária

- Necessidade de grandes quantidades de memória e o alto custo da memória principal motivam o uso da Memória Secundária.

- A organização do fluxo de informação entre a M.P e M.S. é extremamente importante, para tal faz-se necessário a gestão entre espaço de endereçamento e espaço de memória.espaço de endereçamento e espaço de memória.

- Desta forma, o “programador” utiliza o espaço de endereçamento para desenvolver seu trabalho, que pode ser maior que o espaço de memória primária disponível.

- O programador acaba por utilizar uma MEMÓRIA VIRTUAL.



Modelo de Computação para Memória Secundária

MemóriaVirtual

Memória Física“Primária”

- Existem várias formas para implementar sistemas de memória virtual, um dos meios mais utilizados é o sistema de paginação.


Disco Rígido“Secundária”

Memória Física“Primária”


Modelo de Computação para Memória Secundária- O mecanismo de paginação possui duas funções:

1) Realizar o mapeamento de endereços, isto é, determinar qual páginaum programa está endereçado, que pode ser feito por meio de Tabela depáginas.

2) Transferir páginas da memória secundária para a memória primáriaquando necessário, e transferi-las de volta para a memória secundáriaquando não são mais utilizadas. Para tal algumas abordagens sãoestudadas:


Menos Recentemente Utilizada (LRU – Least Recently Used)

Menos Frequentemente Utilizada (LFU – Least Frequently Used)

Ordem de Chegada (FIFO)

Deve ser registrada a frequência

Uma página recente pode ser removida

É o mais simples e barato de manter


Acesso Sequencial Indexado

- A partir do primeiro, cada registro é lido sequencialmente até encontrar uma chave maior ou igual à chave de pesquisa.

- Para aumentar a eficiência, é necessário:

a) Manter ordenado o campo chave do registro;

b) Caso o índice seja pares de valores (<x, p>), x deve ser uma chave e p o b) Caso o índice seja pares de valores (<x, p>), x deve ser uma chave e p o endereço do “primeiro” x;


3 14 25 41

1 2 3 4

3 5 7 11 14 17 20 21 25 29 32 36 41 44 48


Árvore de Pesquisa- Árvores binárias são soluções adequadas para trabalhar com memóriainterna, apresentando resultados adequados para acesso sequencial,facilidade de inserção e retirada de registros e boa utilização de memória.

- No caso da memória secundária, uma estratégia é agrupar os nós daárvore em páginas.

Balanceamento caro


Menos acessos aos

discos

Balanceamento caro


Árvore de Pesquisa- Árvore-B (Árvore-Bayer ou Multivias):

- São chamadas de árvores n-árias, pois possuem mais de duas sub-árvores por nó, também chamada de página.

- Cada página contém no mínimo m registros m+1 descendentes.

- Cada página contem no máximo 2m registros e 2m+1 descendentes.

- Todas as páginas folhas devem estar no mesmo nível.

- Cada página, exceto a raiz e as folhas, tem pelo menos ⌈d/2⌉ páginasfilhas

- A página raiz tem ao menos duas páginas filhas (ao menos que ela sejauma folha)



Árvore de Pesquisa

- Árvore-B (Árvore-Bayer ou Multivias):


http://slady.net/java/bt/view.php?w=800&h=600


Árvore de Pesquisa- Árvore-B (Árvore-Bayer ou Multivias):

1) Foram originalmente concebidas para a implementação de mecanismosde indexação por chave em memória secundária.

2) Permitem um número menor de nós (altura), por isso, menos acessos adisco.

Vantagens:•Mais adequada a arquivos voláteis do que árvores binárias.•Mais adequada a arquivos voláteis do que árvores binárias.• Nós com muitas chaves tornam paginação desnecessária.• Economia de espaço: poucos ponteiros entre os nós.• Algoritmos são os mesmos que para árvore-B em memóriaprincipal.

Desvantagem:• Não oferece solução econômica para indexação por chavesecundária• Não oferece solução barata para problema de percurso por sequencia de chave.



Árvore de Pesquisa

Árvore B+

• Nas árvores de índices, os nós só possuem, além da chave, um ponteiro para o registro de dados em outro arquivo.

- Nós internos servem só como referência para o percurso.- Chaves de nós internos são repetidas nas folhas.

• Árvore é dividida em Index Set e Sequence Set. • Árvore é dividida em Index Set e Sequence Set.

• Nodos do Sequence Set (folhas) são encadeados.



Árvore de Pesquisa

Árvore B+

Vantagens Árvore B+:

1) Mecanismo para percorrer seqüencialmente o arquivo de registros dedados sem que seja necessário visitar toda a árvore.

2) Mecanismo para percorrer seqüencialmente o arquivo de registros dedados sem que seja necessário ordenar o arquivo de registro de dados.



Árvore de Pesquisa- Vantagens e desvantagens Gerais:

Vantagens:1- Aplicação Imediata: Supondo-se a possibilidade do endereçamento relativo por

registros de arquivos, algoritmos de gerência de árvores podem ser (quase todos) diretamente aplicados a arquivos.

2- Pesquisa rápida: Árvores oferecem tempos de acesso a registros relativamente curtos, com caminhos de busca O(log n). curtos, com caminhos de busca O(log n).

Desvantagens:1- Desperdício de Espaço. Indexação por chave secundária impõe (com exceção

das árvores k-d) necessidade de vários arquivos de índices, um para cada índice. 2- Redundância de valor de chave cara. Quando um valor de chave tem alta

redundância (índices de chave secundária. Ex.: cargo em um arquivo de depto. pessoal) muitos registros do arquivo de índices têm de ser lidos.

3- Manutenção Cara. Em aplicações com frequentes inserções e exclusões de registros e chaves, a manutenção de um arquivo de índices em uma árvore balanceada é extremamente cara.

4- Listagem sequencial cara. Listagem de registros em ordem de chave implica em visitas repetidas a todos os nodos da árvore que não são folha.



Considerações Práticas

- A Árvore B é simples, de fácil manutenção, eficiente e versátil. Permiteacesso sequencial. O custo para recuperação, inserção e exclusão deregistros é logarítmico.

- O Banco de Dados DB2 (IBM) utiliza as estruturas VSAM/ISAM/SAM queoferecem vantagens de no mínimo 50% na memória usando árvores B*.oferecem vantagens de no mínimo 50% na memória usando árvores B*.

- A técnica do transbordamento (overflow) ao invés de particionar e fazer aescolha adequada da quantidade em memória, espera que a mesma tenhasua quantidade superada para remoção.

- O tamanho adequado da ordem da árvore vai depender da característicado computador, estando fortemente vinculada ao tamanho da páginacontrolada pelo SO e a transferência de dados da MS para MP.



Referências

Ziviani, Nivio. Projeto de algoritmos: com implementações em Java e C. Thomson Learning, 2007.

Leiserson, Charles E., Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. Ed. Thomas H. Cormen. The MIT press, 2001.

Documents

5COP096 Teoria da Computação - · PDF file5COP096 –Teoria da Computação Aula 9 –Pesquisa em Memória Secundária Sumário 1) Introdução à Pesquisa em Memória Secundária