Ficheiros
•
Referências
– Ullman, Principles of Database and Knowledge-Base Systems, Vol 1, Capítulo 6.
– Frakes & Baeza-Yates, Information Retrieval - Data Structures and Algorithms, 1992,
Capítulos 3, 4, 5.
Ficheiro: sequência de bytes armazenados de forma permanente num sistema informático
 informação externa em disco (persistente)
versus
estruturas de dados internas ao espaço de memória central acessível ao programa (volátil)
 abstracção básica para os objectos do sistema operativo
 nível físico da arquitectura de três níveis das bases de dados
• preocupação essencial: eficiência das operações definidas no modelo de dados
Ex: uma selecção deve demorar um tempo proporcional ao número de tuplos da
resposta e não ao tamanho da relação
Ficheiros - 1
Ficheiros
 informação estruturada em registos com um ou mais campos
 valores dos campos são de tipos elementares: inteiros, reais, apontadores (para registos),
cadeias de caracteres de comprimento fixo ou variável
 registos armazenam fisicamente cada um dos objectos básicos dos modelos de dados
• tuplo — cada atributo guardado num campo do registo
• registo lógico (modelo hierárquico ou reticulado) — campos do registo lógico guardados em campos do
registo físico; campos correspondentes a registos virtuais guardados como apontadores para os registos
físicos correspondentes
• objecto — variáveis de instância que são objectos elementares guardados fisicamente no registo; variáveis
que são objectos complexos guardadas como apontadores para os registos correspondentes
 registos são vistos como instâncias de um esquema que indica, para cada campo, o nome e
tipo de dados — formato
 acesso de formas variadas e armazenamento nem sempre sequencial
ficheiro: colecção de registos com o mesmo formato
Ficheiros - 2
Meio físico de armazenamento
 memória virtual
• espaço de endereçamento grande (24 bits - 16M; 32 bits - 4G)
• grande parte efectivamente guardada em dispositivos de memória secundária (disco)
 níveis de memória: memória secundária (disco) versus memória principal (RAM)
- grandes quantidades de dados
- consideração explícita da necessidade de transferência para memória principal
- ordem de grandeza do tempo de transferência tipicamente maior que a do tempo de
processamento
- transferência ao bloco (512 a 4K bytes) — corresponde a um sector do disco
sector
cilindro
Disco
pista
Ficheiros - 3
Custo das operações com ficheiros
 unidade de custo: acesso a um bloco (leitura para memória principal ou escrita no disco)
•
tempo de acesso varia com a posição das cabeças nos cilindros e com a posição
angular do disco (esquemas de numeração intercalada dos sectores para optimizar a
sequência de leitura)
•
utilização de caches (armazéns temporários de blocos na memória principal geridos
pelo sistema operativo ou pelo SGBD) e buffers: alguns acessos a blocos não se
traduzem em acessos a disco
•
abstrai-se destes factores e consideram-se todos os acessos com o mesmo custo
 unidade de medida não é o acesso ao registo
•
um bloco costuma conter vários registos
•
desprezar o tempo de processamento  processar um ou todos os registos de um
bloco tem o mesmo custo
•
objectivo: algoritmos devem minimizar acessos; registos processados ao mesmo
tempo devem estar no mesmo bloco (independentemente do modelo usado no nível
conceptual)
Ficheiros - 4
Apontadores
 apontador para um registo: informação para aceder a um registo rapidamente
• endereço absoluto do início do registo na memória virtual ou no sistema de
endereçamento de um disco
- deslocar registos dentro de um bloco ou conjunto de blocos  alterar todos os
apontadores existentes para esse registo
• apontador como par (b,k)
- b: bloco que contém o registo
- k: chave do registo (campo ou campos que identificam univocamente o registo)
- necessário saber o início de cada registo no bloco e o seu formato, para analisar a
chave
 registos pregados — podem existir apontadores para eles em locais desconhecidos
• registos não pregados podem ser movidos livremente
• registos pregados por endereços absolutos — fixos; por pares bloco-chave — móveis
só dentro do bloco
• apagamento — não pode ser completo
- reutilizar o espaço implicaria devolver o registo errado a um acesso pelo
apontador antigo (quer por endereço absoluto quer por bloco-chave, pois
poderia o novo registo ter a mesma chave)
- bit de apagamento em cada registo — necessário para evitar apontadores
pendentes
Ficheiros - 5
Organização de registos
 para descodificar cada campo: formato indica a distância (offset) do início do registo até ao
