Estruturas de Arquivo Físicas vs. Lógicas

Um arquivo é um conjunto de dados persistente sob um nome. Duas perguntas se misturam com facilidade: o que o programa enxerga e como esses dados ocupam o disco. A primeira é a estrutura lógica; a segunda, a estrutura física. O mesmo conteúdo pode ser uma fita de bytes, uma lista de registros ou uma árvore, e ainda assim ocupar o disco de jeitos diferentes.

O programa pede "o registro da matrícula $1042$". Quem traduz isso para bloco — a unidade de transferência do disco — e deslocamento é a organização física. O método de acesso é uma terceira peça: a mesma organização admite varrer o próximo, pular para um endereço de bloco, ou recuperar pela chave. No sequencial restrito, recomeçar é rewind, não um salto para o início.

Campo, registro e arquivo

Um campo é o menor item nomeado: um inteiro de matrícula, um nome, um preço. Um registro é o agrupamento de campos que descreve uma entidade — um aluno, uma venda. O arquivo é a coleção desses registros ou, no caso mais pobre, só dos bytes.

Sem registro, o programa teria de saber sozinho onde termina o nome e começa a nota. O registro fixa essa fronteira: o campo é um atributo, o registro é a entidade, o arquivo é a coleção.

O setor, o cilindro e a trilha — a geometria do disco magnético — não fazem parte dessas definições. O programa quase nunca pensa nessa geometria; ele pede um registro. A organização física é quem calcula bloco e deslocamento.

Três visões lógicas

O mesmo conteúdo admite três organizações lógicas. São três jeitos de o programa — ou a biblioteca — interpretar o mesmo arquivo.

Sequência de bytes. O arquivo é um vetor de octetos, do deslocamento $0$ até $n-1$. Não há registro embutido: quem interpreta o layout é o programa — um texto, um arquivo sem estrutura interna. O sistema de arquivos, a camada que persiste o nome e os bytes, só sabe ler, escrever e posicionar em deslocamentos.

Pedir "o terceiro aluno" não faz sentido para o sistema. Faz sentido "os $4$ bytes a partir de $8$", se o programa já tiver essa conta.

Sequência de registros. O arquivo é uma lista de registros. O registro pode ter tamanho fixo (todos com $L$ bytes; o $i$-ésimo começa em $i\cdot L$) ou tamanho variável (um campo de comprimento, ou um delimitador, antecede o próximo).

Em arquivo de registros o tamanho pode ser variável ou fixo. No variável, cada entrada é registro do mesmo jeito; muda só o endereço do sucessor. Quem trata o arquivo como registros — o sistema ou a biblioteca — já sabe onde um termina e o outro começa.

Árvore. Os registros — ou as páginas que os guardam — são nós com filhos. Caminhar pela chave escolhe um ramo. Essa visão dá escolha de ramo: dá para descer por um caminho sem varrer a fita. A sequência de bytes é a visão mais livre: o sistema não impõe layout.

O custo é o layout mais irregular. Por isso a árvore costuma usar registros de tamanho variável: cada nó carrega um número variável de chaves e ponteiros. Esse é o caso típico na prática, sem ser obrigatório. O que define a visão é a escolha de ramo.

A sequência de bytes é a mais flexível das três porque bytes só oferecem posição: quem interpreta o conteúdo é o programa. A fita de registros já impõe o próximo e, se os registros forem fixos, o $i$-ésimo por aritmética. A árvore impõe escolha de ramo a cada nó: a chave decide o filho, e os irmãos do outro lado ficam de fora — acesso mais estruturado que a sequência de bytes.

Em tamanho fixo e variável, a diferença está no endereço do sucessor. Fixo: o endereço do registro $i$ é $i\cdot L$; inserir no meio desloca tudo em múltiplos de $L$. Variável: o sucessor só se conhece depois de ler o comprimento ou o delimitador; um registro maior que o buraco não cabe sem gravar noutro lugar ou reescrever.

O mapa físico

No disco, três arranjos clássicos respondem "onde está o registro da chave $k$". O arquivo direto é o nome clássico do arranjo hash: a chave passa por uma função e cai num balde, o conjunto de registros que compartilham o mesmo $h(k)$.

Hash não atende "chave entre $a$ e $b$". A função espalha valores próximos por baldes distintos: $h(10)$ e $h(11)$ não são vizinhos. Percorrer o intervalo exigiria visitar baldes sem relação de ordem. Intervalo é trabalho de arquivo ordenado ou de índice em árvore.

Não confunda arquivo sequencial com acesso sequencial. Dá para varrer um arquivo hash em ordem de balde — sequencial no dispositivo — sem que a organização seja sequencial. A organização diz onde o registro está; o método de acesso diz como o endereço chega ao dispositivo.

Métodos de acesso

Independentemente da organização, o método de acesso é o contrato entre o programa e o dispositivo.

• Sequencial. Lê-se o próximo registro depois do atual. O "endereço" é a posição na sequência; um marcador — deslocamento ou número de registro — avança de um em um. Serve para separar um registro do seguinte e para recuperar na ordem em que estão gravados. Em fita, muitas vezes é o único método barato.
• Direto. Cada bloco tem um endereço exclusivo, derivado da posição física — número do bloco, ou o tripleto cilindro/trilha/setor. Dado o endereço, o dispositivo vai lá sem passar pelos vizinhos. Quando o custo de alcançar um bloco não depende de qual bloco é, fala-se em acesso aleatório: o primeiro e o último bloco custam o mesmo. Disco com endereçamento por bloco se aproxima disso; fita, não.
• Associativo. Recupera-se um registro a partir de parte do conteúdo — um campo-chave — e não a partir da posição. O endereço lógico é a própria chave, ou um pedaço dela. Se a busca não exigir a chave inteira, pode usar só um prefixo: "nome começa com par" em vez de "registro $3$".

Método de acesso e organização são coisas distintas. O mesmo arquivo hash admite varrer o próximo balde (sequencial), ir ao bloco cujo número veio de $h(k)$ (direto) e responder "qual registro tem esta chave" (associativo). Quem muda é a pergunta feita ao arquivo.

Não confunda direto com associativo. Direto parte de um endereço físico já conhecido. Associativo parte do conteúdo e só então chega a um endereço — a chave é o pedido, não o número do bloco. No sequencial restrito falta ainda a operação de recomeçar: o marcador só anda para a frente.

Rewind no sequencial restrito

Fita com quatro ids. Nesta ordem: $10$, $31$, $71$ e $88$. O marcador começa no primeiro.

Três pares, doze bytes

Um arquivo guarda três pares $(\text{id}, \text{nota})$, cada um com $4$ bytes, sem cabeçalho. Os ids são $7$, $12$ e $19$; as notas, $8$, $5$ e $10$. O total é $12$ bytes.

Para o sistema de arquivos isso é só um vetor de $12$ bytes. Pedir "a nota do id $19$" não é operação do sistema.

Quatro produtos no catálogo

Um arquivo tem quatro produtos. Cada um traz id (inteiro de $2$ bytes), nome e preço (inteiro de $2$ bytes). Os nomes são fio ($3$ letras), prego ($5$), cabo ($4$) e parafuso ($8$); os ids são $10$, $31$, $71$ e $88$; os preços, $12$, $4$, $8$ e $20$.