File organisation and access
Введено| English | Значение |
|---|---|
| file organisation/faɪl ˌɔːɡənaɪˈzeɪʃn/ | организация файлов |
| access method/ˈækses ˈmeθəd/ | метод доступа |
| serial file/ˈsɪərɪəl faɪl/ | последовательный файл |
| sequential file/siːˈkwenʃl faɪl/ | последовательный файл |
| key field/kiː fiːld/ | ключевое поле |
| direct access/daɪˈrekt ˈækses/ | прямой доступ |
| sequential access/siːˈkwenʃl ˈækses/ | последовательный доступ |
| random file/ˈrændəm faɪl/ | случайный файл |
Почему ночная работа банка заняла всю ночь
- До 1980-х годов счета банка хранились на магнитной ленте. Ленту можно читать только от одного конца к другому, поэтому дневные транзакции сортировались ночью, а весь мастер-файл читался от начала до конца один раз для их применения.
- Запросить баланс одного клиента в середине дня означало получить ответ: не раньше завтрашнего дня. Организация файла, а не скорость компьютера, определяла возможности банка.
- Диски позволили другую организацию: вычислить положение записи по её ключу и перейти туда. Именно это позволяет банкомату отвечать за секунду.
- Этот урок посвящён организации файлов, двум методам доступа и тому, как выбирать из того, что программа выполняет чаще всего.
Три организации
- Последовательный файл хранит записи в порядке их добавления, без сортировки. Добавление (append) происходит быстро; поиск требует чтения с начала. Используется для журналов и аудиторских трасс.
- Сортированный последовательный файл хранит записи, отсортированные по полю ключа. Поиск быстрее, так как можно остановиться раньше или использовать бинарный поиск; вставка медленная, так как последующие записи должны сдвигаться. Используется для мастер-файлов, обновляемых пакетно.
- Случайный (direct-access) файл хранит каждую запись в позиции, вычисляемой из ключа записи, обычно с помощью хэша. Поиск по ключу очень быстрый; чтение в порядке ключей неудобно. Используется для больших таблиц поиска и счетов клиентов.

Последовательный: порядок поступления, ничего больше

Сортированный последовательный: те же записи, в порядке ключей
Два метода доступа
- Последовательный доступ читает файл от начала до нужной записи. Это единственный тип доступа, который позволяет последовательный (серийный) файл, и именно так обрабатывается последовательный файл в пакетном режиме.
- Прямой доступ сразу переходит к известной позиции, не читая данные, идущие перед ней. Так читаются случайные файлы, а последовательный файл также может быть прочитан напрямую, если известна позиция ключа или он проиндексирован.
- Таким образом, соответствие тем: последовательный доступ для серийных и последовательных файлов; прямой доступ для последовательных и случайных файлов.

