File organisation and access
Introduzido| English | Significado |
|---|---|
| file organisation/faɪl ˌɔːɡənaɪˈzeɪʃn/ | organização de arquivos |
| access method/ˈækses ˈmeθəd/ | método de acesso |
| serial file/ˈsɪərɪəl faɪl/ | arquivo serial |
| sequential file/siːˈkwenʃl faɪl/ | arquivo sequencial |
| key field/kiː fiːld/ | campo-chave |
| direct access/daɪˈrekt ˈækses/ | acesso direto |
| sequential access/siːˈkwenʃl ˈækses/ | acesso sequencial |
| random file/ˈrændəm faɪl/ | arquivo aleatório |
Por que o trabalho noturno do banco levou a noite toda
- Até a década de 1980, as contas de um banco viviam em fita magnética. Uma fita só pode ser lida de uma extremidade à outra, então as transações do dia eram organizadas durante a noite e todo o arquivo mestre era lido do início ao fim, uma vez, para aplicá-las.
- Pedir o saldo de um cliente no meio da tarde resultava na resposta: não antes de amanhã. A organização do arquivo, não a velocidade do computador, decidia o que o banco podia oferecer.
- Discos permitiram uma organização diferente: calcular onde um registro está a partir de sua chave e pular até lá. É isso que permite que um caixa eletrônico responda em um segundo.
- Esta lição é organização de arquivos 文件组织, os dois métodos de acesso 访问方式, e como escolher entre o que o programa faz principalmente.
Três organizações
- Um arquivo serial 串行文件 armazena registros na ordem em que foram adicionados, sem ordenação. Adicionar é rápido; pesquisar significa ler do início. Usado para logs e rastreamentos de auditoria.
- Um arquivo sequencial 顺序文件 armazena registros ordenados por um campo-chave 键字段. Pesquisar é mais rápido, pois você pode parar cedo ou fazer busca binária; inserir é lento, pois registros posteriores devem mudar de lugar. Usado para arquivos mestres atualizados em lote.
- Um arquivo aleatório, ou de acesso direto, 随机文件 armazena cada registro em uma posição calculada a partir de sua chave de registro, geralmente por um hash. Lookup por chave é muito rápido; ler em ordem de chave é incômodo. Usado para tabelas de lookup grandes e contas de clientes.

Serial: ordem de chegada, nada mais

Sequencial: os mesmos registros, em ordem de chave
Os dois métodos de acesso
- Acesso sequencial 顺序存取 lê do início do arquivo até o registro desejado. É o único acesso que um arquivo serial permite, e é como um arquivo sequencial é processado em lote.
- Acesso direto 直接存取 salta diretamente para uma posição conhecida sem ler o que vem antes. É como um arquivo aleatório é lido, e um arquivo sequencial também pode ser lido diretamente quando a posição de uma chave é conhecida ou indexada.
- Então o pareamento do programa é: acesso sequencial para arquivos seriais e sequenciais; acesso direto para arquivos sequenciais e aleatórios.

