prova

Prévia do material em texto

Modelo cosequencial - É um processamento coordenado de duas ou mais listas em disco 
para produzir uma única lista em disco. 
Pontos importantes: 
- Inicialização: como abrir os arquivos corretamente 
- Sincronização: como avançar adequadamente em cada arquivo 
- Gerenciamento de condições de fim de arquivo e fim de listas 
- Reconhecimento de erros: nomes duplicados ou fora de ordem 
 
Merging (Intercalação) – União de 2 listas 
Um nome duplicado deve ser gravado na lista uma única vez. As listas devem ser lidas até o 
final. 
Base do processo de ordenação de arquivos muito grandes, cujo índice não cabe na memória 
principal. 
 
Algoritmo: 
- Abre os arquivos lista 1 e lista 2 
- Cria um arquivo de saída 
- Seta a variável existe_nome para verdadeiro 
- Chama o nome 1 da lista 1 
- Chama o nome 2 da lista 2 
- Enquanto existirem nomes, se o nome 1 for menor que o nome 2, então escreve o nome 1 na 
saída e chama o proximo nome da lista 1, se o nome 1 for menor que o nome 2, então escreve 
o nome 2 e chama o proximo nome da lista 2, se os nomes forem iguais, então escreve o nome 
1 e chama o próximo nome da lista 1 e da lista 2. 
 
n1 = read_name(list1); 
n2 = read_name(list2); 
while (!eof(list1) || !eof(list2)) { 
if (n1 < n2) { 
write_name(n1,list3); 
n1 = read_name(list1); 
} 
if (n1 > n2){ 
write_name(n2,list3); 
n2 = read_name(list2); 
} 
else{ 
/* n1 == n2 */ 
write_name(n1,list3); 
n1 = read_name(list1); 
n2 = read_name(list2); 
} 
} 
 
Matching (Intersecção) – Produzir nomes comuns em ambas as listas assumindo que não 
contenham nomes repetidos e que esteja em ordem crescente. 
Termina ao final da menor lista. 
Útil nas operações que fazem combinação (AND) dos resultados após busca em vários índices. 
 
Algoritmo: 
- Abre os arquivos lista 1 e lista 2 
- Cria um arquivo de saída 
- Seta a variável existe_nome para verdadeiro 
- Chama o nome 1 da lista 1 
- Chama o nome 2 da lista 2 
- Enquanto existirem nomes, se o nome 1 for menor que o nome 2, então chama o próximo 
nome da lista 1, se o nome 1 for maior que o nome 2, então chama o próximo nome da lista 2, 
se os nomes forem iguais, então escreve o nome 1 na lista de saída e chama o próximo nome 
da lista 1 e da lista 2. 
 
n1 = read_name(list1); 
n2 = read_name(list2); 
while (!eof(list1) && !eof(list2)) { 
if (n1 < n2) 
n1 = read_name(list1); 
else if (n1 > n2) 
n2 = read_name(list2); 
else{ 
 /* n1 == n2 */ 
write_name(n1,list3); 
n1 = read_name(list1); 
n2 = read_name(list2); 
} 
} 
 
Intercalação em K-vias 
- Pode ordenar arquivos realmente grandes. 
- Processamento cosequencial com mais de 2 arquivos. 
- Geração, leitura e escrita das corridas é seqüencial (mais rápido e pode utilizar fitas). 
Ideia: Le registros para a memória até lotar, ordena os registros na memória (ordenação 
interna) e escreve os registros ordenados em um sub-arquivo chamado de corrida e vai 
repetindo para o resto do arquivo criando várias corridas. Assim é feita a intercalação nas 
corridas criando o arquivo completamente ordenado. 
No keysorting, as chaves tinham que caber em memória e após a ordenação era necessários 
vários seekings para criar o arquivo ordenado. 
 
 
HeapSort 
O HeapSort pode começar a fazer a ordenação a partir da leitura das chaves. 
Ou seja, ele começa a trabalhar a medida que os números são lidos, comparando as chaves a 
medida que elas são encontradas. 
- Cada nó possui uma única chave >= chave do nó pai. 
- Todas as folhas estão em no máximo 2 níveis e todas as folhas do nível mais baixo estão 
mais à esquerda. 
- Heap pode ser mantida em vetor. 
Filho esquerdo = 2i 
Filho direito = 2i+1 
Nó pai = Menor inteiro igual a j/2 
 