Случайный доступ: ключ указывает, где искать
File access route
Follow a file from storage to program and back safely.
A serial file stores records:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
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.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Serial = arrival order; sequential = sorted; random = hashed position; indexed-sequential = sorted + an index.
A random (direct-access) file places each record:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
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?
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Order of arrival versus sorted by key. That single difference is what makes a sequential file searchable early and slow to insert into.
Разбор примера: выберите организацию
- Программа начисления зарплаты один раз в месяц считывает каждую запись сотрудника по номеру сотрудника, чтобы сформировать расчетные листки. Какую организацию и метод доступа выбрать, и почему?
- Последовательная организация с последовательным доступом: каждая запись обрабатывается, поэтому нет смысла перемещаться по файлу, а хранение по ключу означает, что расчетные листки выдаются в порядке без дополнительной сортировки.
- Банкомат должен получить одну запись счета по его номеру менее чем за секунду. Случайная организация с прямым доступом: позиция вычисляется по номеру счета, поэтому требуется ровно одно чтение вместо поиска среди миллионов записей.
- Веб-сервер добавляет одну строку в лог на каждый запрос. Серийный формат: важна только операция добавления, а запись в конец — самое быстрое действие для серийного файла.
A sequential file can be read by sequential access and also by direct access.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
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.
Сложность 3/5 · 200 монет + небольшой бонус за первое завершение сегодня
No searching happens at all: the key is turned into a position and read once. The final check catches a collision.
Компромиссы рядом
| Серийный | Последовательный | Случайный | |
|---|---|---|---|
| Порядок записей | как добавлены | отсортированы по ключу | вычисляются из ключа |
| Добавление записи | быстро, добавление в конец | медленно, записи сдвигаются | быстро, если слот свободен |
| Поиск одной записи | медленно, чтение всего | быстрее, можно остановиться раньше | быстрее всего, одно чтение |
| Чтение по порядку ключа | нужна сортировка | естественный порядок | нужна сортировка |
- Правильный ответ всегда обосновывается через доминирующую операцию: что эта программа делает чаще всего?
Sequential file organisation is well suited to processing every record in turn.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Direct access suits looking up a single record.
Match each situation to the file organisation that suits it.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Append only, process everything in order, or look one record up: the dominant operation picks the organisation.
Разбор примера: обоснуйте изменение
- Файл книг библиотеки является серийным. Поиск одной книги медленный. Предложите изменение и обоснуйте его.
- Переорганизовать в случайный файл, хешируя ISBN в адрес, чтобы поиск стал одним прямым чтением вместо сканирования всего файла.
- Если библиотека также печатает каталог по названию, последовательная организация по названию служит обеим целям: каталогу не нужна сортировка, а поиск можно остановить рано или использовать бинарный поиск.
- Назовите организацию, назовите метод доступа и свяжите оба с операцией, упомянутой в вопросе.
To produce reports in key order, the best file organisation is:
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
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.
Сложность 1/5 · 100 монет + небольшой бонус за первое завершение сегодня
Every organisation is fast at something and slow at something else, so the operation done most often decides.
Что должно быть ключом и почему хеширование дает сбои
- Прямой доступ требует ключа, и ключ должен быть уникальным для одной записи. Фамилия не является ключом; номер клиента является.
- Хеширование превращает этот ключ в адрес записи одним вычислением, поэтому одно чтение достигает записи, независимо от размера файла.
- Два разных ключа могут хешироваться в один адрес. Это коллизия, и это не ошибка алгоритма: она неизбежна, когда возможных ключей больше, чем адресов.
- Исправление, указанное в схеме оценки, представляет собой зону переполнения, или хранение указателя на адрес цепочки записей, разделяющих эту зону. Следовательно, коллизия обходится в одно дополнительное чтение, а не в утрату записи.
- Так что честное сравнение: хеширование обеспечивает почти постоянную скорость доступа пока файл не заполнится, а его производительность снижается по мере накопления коллизий. Последовательный доступ никогда не деградирует, но никогда и не был быстрым.
Two records hash to the same address. Which are true? Select все that apply.
Сложность 2/5 · 140 монет + небольшой бонус за первое завершение сегодня
Nothing is lost; a collision costs one extra read. It is unavoidable in principle, because there are always more possible keys than addresses.
Потерянные баллы
- Серийный — это порядок поступления; последовательный — это отсортировано по ключу. Это не синонимы, и экзамен проверяет именно эту разницу.
- Организация — это то, как расположены записи; доступ — это то, как программа находит одну запись. В вопросе упоминается один из них.
- Последовательный файл поддерживает оба метода доступа; серийный файл поддерживает только последовательный доступ.
- Обосновывайте через доминирующую операцию, а не просто «это быстрее». Укажите, что быстрее и почему.
Вы поняли
- Серийный: порядок добавления, быстрое добавление в конец, медленный поиск, используется для логов · Последовательный: отсортирован по ключевому полю, хорош для пакетной обработки и вывода по порядку · Случайный: позиция вычисляется из ключа записи, одно чтение для поиска записи
- Последовательный доступ читает от начала; прямой доступ перепрыгивает к позиции
- Последовательный доступ подходит для серийных и последовательных файлов; прямой доступ подходит для последовательных и случайных файлов
- Выберите из доминирующей операции: обработать всё, найти одну или только добавить