início do campo
 bytes adicionais (para além dos valores dos campos) que por vezes aparecem:
• identificação do formato (se for o mesmo para todos os registos de um bloco estes
bytes podem não estar no registo)
• comprimento do registo se for variável
• bit de apagamento
• bit usado/livre, para indicar se o espaço respectivo no bloco contém um registo
•
espaço desperdiçado, para alinhamento dos campos em bytes múltiplos de 4
(eficiência das operações da máquina)
Exemplo 1: registos do tipo Números
• campos:
• NÚMERO - inteiro / chave
• NOME - inicial da designação do número
• QUADRADO - quadrado de NÚMERO (inteiro ou cadeia de dígitos)
0
1
2
3 4
LIXO
INFO NOME
7 8
NÚMERO
11
QUADRADO
total = 12 bytes
Ficheiros - 6
Registos de comprimento variável
 distâncias dependem dos valores e não só do formato
1 tamanho no início de cada campo de comprimento variável (se houver vários, pode ser
interessante ter o tamanho total do registo no seu início)
- menos espaço; mais processamento
2 apontadores no início do registo para o início de cada campo variável e um para o fim
do último
- este esquema pode também ser usado para guardar registos no bloco
Exemplo 1 (cont.): registos de comprimento variável do tipo Números
• campos e bytes informativos:
• 0 - comprimento do registo (max: 255)
• 1 - bits INFO
• 2 - campo NOME
• 3 - desperdiçado para alinhamento
• 4/7 - campo NÚMERO
• 8 - comprimento do campo QUADRADO
• 9/ - campo QUADRADO (cadeia de dígitos)
0
10
1
2
3 4
t
INFO LIXO
7 8
2
9
0
1 4
12
total =10 bytes
1
2
3 4
t
INFO LIXO
7 8
13
9
11
3 1 6 9
total = 12 bytes
Ficheiros - 7
Formatos de bloco
 os registos, dentro do bloco, devem começar num byte múltiplo de 4, para garantir o
alinhamento dos inteiros dentro do registo
 informação extra ao nível do bloco; por exemplo, um apontador para o bloco seguinte
Exemplo 2:
• blocos de comprimento 64 (para facilitar)
• registos do tipo Números (12 bytes)
• apontador de 4 bytes para o bloco seguinte
0
11 12
23 24
35 36
47 48
59 60
63
registo 1 registo 2 registo 3 registo 4 registo 5 apont.
 se se pretender agrupar os bits usado/livre ao nível do bloco, para facilitar a gestão do espaço
é preciso 1 byte no início do bloco  registos ainda com 12 bytes, só 4 registos, bytes 1 a 3
e 52 a 59 desperdiçados
Ficheiros - 8
Formatos de bloco (cont.)
 bloco com registos de comprimento variável
1
comprimento do registo no respectivo início  visitar todos os registos até ao
pretendido
2
directório no início do bloco: vector de distâncias até ao início de cada registo
i.
preceder o directório de um byte a indicar quantos apontadores existem
ii. número fixo de campos com apontadores, preenchendo a 0 os vazios
iii. número variável de campos com apontadores, terminando a lista com 0
Exemplo 2 (cont):
• registos do tipo Números (nº de bytes variável)
• directório do tipo ii. ou iii.
• bytes 26-27 desperdiçados para alinhamento
• poder-se-ia ter usado distâncias só com 1 byte
0 3 4 7 8 11 12 15 16
25 26 27 28
16 28 40 0 registo 2
reg. 13
39 40
53 54 59 60
reg. 100
63
apont.
Ficheiros - 9
Registos semi-pregados
• vantagens do esquema do directório (endereçamento
indirecto)
– lidar com registos de comprimento variável
– permite movimentos dentro do bloco (registos semi-pregados)
• apontador com endereço absoluto refere um campo do directório
• se um registo variar de tamanho, os outros podem-se chegar ao
lado, actualizando as respectivas distâncias
– permite reaproveitar o espaço de registos apagados
• põe-se os bits de apagamento nos campos do directório
• o campo do directório fica pregado, mas o espaço do registo pode
ser reaproveitado por um novo registo referido por um outro
campo
Ficheiros - 10
Índices primários
 estruturas que determinam a localização de registos num ficheiro
 baseados numa chave; objectivo: dada a chave, encontrar rapidamente o registo
 estruturas de dados úteis para índices primários