Dividida em suas fases: 
- Construção da heap (a partir da leitura das chaves) 
- Escrita das chaves ordenadamente 
 
Algoritmo de inserção: 
- Coloca o valor a ser inserido na última posição da heap. 
- Compara o valor inserido com o valor da chave do nó pai. 
- Troca os valores de posição se o valor inserido é menor que o nó pai. 
- Faz a troca até que o valor inserido seja maior ou igual ao valor do nó pai ou até atingir a raiz. 
 
Algoritmo de remoção: 
- Remove o valor que está na raiz da árvore (a menor chave). 
- Move o elemento da última posição para a raiz. 
- Ajusta a heap com tamanho menor em um elemento. 
- Enquanto K for maior que o menor dos seus filhos, troque K pelo menor filho. 
 
O buffer de entrada evita o número excessivo de seeks, mas não permite que a leitura seja 
feita paralelamente a construção da heap. O uso de múltiplos buffers fazem com que enquanto 
as chaves de um bloco são processadas, os blocos seguintes já podem ser lidos. 
O número de buffers é igual ao número de blocos do arquivo. 
Assim que um bloco de registros é ordenado, ele pode ser escrito para o arquivo de saída, 
enquanto o próximo bloco é processado e assim por diante. 
Toda operação de E/S é seqüencial então o número de operações de seek é o menor possível. 
 
Merge Sort 
Envolve 2 fases: 
- Geração de corridas: Os segmentos do arquivo (corridas) são ordenados em memória RAM, 
usando algum método como HeapSort e gravados em disco. As corridas vão sendo gravadas a 
medida em que são geradas. 
- Intercalação: As corridas geradas são intercaladas formando o arquivo ordenado. 
Essa solução pode ordenar arquivos muito grandes e a geração, leitura das corridas e escrita 
final envolvem apenas acesso seqüencial. 
 
Pontos considerados no custo do MergeSort: 
- Leitura dos registros para a memória para a criação de corridas. 
- Escrita das corridas ordenadas para o disco 
- Leitura das corridas para intercalação 
- Escrita do arquivo final em disco 
 
O tempo de leitura de cada corrida inclui o tempo de acesso a cada bloco (seek + rotation 
delay) + tempo que leva para transferir cada bloco. Escrita idem a leitura. 
 
Maneiras de reduzir o tempo: 
- Usar mais hardware 
- Realizar a intercalação em mais de um passo, reduzindo a ordem de cada intercalação e 
aumenta o tamanho do buffer para cada corrida. 
- Aumentar o tamanho das corridas iniciais ordenadas. 
- Achar meios de realizar I/O simultâneo. 
 
Ao invés de intercalar todas as corridas ao mesmo tempo, o grupo é dividido em grupos 
menores e a intercalação é feita para cada sub-grupo, alocando um espaço maior para cada 
corrida e portanto necessitando de um numero menor de seeks. 
Em geral, corridas iniciais maiores implicam em um numero menor de corridas, o que implica 
em uma intercalação de ordem menor, com buffer maiores, resultando em numero menor de 
seeks. 
 
Replacement Selection – Quantidade de registros do arquivo é maior do que a memória 
interna. 
Dobrar o tamanho das corridas reduz o numero de seeks pela metade. 
É uma solução para aumentar o tamanho das corridas sem usar mais memória. 
Selecionar na memória a menor chave, escreve-la no arquivo e saída e usar seu lugar para 
uma nova chave 
Algoritmo: 
- Ler conjunto de registros e ordenar usando HeapSort. 
- Ao invés de escrever a heap inteira e gerar uma corrida, escreve apenas o registro com 
menor chave. 
- Busca um novo registro no arquivo de entrada e compara com a chave que acabou de ser 
escrita. Se ela for maior, insere o registro normalmente na heap. Se ela for menor que qualquer 
chave já escrita, insere o registro na heap secundaria. 
- Repete o passo anterior enquanto existirem registros a serem lidos. Por fim, transforma a 
secondary heap em primary heap e assim sucessivamente. 
 
