Algoritmo e Estrutura de Dados

∗
Pesquisa em Memória Secundária

Última alteração: 31 de Agosto de 2010

∗ Transparências

Almeida

elaboradas por Wagner Meira Jr, Flávia Peligrinelli Ribeiro, Israel Guerra, Nívio Ziviani e Charles Ornelas

Projeto de Algoritmos – Cap.1 Introdução

Conteúdo do Capítulo
6.1 Modelo de Computação para Memória Secundária
6.1.1 Memória Virtual
6.1.2 Implementação de um Sistema de Paginação
6.2 Acesso Sequencial Indexado
6.2.1 Discos Ópticos de Apenas-Leitura
6.3 Árvores de Pesquisa
6.3.1 Árvores B
6.3.2 Árvores B∗
6.3.3 Acesso Concorrente em Árvores B∗
6.3.4 Considerações Práticas

1

Projeto de Algoritmos – Cap.1 Introdução

Introdução
• Pesquisa em memória secundária: arquivos contém mais registros do que a memória interna pode armazenar.
• Custo para acessar um registro é algumas ordens de grandeza maior do que o custo de processamento na memória primária.
• Medida de complexidade: custo de trasferir dados entre a memória principal e secundária (minimizar o número de transferências).
• Memórias secundárias: apenas um registro pode ser acessado em um dado momento (acesso seqüencial).
• Memórias primárias: acesso a qualquer registro de um arquivo a um custo uniforme (acesso direto).
• O aspecto sistema de computação é importante.
• As características da arquitetura e do sistema operacional da máquina tornam os métodos de pesquisa dependentes de parâmetros que afetam seus desempenhos.

2

Projeto de Algoritmos – Cap.6 Pesquisa em Memória Secundária – Seção 6.1

Modelo de Computação para Memória Secundária Memória Virtual
• Normalmente implementado como uma função do sistema operacional. • Modelo de armazenamento em dois níveis, devido à necessidade de grandes quantidades de memória e o alto custo da memória principal.
• Uso de uma pequena quantidade de memória principal e uma grande quantidade de memória secundária.
• Programador pode endereçar grandes quantidades de dados, deixando para o sistema a