File organisation and access · Organização e acesso a arquivos
| English | Português |
|---|---|
| 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 |
Why the bank's night job took all night
- Into the 1980s a bank's accounts lived on magnetic tape. A tape can only be read from one end to the other, so the day's transactions were sorted overnight and the whole master file was read start to finish, once, to apply them.
- Ask for one customer's balance in the middle of the afternoon and the answer was: not until tomorrow. The organisation of the file, not the speed of the computer, decided what the bank could offer.
- Disks made a different organisation possible: compute where a record is from its key and jump there. That is what lets a cash machine answer in a second.
- This lesson is file organisation 文件组织, the two access methods 访问方式, and how to choose from what the program mostly does.
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.
Three organisations
- A serial file 串行文件 holds records in the order they were added, with no sorting. Appending is fast; searching means reading from the start. Used for logs and audit trails.
- A sequential file 顺序文件 holds records sorted by a key field 键字段. Searching is faster, because you can stop early or binary-search; inserting is slow, because later records must shift. Used for master files updated in batch.
- A random, or direct-access, file 随机文件 holds each record at a position computed from its record key, usually by a hash. Lookup by key is very fast; reading in key order is awkward. Used for large lookup tables and customer accounts.
Serial: order of arrival, nothing more
Sequential: the same records, in key order
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
The two access methods
- Sequential access 顺序存取 reads from the start of the file to the record wanted. It is the only access a serial file allows, and it is how a sequential file is processed in a batch.
- Direct access 直接存取 jumps straight to a known position without reading what comes before. It is how a random file is read, and a sequential file can also be read directly when the position of a key is known or indexed.
- So the syllabus pairing is: sequential access for serial and sequential files; direct access for sequential and random files.
Random: the key tells you where to look
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 · Rota de acesso a arquivo
Follow a file from storage to program and back safely. · Siga um arquivo do armazenamento ao programa e de volta com segurança.
A serial file stores records: · Um arquivo serial armazena registros:
Serial files keep records in arrival order — fast to append, slow to search. Sequential files are sorted by key. · Arquivos mantêm registros na ordem de chegada — rápido para adicionar, lento para pesquisar. Arquivos sequenciais são ordenados por chave.
Match each file organisation to how it stores records. · Associe cada organização de arquivo à forma como armazena registros.
Serial = arrival order; sequential = sorted; random = hashed position; indexed-sequential = sorted + an index. · Serial = ordem de chegada; sequencial = ordenado; aleatório = posição hash; indexado-sequencial = ordenado + um índice.
A random (direct-access) file places each record: · Um arquivo aleatório (acesso direto) posiciona cada registro:
A key is converted (often by a hash) to a position, so a single-key lookup is very fast. · Uma chave é convertida (muitas vezes por um hash) em uma posição, então uma consulta de chave única é muito rápida.
What is the difference between a serial file and a sequential file? · Qual é a diferença entre um arquivo serial e um arquivo sequencial?
Order of arrival versus sorted by key. That single difference is what makes a sequential file searchable early and slow to insert into. · Ordem de chegada versus ordenado por chave. Essa única diferença faz com que um arquivo sequencial possa ser pesquisado precocemente e seja lento para inserção.
Worked example: choose the organisation
- A payroll program reads every employee record once a month, in employee-number order, to produce payslips. Which organisation and access, and why?
- Sequential organisation with sequential access: every record is processed, so there is nothing to gain from jumping about, and storing them in key order means the payslips come out in order with no sorting step.
- A cash machine must fetch one account by its number in under a second. Random organisation with direct access: the position is computed from the account number, so exactly one read is needed instead of a search through millions.
- A web server appends one line per request to a log. Serial: only appending matters, and appending to the end is the fastest thing a serial file does.
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. · Um arquivo sequencial pode ser lido por acesso sequencial e também por acesso direto.
Sequential access serves serial and sequential files; direct access serves sequential and random files. Only a serial file is limited to one method. · O acesso sequencial serve arquivos seriais e sequenciais; o acesso direto serve arquivos sequenciais e aleatórios. Apenas um arquivo serial é limitado a um método.
Put the steps of fetching one account from a random file in order. · Coloque as etapas para buscar uma conta em um arquivo aleatório na ordem correta.
No searching happens at all: the key is turned into a position and read once. The final check catches a collision. · Nenhuma busca ocorre: a chave é transformada em uma posição e lida uma vez. A verificação final captura colisões.
The trade-offs, side by side
| serial | sequential | random | |
|---|---|---|---|
| order of records | as added | sorted by key | computed from key |
| adding a record | fast, append | slow, records shift | fast, if the slot is free |
| finding one record | slow, read all | faster, can stop early | fastest, one read |
| reading in key order | needs a sort | natural | needs a sort |
- The right answer is always argued from the dominant operation: what does this program do most?
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. · A organização de arquivo sequencial é bem adequada para processar cada registro em sequência.
Direct access suits looking up a single record. · O acesso direto é adequado para consultar um único registro.
Match each situation to the file organisation that suits it. · Associe cada situação à organização de arquivo que a adequa.
Append only, process everything in order, or look one record up: the dominant operation picks the organisation. · Append apenas, processe tudo em ordem ou procure um registro: a operação dominante escolhe a organização.
Worked example: justify a change
- A library's book file is serial. Searching for one title is slow. Suggest a change and justify it.
- Reorganise as a random file, hashing the ISBN to an address, so a search becomes one direct read instead of a scan of the whole file.
- If the library also prints a catalogue in title order, a sequential organisation by title serves both reasonably: the catalogue needs no sort and a search can stop early or binary-search.
- Name the organisation, name the access method, and tie both to an operation the question mentions.
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: · Para produzir relatórios em ordem de chave, a melhor organização de arquivo é:
A sequential file is already in key order, so reading it sequentially gives an in-order report. · Um arquivo sequencial já está em ordem de chave, então lê-lo sequencialmente produz um relatório em ordem.
A file organisation is chosen by looking at the program's ____ operation. · Uma organização de arquivo é escolhida olhando para a operação ____ do programa.
Every organisation is fast at something and slow at something else, so the operation done most often decides. · Toda organização é rápida em algo e lenta em outro, então a operação feita com mais frequência decide.
What the key has to be, and why hashing breaks
- Direct access needs a key, and the key must be unique to one record. A surname is not a key; a customer number is.
- Hashing turns that key into a record address in one calculation, so a single read reaches the record however large the file is.
- Two different keys can hash to the same address. That is a collision, and it is not a fault in the algorithm: it is unavoidable once there are more possible keys than addresses.
- The fix named in the mark scheme is an overflow area, or storing a pointer at the address to a chain of records that share it. A collision therefore costs one extra read, not a lost record.
- So the honest comparison is: hashing gives near-constant access until the file fills up, and its performance degrades as collisions build. Sequential access never degrades but was never fast.
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 all · todos that apply. · Dois registros hasham para o mesmo endereço. Quais são verdadeiras? Selecione todas que se aplicam.
Nothing is lost; a collision costs one extra read. It is unavoidable in principle, because there are always more possible keys than addresses. · Nada é perdido; uma colisão custa uma leitura extra. É inevitável em princípio, pois sempre há mais chaves possíveis do que endereços.
Marks that slip away
- Serial is order of arrival; sequential is sorted by a key. They are not synonyms, and the exam tests exactly that difference.
- Organisation is how the records are laid out; access is how the program reaches one. A question names one or the other.
- A sequential file supports both access methods; a serial file supports only sequential access.
- Justify from the dominant operation, not from "it is faster". Say faster at what, and why.
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ê.
You've got it
- serial: order added, append fast, search slow, used for logs · sequential: sorted by a key field, good for batch processing and in-order output · random: position computed from the record key, one read to find a record
- sequential access reads from the start; direct access jumps to a position
- sequential access serves serial and sequential files; direct access serves sequential and random files
- choose from the dominant operation: process everything, look one up, or only append
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