Custos de usar replacement selection: Precisa de buffers para I/O e portanto, não pode usar 
toda a memória disponível para ordenação. 
 
Melhorar ordenação externa: 
- Para ordenação interna usar heapsort para formar corridas e Double buffering para sobrepor 
o processamento com input e output. 
- Usar o máximo de memória possível permitindo corridas maiores e buffers maiores na fase deintercalação. 
- Quando o numero de corridas é muito grande, usar intercalação em múltiplos passos, 
aumenta o tempo de transmissão mas diminui o numero de seeks. 
- Utilize Replacement Selection para formação da corrida inicial, especialmente se as corridas 
estiverem parcialmente ordenadas. 
 
Árvores Binárias Paginadas 
Tempo: O(logm n), onde m é o tamanho do nó (página). 
Pior caso para árvore binária completa perfeitamente balanceada: log2 (N+1) 
Versão em páginas: logk+1 (N+1), onde N é o numero total de chaves e k é o numero de chaves 
armazenadas em uma pagina. 
O problema fundamental associado a manutenção de um índice em disco é que o acesso é 
muito lento causando problemas para uma manutenção eficiente. 
Pesquisa binária (melhor solução até agora) requer muitos acessos e pode ficar caro manter 
um índice ordenado para permitir a busca binária. Precisamos que a inserção e eliminação dos 
registros não exijam reorganização total do índice. 
Os ponteiros esq e dir indicam onde estão os registros filhos e a estrutura pode ser mantida em 
memória secundária já que os ponteiros para os filhos dão o RRN das entradas 
correspondentes aos filhos e a sua localização no arquivo. 
 
Vantagens: 
- A ordem lógica dos registros não está associada a ordem física do arquivo. 
- O arquivo física do índice não precisa mais ser mantido ordenado, pois o que interessa é 
poder recuperar a estrutura lógica da árvore através dos campos esq e dir. 
Quando acrescentamos uma nova chave ao arquivo precisa-se saber apenas onde inserir na 
árvore. 
 
Desvantagem da árvore binária: 
- A altura tende a ser muito grande em relação ao numero de nós ou registros que ela contem. 
 
A árvore precisa estar balanceada para que não seja necessários muitos acessos adicionais. 
Nas árvores AVL a diferença de altura entre as duas sub-arvores compartilhando a mesma raiz 
é no máximo 1. 
Árvore AVL não requer ordenação do índice e reorganização na inserção mas há numero 
excessivo de acessos a disco. 
 
Nas árvores binárias paginadas a busca por uma posição especifica no disco é muito lenta, 
mas uma vez encontrada a posição, é possível ler uma grande quantidade de registros 
sequencialmente a um custo relativamente pequeno ecomizando acessos a disco. 
Combinação de busca (seek) lento e transferência rápida!!! 
Uma vez realizado um seek, todos os registros em uma mesma página do arquivo são lidos, ao 
invés de recuperar apenas alguns bytes. 
 
Desvantagens: Maior tempo na transmissão de grande quantidades de dados e a necessidade 
da manutenção da organização da arvore. 
 
Construção Top-Down – Construídas de cima pra baixo, é feita a partir da raiz, sendo que, 
cada vez que uma chave é inserida, a arvore dentro da página é rotacionada, se necessário, 
para manter o balanceamento. 
Difícil garantir que as chaves na página raiz dividam o conjunto de chaves de maneira 
balanceada e que cada pagina contenha um numero mínimo de chaves. 
Construção Bottom-Up – Construídas de baixo pra cima, as chaves na raiz da árvore emergem 
naturalmente, sendo desnecessário setar a raiz e depois encontrar formas de alterá-la. 
 