Aleatório: a chave diz onde olhar
File access route
Follow a file from storage to program and back safely.
A serial file stores records:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Serial files keep records in arrival order — fast to append, slow to search. Sequential files are sorted by key.
Match each file organisation to how it stores records.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Serial = arrival order; sequential = sorted; random = hashed position; indexed-sequential = sorted + an index.
A random (direct-access) file places each record:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A key is converted (often by a hash) to a position, so a single-key lookup is very fast.
What is the difference between a serial file and a sequential file?
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Order of arrival versus sorted by key. That single difference is what makes a sequential file searchable early and slow to insert into.
Exemplo resolvido: escolha a organização
- Um programa de folha de pagamento lê todos os registros de funcionários uma vez por mês, em ordem de número de funcionário, para produzir holerites. Qual organização e acesso, e por quê?
- Organização sequencial com acesso sequencial: todo registro é processado, então não há ganho em pular, e mantê-los em ordem de chave significa que os holerites saem em ordem sem etapa de ordenação.
- Um caixa eletrônico precisa buscar uma conta pelo seu número em menos de um segundo. Organização aleatória com acesso direto: a posição é calculada a partir do número da conta, então exatamente uma leitura é necessária em vez de uma pesquisa através de milhões.
- Um servidor web anexa uma linha por solicitação a um log. Serial: apenas anexo importa, e anexo ao final é a coisa mais rápida que um arquivo serial faz.
A sequential file can be read by sequential access and also by direct access.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Sequential access serves serial and sequential files; direct access serves sequential and random files. Only a serial file is limited to one method.
Put the steps of fetching one account from a random file in order.
Dificuldade 3/5 · Moedas 200 + pequeno bônus na primeira conclusão hoje
No searching happens at all: the key is turned into a position and read once. The final check catches a collision.
As compensações, lado a lado
| serial | sequencial | aleatório | |
|---|---|---|---|
| ordem dos registros | conforme adicionado | ordenado por chave | calculado a partir da chave |
| adicionar um registro | rápido, anexo | lento, registros mudam | rápido, se o slot estiver livre |
| encontrar um registro | lento, ler tudo | mais rápido, pode parar cedo | mais rápido, uma leitura |
| ler em ordem de chave | precisa ordenar | natural | precisa ordenar |
- A resposta certa sempre é argumentada a partir da operação dominante: o que este programa faz mais?
Sequential file organisation is well suited to processing every record in turn.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Direct access suits looking up a single record.
Match each situation to the file organisation that suits it.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Append only, process everything in order, or look one record up: the dominant operation picks the organisation.
Exemplo resolvido: justifique uma mudança
- O arquivo de livros de uma biblioteca é serial. Pesquisar um título é lento. Sugira uma mudança e justifique-a.
- Reorganizar como um arquivo aleatório, hashando o ISBN para um endereço, para que uma busca se torne uma leitura direta única em vez de uma varredura de todo o arquivo.
- Se a biblioteca também imprimir um catálogo em ordem de título, uma organização sequencial por título serve razoavelmente bem a ambos: o catálogo não precisa de ordenação e uma busca pode parar cedo ou fazer busca binária.
- Nomeie a organização, nomeie o método de acesso e vincule ambos a uma operação mencionada na questão.
To produce reports in key order, the best file organisation is:
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
A sequential file is already in key order, so reading it sequentially gives an in-order report.
A file organisation is chosen by looking at the program's ____ operation.
Dificuldade 1/5 · Moedas 100 + pequeno bônus na primeira conclusão hoje
Every organisation is fast at something and slow at something else, so the operation done most often decides.
O que a chave precisa ser e por que o hashing falha
- O acesso direto precisa de uma chave, e a chave deve ser única para um registro. Um sobrenome não é uma chave; um número de cliente é.
- O hashing transforma essa chave em um endereço de registro em um único cálculo, então uma única leitura alcança o registro independentemente do tamanho do arquivo.
- Duas chaves diferentes podem hashar para o mesmo endereço. Isso é uma colisão, e não é um defeito no algoritmo: é inevitável uma vez que há mais chaves possíveis do que endereços.
- A correção citada no gabarito é uma área de overflow, ou armazenar um ponteiro no endereço para uma cadeia de registros que compartilham ele. Uma colisão, portanto, custa uma leitura extra, não um registro perdido.
- Então a comparação honesta é: o hashing oferece acesso quase constante até que o arquivo encha, e seu desempenho degrada à medida que as colisões se acumulam. O acesso sequencial nunca degrada, mas nunca foi rápido.
Two records hash to the same address. Which are true? Select todos that apply.
Dificuldade 2/5 · Moedas 140 + pequeno bônus na primeira conclusão hoje
Nothing is lost; a collision costs one extra read. It is unavoidable in principle, because there are always more possible keys than addresses.
Marcas que escapam
- Serial é ordem de chegada; sequencial é ordenado por uma chave. Eles não são sinônimos, e o exame testa exatamente essa diferença.
- Organização é como os registros estão dispostos; acesso é como o programa alcança um. Uma questão nomeia um ou outro.
- Um arquivo sequencial suporta ambos os métodos de acesso; um arquivo serial suporta apenas acesso sequencial.
- Justifique pela operação dominante, não por "é mais rápido". Diga mais rápido para quê, e por quê.
Entendeu?
- serial: ordem de adição, append rápido, busca lenta, usado para logs · sequential: ordenado por um campo de chave, bom para processamento em lote e saída em ordem · random: posição calculada a partir da chave do registro, uma leitura para encontrar um registro
- acesso sequencial lê do início; acesso direto salta para uma posição
- acesso sequencial serve arquivos serial e sequencial; acesso direto serve arquivos sequenciais e aleatórios
- escolha pela operação dominante: processar tudo, buscar um, ou apenas appending