Организация файлов и доступ к ним
| 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) файл хранит каждую запись в позиции, вычисляемой из ключа записи, обычно с помощью хэша. Поиск по ключу очень быстрый; чтение в порядке ключей неудобно. Используется для больших таблиц поиска и счетов клиентов.
Последовательный: порядок поступления, ничего больше
Сортированный последовательный: те же записи, в порядке ключей
Два метода доступа
- Последовательный доступ читает файл от начала до нужной записи. Это единственный тип доступа, который позволяет последовательный (серийный) файл, и именно так обрабатывается последовательный файл в пакетном режиме.
- Прямой доступ сразу переходит к известной позиции, не читая данные, идущие перед ней. Так читаются случайные файлы, а последовательный файл также может быть прочитан напрямую, если известна позиция ключа или он проиндексирован.
- Таким образом, соответствие тем: последовательный доступ для серийных и последовательных файлов; прямой доступ для последовательных и случайных файлов.
Случайный доступ: ключ указывает, где искать
Маршрут доступа к файлу
Безопасно следите за файлом от хранилища до программы и обратно.
Сериальный файл хранит записи:
Серийные файлы сохраняют записи в порядке поступления — быстро добавлять, медленно искать. Секвенциальные файлы отсортированы по ключу.
Соотнесите каждую организацию файлов с тем, как она хранит записи.
Серийный = порядок поступления; секвенциальный = отсортирован; случайный = хешированная позиция; индексно-секвенциальный = отсортирован + индекс.
В случайном (файле прямого доступа) каждая запись размещается:
Ключ преобразуется (часто через хеш-функцию) в позицию, поэтому одноключевой поиск выполняется очень быстро.
Какова разница между серийным и секвенциальным файлом?
Порядок поступления против сортировки по ключу. Именно эта одна разница делает секвенциальный файл пригодным для раннего поиска и медленного добавления.
Разбор примера: выберите организацию
- Программа начисления зарплаты один раз в месяц считывает каждую запись сотрудника по номеру сотрудника, чтобы сформировать расчетные листки. Какую организацию и метод доступа выбрать, и почему?
- Последовательная организация с последовательным доступом: каждая запись обрабатывается, поэтому нет смысла перемещаться по файлу, а хранение по ключу означает, что расчетные листки выдаются в порядке без дополнительной сортировки.
- Банкомат должен получить одну запись счета по его номеру менее чем за секунду. Случайная организация с прямым доступом: позиция вычисляется по номеру счета, поэтому требуется ровно одно чтение вместо поиска среди миллионов записей.
- Веб-сервер добавляет одну строку в лог на каждый запрос. Серийный формат: важна только операция добавления, а запись в конец — самое быстрое действие для серийного файла.
Секвенциальный файл можно читать последовательным доступом, а также прямым доступом.
Последовательный доступ используется для серийных и секвенциальных файлов; прямой доступ — для секвенциальных и случайных. Только серийный файл ограничен одним методом.
Расставьте шаги получения одного счета из случайного файла в правильном порядке.
Поиск не происходит вовсе: ключ превращается в позицию и чтение выполняется один раз. Финальная проверка выявляет коллизию.
Компромиссы рядом
| Серийный | Последовательный | Случайный | |
|---|---|---|---|
| Порядок записей | как добавлены | отсортированы по ключу | вычисляются из ключа |
| Добавление записи | быстро, добавление в конец | медленно, записи сдвигаются | быстро, если слот свободен |
| Поиск одной записи | медленно, чтение всего | быстрее, можно остановиться раньше | быстрее всего, одно чтение |
| Чтение по порядку ключа | нужна сортировка | естественный порядок | нужна сортировка |
- Правильный ответ всегда обосновывается через доминирующую операцию: что эта программа делает чаще всего?
Секвенциальная организация файлов хорошо подходит для обработки каждой записи по очереди.
Прямой доступ подходит для поиска одной записи.
Соотнесите каждую ситуацию с организацией файлов, подходящей для неё.
Добавление только в конец, обработка всего по порядку или поиск одной записи: доминирующая операция выбирает организацию.
Разбор примера: обоснуйте изменение
- Файл книг библиотеки является серийным. Поиск одной книги медленный. Предложите изменение и обоснуйте его.
- Переорганизовать в случайный файл, хешируя ISBN в адрес, чтобы поиск стал одним прямым чтением вместо сканирования всего файла.
- Если библиотека также печатает каталог по названию, последовательная организация по названию служит обеим целям: каталогу не нужна сортировка, а поиск можно остановить рано или использовать бинарный поиск.
- Назовите организацию, назовите метод доступа и свяжите оба с операцией, упомянутой в вопросе.
Для создания отчетов в порядке ключа лучшей организацией файлов является:
Секвенциальный файл уже упорядочен по ключу, поэтому его последовательное чтение дает отчет в правильном порядке.
Организация файлов выбирается на основе ____ операции программы.
Каждая организация быстра в чем-то и медленна в другом, поэтому решает наиболее часто выполняемая операция.
Что должно быть ключом и почему хеширование дает сбои
- Прямой доступ требует ключа, и ключ должен быть уникальным для одной записи. Фамилия не является ключом; номер клиента является.
- Хеширование превращает этот ключ в адрес записи одним вычислением, поэтому одно чтение достигает записи, независимо от размера файла.
- Два разных ключа могут хешироваться в один адрес. Это коллизия, и это не ошибка алгоритма: она неизбежна, когда возможных ключей больше, чем адресов.
- Исправление, указанное в критериях оценивания, — это зона переполнения (overflow area) или хранение указателя по адресу на цепочку записей, которые им делят. Коллизия因此 costs one extra read, not a lost record.
- Так что честное сравнение: хеширование обеспечивает почти постоянную скорость доступа пока файл не заполнится, а его производительность снижается по мере накопления коллизий. Последовательный доступ никогда не деградирует, но никогда и не был быстрым.
Две записи хешируются в один адрес. Какие утверждения верны? Выберите все подходящие варианты.
Ничего не теряется; коллизия требует одного дополнительного чтения. Это неизбежно в принципе, так как возможных ключей всегда больше, чем адресов.
Потерянные баллы
- Серийный — это порядок поступления; последовательный — это отсортировано по ключу. Это не синонимы, и экзамен проверяет именно эту разницу.
- Организация — это то, как расположены записи; доступ — это то, как программа находит одну запись. В вопросе упоминается один из них.
- Последовательный файл поддерживает оба метода доступа; серийный файл поддерживает только последовательный доступ.
- Обосновывайте через доминирующую операцию, а не просто «это быстрее». Укажите, что быстрее и почему.
Вы поняли
- Серийный: порядок добавления, быстрое добавление в конец, медленный поиск, используется для логов · Последовательный: отсортирован по ключевому полю, хорош для пакетной обработки и вывода по порядку · Случайный: позиция вычисляется из ключа записи, одно чтение для поиска записи
- Последовательный доступ читает от начала; прямой доступ перепрыгивает к позиции
- Последовательный доступ подходит для серийных и последовательных файлов; прямой доступ подходит для последовательных и случайных файлов
- Выберите из доминирующей операции: обработать всё, найти одну или только добавить