Ordenação Externa de
Arquivos – Um exemplo
AULA 16 – Parte II
Profa. Sandra de Amo
GBC053 – BCC
Arquivo Q de 108 páginas em disco
Descrever as operações para ordenar as tuplas do
arquivo Q, distribuídas em 108 páginas em disco.
Cada página tem duas tuplas, portanto o arquivo Q
contém 216 tuplas ao todo.
Dispõe-se de somente 4 páginas na memória principal
para realizar a ordenação de todas as tuplas. Logo,
não será possível carregar as 108 páginas de uma só
vez e aplicar um algoritmo de ordenação interna (tipo
quicksort, bubblesort, etc)
Buffer com 4 páginas
Etapa 0
Arquivo em disco
Ordena os registros das 4 páginas
em memória principal utilizando um
algoritmo de ordenação interna:
quicksort, bubblesort, por exemplo.
Buffer com 4
páginas
Tais algoritmos são do tipo “in place”:
fazem a ordenação utilizando o
próprio espaço ocupado pelos registros,
Sem necessidade de mais páginas
livres para fazer as operações.
Etapa 0
Buffer com 4
páginas
Etapa 0
Subarquivo 1 = 4 páginas ordenadas
Subarquivo 2 = 4 páginas ordenadas
Subarquivo 3 = 4 páginas ordenadas
Buffer com 4
páginas
Etapa 0
Subarquivo 1 = 4 páginas ordenadas
Subarquivo 2 = 4 páginas ordenadas
Subarquivo 3 = 4 páginas ordenadas
Buffer com 4
páginas
...
Subarquivo 27 = 4 páginas ordenadas
Custo da Etapa 0
• Ao final da etapa 0 temos 27 arquivos de
4 páginas cada um.
• Cada um dos subarquivos está ordenado.
• Custo = 2.108 = 216 I/Os
• Na etapa 0, carregamos blocos de 4
páginas cada no buffer.
• Total de blocos carregados = 108/4 = 27
Etapa 1
Agrupa-se os 27 subarquivos de 3 em 3
(3 = B – 1 = 4 - 1)
Cada bloco constituido de 3 subarquivos
tem 3*4 = 12 páginas
Nº de blocos de 12 páginas = 27/3 = 9
Etapa 1
São 9 iterações na etapa 1.
Em cada iteração, cada subarquivo de 12
páginas é carregado, ordenado na
memória principal e gravado de volta no
disco, totalmente ordenado.
A ordenação de cada subarquivo utiliza
um algoritmo de ordenação EXTERNA, de
forma iterativa.
Etapa 1
No final da Etapa 1 temos 9 subarquivos de
12 páginas cada um.
Cada um dos 9 subarquivos está ordenado
Custo da etapa 1 = 2*108 = 216 I/O
Etapa 2
Agrupa-se os 9 subarquivos de 3 em 3
(3 = B – 1 = 4 - 1)
Cada bloco constituído de 3 subarquivos
tem 3*12 = 36 páginas
Nº de blocos de 36 páginas = 9/3 = 3
Etapa 2
São 3 iterações na etapa 2.
Em cada iteração, cada subarquivo de 36
páginas é carregado, ordenado na
memória principal e gravado de volta no
disco, totalmente ordenado.
A ordenação de cada subarquivo utiliza
um algoritmo de ordenação EXTERNA, de
forma iterativa.
Etapa 2
No final da Etapa 2 temos 3 subarquivos de
36 páginas cada um.
Cada um dos 3 subarquivos está ordenado
Custo da etapa 2 = 2*108 = 216 I/O
Etapa 3
Agrupa-se os 3 subarquivos
(3 = B – 1 = 4 - 1)
Temos um único bloco constituído de 3
subarquivos com 3*36 = 108 páginas
Etapa 3
Em uma única iteração o arquivo de 108
páginas é carregado, ordenado na
memória principal e gravado de volta no
disco, totalmente ordenado.
A ordenação do arquivo utiliza um
algoritmo de ordenação EXTERNA, de
forma iterativa.
Etapa 3
No final da Etapa 3 temos 1 arquivo de 108
páginas completamente ordenado
Custo da etapa 3 = 2*108 = 216 I/O
Nº total de etapas = 1 + log3 ( 108/4) =
1 + log3 ( 27) = 1 + 3 = 4
Custo total da ordenação = 4*216 = 864 I/O
Algoritmo
Input: Arquivo A com P páginas (em disco), B = nº de páginas livres no buffer
Output: Arquivo A ordenado (em disco).
1.
M = [P/B]
2.
[A1,...,AM] = Separa_SubArq(A)
3.
For each i = 1, ..., M do
4.
- Lê Ai
5.
- AiOrd = Ordena_INT(Ai)
6.
- Grava AiOrd
7.
M = [M/B-1]
8.
While M ≥ 1 do
9.
- [A1,...,AM] = Separa_SubArq(A)
10.
- Para cada i = 1, ..., M
11.
* Lê Ai
12.
* AiOrd = Ordena_EXT(Ai)
13.
* Grava AiOrd
14.
- A = A1Ord U A2Ord U A3Ord . ... U AMOrd
15.
- M = [M/B-1]
Ordena_Ext
5
10
1
7
13
6
11
18
9
14
21
11
16
22
15
19
30
20
24
28
32
35
22
25
Ai
Uma das 9 iterações da Etapa 1