Árvore-B – é do tipo bottom-up e quando o nó fica cheio, ele é dividido (splitting) e uma chave 
é promovida (promoting). 
As árvores B permitem manter mais de uma chave em cada nó da estrutura, proporciona 
organização de ponteiros de forma que as operações são executadas rapidamente e assegura 
que todas as folhas se encontram no mesmo nível não importando a ordem de entrada dos 
dados. 
São arvores balanceadas desenvolvidas minimizar o numero de acessos ao disco 
maximizando o numero de filhos de um nó. 
Como o custo do acesso a disco é muito alto, toda vez que ele é feito, deve ser aproveitado da 
melhor maneira possível, trazendo o máximo de informação. 
A quantidade de dados utilizados numa árvore B não cabem na memória, por isso é necessário 
paginá-la. 
Para inserir uma nova chave numa folha cheia, o nó folha é dividido (split) em dois nós folhas 
distribuindo as chaves igualmente entre os nós. Então promovemos uma das chaves que estão 
nos limites de separação das folhas. 
 
Inserção (casos): 
1. Uma chave é colocada em uma folha que ainda tem algum espaço 
2. A folha na qual uma chave precisa ser colocada está cheia 
3. A raiz da árvore B está cheia 
A ideia principal é dividir a folha cheia em duas e a chave do meio é promovida para a página 
pai. 
 
A árvore é balanceada com relação a altura e as chaves promovidas sempre são boas 
separadoras. 
Algoritmo é recursivo e trabalha em duas etapas: Operando intercaladamente nas páginas 
inteiras e dentro das páginas. 
A ordem de uma árvore-B é dada pelo número maximo de descendentes que um nó pode 
possuir. 
Ordem m = numero maximo de chaves em uma página é m-1. 
O numero mínimo de chaves de um nó é m/2 – 1. 
Altura máxima e acessos: D <= 1 + log[m/2] ((N+1)/2) 
 
Características de uma árvore B de ordem d 
- A raiz é uma folha ou tem no mínimo 2 filhos 
- Cada nó interno (não folha e não raiz) possui no mínimo d+1 filhos 
- Cada nó tem no máximo 2d + 1 filhos 
- Todas as folhas estão no mesmo nível 
 
N=4 
Máximo de valores por nó = 3 
Nó-folha:Mínimo de valores por nó = 2 
Nó não-folha:Mínimo de filhos = 2 
Máximo de filhos = 4 
 