• ficheiros de dispersão
• ficheiros indexados
• árvores-B
 operações básicas
pesquisa - dada uma chave, encontrar o(s) registo(s) respectivo(s)
inserção - adiciona um registo ao ficheiro; assume-se que o registo ainda não existe,
(pode-se fazer um pesquisa prévia) ou que se aceitam duplicados
apagamento - apaga um registo do ficheiro; processo inclui a pesquisa
modificação - altera o valor de um ou mais campos do registo; processo inclui a pesquisa;
em muitos casos, alterar campos da chave corresponde a um apagamento seguido de
uma inserção
 comparação de eficiência com a organização trivial em monte (heap)
Ficheiros - 11
Organização em monte (heap)
 registos empacotados em blocos sem ordem especial e blocos sem organização especial
 existem, na memória principal, apontadores para todos os blocos (se não couberem, ficam
em blocos da memória secundária e são recuperados quando necessário)
 parâmetros
• n registos no ficheiro (registos pregados: n inclui registos correntes mais os apagados)
• R registos que cabem em cada bloco (em média)
• número mínimo de blocos: n/R
 operações
• pesquisa: n/2R acessos a disco (em média) — percorrer o ficheiro sequencialmente; se
não existir registo com a chave pretendida: n/R acessos
• inserção: 2 acessos, um para leitura do último bloco (ou adição de um novo) e outro para
escrita do bloco modificado
• apagamento: 1 + n/2R; pesquisa mais uma escrita do bloco alterado com o bit de
apagamento activo; se os registos não forem pregados pode-se reutilizar o espaço
- registos de tamanho fixo: transferir o último registo do ficheiro para o buraco aberto e libertar o
último bloco se tiver ficado vazio — mantém o ficheiro compacto
- registos de tamanho variável: deslocar os registos no bloco até haver espaço para transferir um do
último bloco; convém deixar algum espaço livre no bloco para acomodar algum crescimento de
registos
• modificação: semelhante ao apagamento
Ficheiros - 12
Exemplo 3
 Ficheiro: n = 1 000 000 de registos
registo: 200 bytes
bloco: 4096 bytes
• R = 20 registos/bloco
• pesquisa média: 25 000 acessos (50 000 se a pesquisa falhar)
 Supondo tempo de acesso: 0.01 segundo
• tempo de pesquisa: 4 minutos (idem para apagamento e modificação; só a inserção é
rápida)
 Directório de blocos: supondo endereços de 4 bytes
• 4 * 50 000 = 200 000 bytes (50 blocos)
Ficheiros - 13
Ficheiros de dispersão
 Ideia
• dividem-se os registos do ficheiro em áreas (buckets), segundo o valor da chave
• uma função de dispersão calcula directamente o número da área correspondente
• a função toma valores de 0 a B-1; B é o número de áreas
• cada área contém um número (pequeno) de blocos, em heap
• directório de áreas (vector ou ficheiro) com apontadores para os primeiros blocos
• blocos suplementares em lista ligada
• função: distribuir bem os registos pelas áreas; evitar longas cadeias de blocos
 Exemplo 4
0
B=4
h(v) = v mod 4
‡
1
•
17 13 5 29
‡
2
•
2
‡
3
•
23 7 35 19 11
•
[disparate se chaves são números primos]
‡ - apontador vazio
31
‡
Ficheiros - 14
Operações em ficheiros de dispersão
 Pesquisa: calcular o número da área; analisar os blocos da área (heap)
 Inserção: calcular o número da área; inserir no último bloco; se não houver espaço obtémse outro bloco, liga-se à lista e insere-se o registo; pode haver chaves repetidas
 Apagamento: pesquisar; registo pregado: marcar o bit de apagamento; registo não pregado:
compactar (Ex: eliminar o 35 liberta um bloco)
 Modificação: pesquisa, seguida de escrita, que pode implicar deslocamentos se o registo
