Лекция №24
Название лекции: Операции над сортированным файлом с незакрепленными
и закрепленными записями.
План:
1. Операции над сортированным файлом с незакрепленными записями:
1.1. Поиск;
1.2. Модификация;
1.3. Включение;
1.4. Удаление.
2. Использование цепных файлов при индексной организации.
3. Организация сортированных файлов с закрепленными записями.
3.1. Инициализация;
3.2. Поиск;
3.3. Модификация;
3.4. Включение;
3.5. Удаление.
1. Операции над сортированным файлом с незакрепленными записями.
Операции (модификации, поиска, включения и удаления) над файлом требует таких же операций над файлами индекса. Записи файла индекса всегда не закреплены, т.о. как выполняются операции на основном файле (у которого записи не закреплены) так и выполняются операции над файлом индекса.
Поиск записи: (найти запись с ключом v)
a) в индексе найти запись (v2,b2), где v2 покрывает v1;
b) прочитать блок b2 в оперативную память и искать запись с ключом v1 в оперативной памяти каким-нибудь методом (двоичным или линейным). Если найдено, то успешно.
При поиске проверять биты свободен/занят, удален/не удален.
Модифицирование:
a) найти запись с ключом v1, если нет то выход;
b) запись найдена. Если в ключ входит хотя бы одно из модифицированных полей, то удаление из внешней памяти. Среди модифицированных полей нет ни одной записи, в которую входит ключ, то изменить и записать на прежнее место.
Включение: (добавить запись с ключом v1)
a) новую запись надо добавить в 1 блок. v1 меньше, чем первая запись первого блока значит первую запись в индексе надо изменить;
b) если v2≤v1не в первый блок, тогда в начало среднего блока никогда не добавится; v2<v1 запись не будет первой; если v2=v1, то аварийный останов.
Т.о. если добавляется не в 1 блок, то файл индекса никогда не изменяется. Еще при добавлении: - есть место в блоке – добавили и все; - если места в блоке нет, тогда добавление новой записи в ОП в данный блок нужно отсортировать в порядке и дальше этот блок делят: последнюю запись выталкивают в следующий блок, следовательно, индекс модифицируется. Обработка последнего блока – выталкивать некуда, тогда надо взять у OS новый блок.
Удалить: (запись с ключом v1)
a) найти запись с ключом v1, если не найдена, то ошибка;
b) запись найдена, то удаление производится сдвигом влево, начиная с записи следующей за удаленной. Установка бита свободен/занят в состояние свободен. Если удаляется первая запись в блоке, то корректируется индекс. Если после удаления блок полностью пустой, то вернуть блок в OS и удалить запись из индекса. Если она последняя и первая, то блок главного файла вернуть в OS и удалить 1 запись из индекса.
2. Использование цепных файлов при индексной организации.
При выполнении операций включения иногда требуется найти следующий блок главного файла. Эту процедуру можно упростить, если в заголовок каждого блока поместить ссылку на следующий блок (цепная организация файла). Аналогично может быть организованна структура файла индекса. При использовании линейного поиска в индексе цепная организация позволяет избавится от справочника (таблицы) блоков индекса (необходим лишь адрес его первого блока).