Operações principais: 
- Pesquisa (Pesquisa externa ao nó: Desce pela arvore a procura da chave de interesse e 
Pesquisa interna ao nó: Faz busca seqüencial ou binária entre as chaves do nó. 
- Percurso 
- Inserção 
- Remoção 
 
Busca: A busca recebe o apontador para o nó raiz e a chave k sendo procurada. Se a chave k 
pertencer a arvore, o algoritmo retorna o nó ao qual ela pertence e o índice dentro do nó 
correspondente a chave procurada. 
 
procedimento buscaB(x, pt, encontrou, pos) 
p:= ptraiz; pt:= y; encontrou := 0; 
enquanto p ≠ y faça 
inicio 
 i:= 1; pos:= 1; pt:= p 
 enquanto i ≤ m faça % m é o número de chaves que a página p contém 
 inicio 
 se x > p.s[i] então i: = i+1; pos: = i + 1 
 senão inicio 
 se x = p.s[i] então 
 p:= y; encontrou := 1 % chave encontrada 
 senão p := p.pont[i-1] % mudança de página 
 i:= m + 2 
 fim 
 fim {enquanto} 
 se i = m + 1 então p:= p.pont[m] 
fim {enquanto} 
 
 
B-TREE-SEARCH(x, k) 
i ← 1 
while i ≤ n[x] and k > keyi[x] do 
i ← i + 1 
if i ≤ n[x] and k = keyi[x] then 
return (x, i) 
if leaf [x] then 
return NIL 
else DISK-READ(ci[x]) 
return B-TREE-SEARCH(ci[x], k) 
 
Particionamento 
- O particionamento da raiz é a unica forma de aumentar a altura da arvore. 
- Em alguns casos o particionamento se propaga para a raiz, então o nó raiz é particionado 
mas como ele não tem pai, cria-se um novo nó que passa a ser a nova raiz. 
 
Concatenação 
- Acontece se as páginas são irmãs adjacentes (tem o mesmo pai) e juntas possuem menos de 
2d chaves. 
 
Acesso Sequencial Indexado 
 
 
Hash 
A idéia básica é criar uma série de sub-listas no lugar de uma única lista maior. A partir da 
aplicaçao de uma determinada função chamada hashing sobre a chave de busca do elemento, 
decide-se em qual das sub-listas o elemento deve ser ou estar armazenado. Procede-se, 
entao, uma busca na sub-lista determinada. Portanto, ao invés de realizar a busca em toda a 
lista, faz-se uma busca num subconjunto da lista. 
Acesso a arquivo O(1), o número de seeks é sempre o mesmo não importa o quanto o arquivo 
possa crescer. 
Não requer ordenação, tornando a inserção tão rápida quanto o acesso. 
A função hashing transforma uma chave k em um endereço que é usado como base para o 
armazenamento e recuperação de registros. 
Hashing estático: o tamanho do espaço de endereçamento não muda. 
Deteriora após muitas inserções e remoções. 
Numero de buckets é fixo, se o arquivo encolhe muito o espaço é desperdiçado e o 
crescimento dos arquivos produz longas cadeias prejudicando a busca. 
Hashing dinâmico: o tamanho do espaço deendereçamento pode aumentar e diminuir. 
Número de buckets pode aumentar. 
 
Diferenças da indexação: 
- Os endereços são aleatórios. 
- Duas chaves podem levar ao mesmo endereço (colisão). 
 
Maneiras de reduzir colisões: 
- Espalhamentos dos registros usando uma função que os distribua por igual entre os 
endereços disponíveis. 
- Utilizar mais memória (espalhar poucos registros em muitos endereços). 
- Utilizar de mais de um registro por endereço. 
 
Objetivo: Função hashing espalhe as chaves da maneira mais uniforme possível entre os 
endereços disponíveis. 
 
Algoritmo: 
- Utilizar código ASCII de cada um dos caracteres para formar um numero. 
- Junta 2 e soma. 
- Dividir o resultado da soma pelo espaço de endereçamento para obter o endereço final. 
a = s MOD N. 
 
Alguns métodos: 
- Pegar o resto da divisão da chave pelo tamanho do espaço disponível. 
- Examinar as chaves em busca de um padrão. 
- Segmentar a chave em diversos pedaços e depois fundir os pedaços. 
- Dividir a chave por um numero. 
- Elevar a chave ao quadrado e pegar o meio. 
- Transformar a base. 
 
É preciso decidir quanto de espaço deve perder para reduzir o numero de colisões. 
 
Resolução de colisões: 
- Encadeamento aberto ou hashing fechado 
- Encadeamento interno ou overflow progressivo 
- Hashing aberto 
 
Overflow Progressivo – procura-se a próximo posição vazia do endereço-base da chave. 
Vantagem: simplicidade 
Desvantagem: agrupamento primário, com estrutura cheia a busca fica lenta, dificulta inserções 
e remoções. 
 
Buckets (cestos) – permitem armazenar mais de um registro em um mesmo endereço, escreve 
e le um cesto por vez. Melhora o desempenho do espalhamento pois aumenta a proporção de 
registros por endereço e diminui o numero de colisões. 
 
- O tamanho lógico do arquivo hash deve ser fixado antes do arquivo ser preenchido com 
registros. 
- Qualquer procedimento de inclusão, remoção ou alteração de um registro não deve quebrar a 
ligação entre o registro e o RRN. 
A inicialização do arquivo aloca espaço física para o arquivo antes de começar a armazenar os 
registros criando um arquivos de espaços vazios aumentando a probabilidade dos registros 
serem armazenados próximos uns dos outros no disco, facilitando o processamento 
seqüencial. 
 
Para trabalhar com hashing é necessário uma função de espalhamento e um mecanismo para 
tratar colisões. 
Melhor caso: O(1) 
Pior caso: O(n) 
 
Por que usar arvore-B ao invés de Hashing? 
- Não permite recuperar todos os elementos em ordem de chave. 
- Não permite recuperar o elemento com a maior ou menor chave, nem o antecessor e 
sucessor de uma determinada chave. 
 
A medida que o arquivo aumenta, torna-se mais freqüente a necessidade de procurar por 
registros fora do seu endereço-base deteriorando o desempenho e precisando de mais 
acessos do que se fosse mantido em arvore-B.