variar de tamanho
Eficiência
• ficheiro de dispersão com B áreas comporta-se como heap 1/B avos do tamanho do ficheiro
• efeito de aumentar B: custo mínimo é de 1 acesso; aumenta o directório das áreas, que pode ter
que ir para memória secundária, aumentando o número de acessos
• parâmetros: n registos, R registos por bloco, B áreas (heap com n/B registos)
- n/2BR acessos para pesquisa, apagamento e modificação de registo existente
-n/BR acessos se o registo não existir
- pior caso: n/R se todos os blocos estiverem na mesma área
• Exemplo do milhão: n = 1 000 000, R=20, B= 1000
número de registos por área n/B = 1000, i.e. 50 blocos
- em média 25+1=26 acessos por operação ( < 1 segundo)
Ficheiros - 15
Ficheiros indexados
 organização isam (indexed sequential access method ):
registos do ficheiro ordenados por chave (chaves unívocas)
 ordenação numérica, lexicográfica, como bits, chaves compostas (generaliza lexicográfica)
X1 X2 ... Xk < Y1 Y2 ... Ym sse
(Xi, Yi: caracteres ou componentes da chave)
1) k < m e X1 … Xk = Y1 … Yk ou
2) para i  min(k,m) X1=Y1, …, Xi-1 = Yi-1 e código(Xi) < código(Yi)
 tirar partido do facto de os registos estarem ordenados no ficheiro
• metáfora da lista telefónica  só se olha para uma entrada por página e, no fim, percorrese a página onde está a informação
• criar um índice esparso contendo um par (<chave>, <endereço_do_bloco>) por cada bloco
do ficheiro principal; <chave> é inicialmente o valor da menor chave no bloco, mas
apagamentos podem fazê-la estritamente menor; sempre maior que todas as do bloco
precedente; primeiro bloco: chave = - 
ficheiro principal
2 4 5 16
‡
25 37 54 56
‡
68 79 80 88
‡
• • •
índice - 25 68
Ficheiros - 16
Índice
 organização do índice
• primeiro campo de (v,b) é chave para o ficheiro de índice, mantido ordenado
• ficheiro como os outros mas
- registos nunca estão pregados
- para além das operações de inserção, apagamento e modificação no índice, tem que
suportar questões como: "dada uma chave v para o ficheiro encontrar o registo (w,b) no
índice tal que w  v e (w,b) é o último registo do índice ou o registo seguinte (z,b')
tem v < z — w cobre v — e b é o endereço do bloco pretendido"
- organização em ficheiro de dispersão inconveniente — não permite encontrar w que cobre
v, por não estar ordenado
 pesquisa no índice
• pesquisa linear: só para índices pequenos; melhor que pesquisa linear no ficheiro principal
porque tem só n/R registos e são pequenos (cabem mais num único bloco)
• pesquisa binária: começa-se pelo bloco de índice médio (m blocos no total), compara-se com a
chave e escolhe-se a metade que a contém; repetir até obter um só bloco; pesquisa linear neste
para determinar o apontador para o bloco do ficheiro principal; número total de acessos:
2+log m
• pesquisa interpolada: variante da pesquisa binária em que, em vez de se partir o intervalo
sempre ao meio, se usa uma função baseada na distribuição estatística das chaves para
determinar o próximo ponto de divisão (metáfora da lista telefónica)
Bi; i = m f(v,v1,v2)
fracção
- resultado: 3 + log log m = 6 incluindo 2 acessos ao ficheiro principal
Ficheiros - 17
Exemplo do milhão
 nº registos n = 1 000 000
R = 20 registos/bloco
bloco = 4096 registo = 200 chave = 20
ficheiro principal = 50 000 blocos
índice = 50 000 registos
registo do índice = 20 + 4 = 24
chave apontador
máximo: 170 registos num bloco
escolha: 150 registos apenas, para permitir bits de usado/livre
m = 50 000/150 = 334 blocos de índice
 Conclusão
• pesquisa linear: 168 acessos em média + 2 no ficheiro principal
• pesquisa binária: 2 + log 334 = 11 acessos
 Comparação com função de dispersão
• se número de áreas for semelhante a número de blocos, 3 acessos — um para o
directório de áreas e dois para ler e escrever o respectivo bloco
• desvantagem: perguntas que envolvam uma gama de chaves relativamente grande
obrigam a percorrer quase todas as áreas do ficheiro de dispersão, enquanto que uma
organização isam, depois de encontrar o primeiro bloco da resposta, fornece os
outros sem mais trabalho.
Ficheiros - 18
Operações com registos não pregados
 índice também tem registos não pregados: operações semelhantes, usando estratégias já
descritas
 inicialização
i)
ordenar os registos e distribui-los pelos blocos deixando uma percentagem (20%)
livre para futuras necessidades
ii) criação do ficheiro de índice (exame do primeiro registo de cada bloco do ficheiro
principal) (-  como primeira chave; percentagem de espaço livre)
iii) criar um directório com os endereços dos blocos de índice
 pesquisa
•
examinar o índice com uma das técnicas já referidas e obter o valor w que cobre a
chave pretendida v; seguir o apontador respectivo para o ficheiro principal
 modificação
•
pesquisa seguida de reescrita do bloco alterado
•
se alteração afectar a chave, fazer antes um apagamento seguido de inserção
Ficheiros - 19
Mais operações
 inserção
•
pesquisa para descobrir o bloco de destino
•
introdução do novo registo, sem prejuízo da ordenação dos outros que podem ser
deslocados para a direita para criar espaço
•
se o bloco estiver cheio e antes de considerar a criação de um novo, pode examinarse os adjacentes; havendo espaço, desloca-se um ou mais dos registos extremos para
esse bloco, actualizando o valor da chave no índice, os bits usado/livre
•
não havendo espaço, reclama-se um novo bloco que recebe cerca de metade dos
registos do que tinha enchido e lhe fica adjacente; insere-se um novo registo no
índice, com o endereço e a chave do novo bloco, usando estratégia semelhante à do
ficheiro principal
 apagamento
•
estratégia simples: deslocar os registos à direita do eliminado para a esquerda, para
compactar; ajustar os bits de usado/livre
•
se o bloco ficar vazio, devolvê-lo ao sistema e eliminar o registo correspondente no
índice, usando a mesma estratégia
Ficheiros - 20
Manipulação de ficheiros isam
 ficheiro inicial com registos do tipo Números
(20% de espaço livre)
ficheiro principal
2 4 5 16
‡
25 37 54 56
‡
68 79 80 88
‡
• • •
- 25 68
índice
 após a inserção de 19, 58 e 31
ficheiro principal
2 4 5 16 19
‡
25 31 37 54 56
‡
58 68 79 80 88
‡
• • •
- 25 58
índice
Ficheiros - 21
Ficheiros isam (cont)
ficheiro principal
 após a inserção de 52
2 4 5 16 19
‡
25 31 37
‡
52 54 56
‡
58 68 79 80 88
‡
• • • •
- 25 52 58
índice
Ficheiros - 22
Registos pregados
 registos pregados  não é possível manter a ordem dentro dos blocos
 encara-se cada bloco como o início de uma área; inserções resultam em adicionar blocos às
áreas em lista ligada
 o índice não muda, nesta organização; até que se proceda a uma reorganização geral com
aumento do número de áreas
 operações
•
inicialização: semelhante ao caso não pregado
•
pesquisa: também semelhante, mas tem que estender a pesquisa linear a todos os
blocos da área
•
inserção: ocorre sempre na área determinada pela pesquisa, num bloco já existente ou
adicionando um novo
•
apagamento: usar a pesquisa para encontrar o registo; ligar o bit de apagamento;
manter o bit usado/livre por causa dos apontadores que possam existir
•
modificação: se não alterar a chave, basta usar a pesquisa; se alterar, apaga-se e
insere-se, mas é necessário deixar o bit de apagamento na posição anterior e um
apontador de seguimento para o novo local
 para manter a ordenação, podem juntar-se apontadores com a função de indicar a sequência,
que indicam não só o bloco como também a distância dentro do bloco
Ficheiros - 23
Árvores-B
 motivação: sendo um índice um ficheiro, podem-se construir índices de índices até que o
último caiba num bloco
• uma técnica possível — árvores equilibradas (já estudadas); há muitas variantes
• nesta perspectiva, o ficheiro principal pode fazer parte da árvore — nível inferior,
estando os seus blocos sujeitos às regras das árvores B, embora com uma estrutura
diferente da dos nós do índice, pois não precisa de apontadores e o número de registos
por bloco poderá ser diferente
• os registos não podem estar pregados; a árvore-B funciona como um índice esparso
• a informação do registo está toda no nível de baixo, para permitir ter a maior parte do
processamento do índice no menor número de blocos possível, eventualmente em
memória central; o acesso aos dados fica todo ao mesmo nível e em memória
secundária
 contrastar com a família de árvores-B obtidas por modificação das árvores binárias de
pesquisa: aí os nós têm dados e separam as subárvores como o fazem as binárias, só com a
restrição de todas as folhas estarem à mesma profundidade; os nós são todos iguais, embora
as folhas não precisem de apontadores — estrutura mais adaptada a residir em memória
central do que em disco
Ficheiros - 24
Análise temporal
 parâmetros da árvore:
• d - número mínimo de filhos num nó interior (índice), excepto a raiz (máx: 2d-1)
• e - número mínimo de filhos numa folha (ficheiro principal), (máx: 2e-1)
• n - número total de registos
• i - profundidade da árvore+1
 não há mais do que n/e folhas; não há mais do que n/de pais de folhas; n/ed^2 pais de pais
de folhas — n  e d^(i-1) —
i  1 + log d (n/e)
• numa pesquisa bastam i leituras; nas inserções e apagamentos o número varia
• pode-se considerar 2 + log d (n/e)
 Exemplo do milhão
• blocos de 4096 bytes, 1 000 000 registos
• registos com 200 bytes e número ímpar de registos/bloco dá e=10, nós de ordem 19
• chaves: 20 bytes, apontadores: 4, primeira chave não se armazena, d=86, ordem 171
• número esperado de acessos por operação: 2 + log 86 (1 000 000/10) < 5
• superior ao caso de um nível de indexação, excepto se se conseguir boa interpolação
• inferior à função de dispersão mas permite tratamento ordenado
Ficheiros - 25
Índices densos
 ficheiros de dispersão (1 bloco por área semi-vazio) e árvores equilibradas (nós a 75%)
funcionam bem se tiverem uma percentagem significativa de espaço livre
 a heap mantém todos os blocos do ficheiro principal cheios excepto o último; problema:
encontrar eficientemente um registo no meio do caos
• solução: índice denso, com um registo (v,p) por cada valor v de chave no ficheiro
principal, sendo p um apontador para o respectivo registo
• qualquer estrutura de índice serve para os índices densos
• um índice esparso só tem uma chave por cada bloco do ficheiro principal
 qualquer operação na heap corresponde a uma pesquisa pelo índice denso seguido de mais 1
ou 2 acessos ao ficheiro principal; inserir um registo é inseri-lo no fim da heap e inserir o par
(v,p) no índice denso
 justifica-se usar índices densos, apesar dos 2 acessos suplementares, quando
• os registos do ficheiro principal estão pregados, mas os do índice não precisam de estar,
o que permite uma organização mais eficiente no índice do que seria possível no
ficheiro principal
• se os registos do ficheiro principal forem grandes, pode o número total de blocos usado
no índice denso ser inferior ao necessário para um índice esparso ou árvoreB
 Exemplo do milhão
índice denso com árvore-B: d = 86, e = 85  acessos = 2 + log 86 (1 000 000/85) + 2=6
mas heap poupa 25% do espaço no ficheiro principal, o que dá 13% no total se se subtrair
12% para as folhas do índice denso(24 bytes cada)
Ficheiros - 26
Sumário de métodos de acesso
Organização
Tempo por operação
Vantagens/desvantagens
Dispersão
3 se áreas = 1 bloco
Índice isam
2+ log (n/de) para
pesquisa binária
3+ log log (n/de)
interpolação
2 + log d(n/e)
Método mais rápido
Aumenta espaço.
Se o ficheiro cresce atrasa, Obriga a procurar área.
pois as áreas ficam grandes.
Mau em acesso ordenado.
Acesso rápido com
Idem.
interpolação.
Acesso ordenado.
Árvore-B
Índice denso
 2 + operação no
índice denso.
Registos pregados
Acesso rápido.
Acesso ordenado.
Usar árvore B como
índice denso.
Blocos com buracos.
Mais lento 1 ou 2 acessos.
Pode poupar espaço.
Sem problemas.
Ficheiros - 27