Лекция №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) в индексе найти запись (v₂,b₂), где v₂ покрывает v₁;

b) прочитать блок b₂ в оперативную память и искать запись с ключом v₁ в оперативной памяти каким-нибудь методом (двоичным или линейным). Если найдено, то успешно.

При поиске проверять биты свободен/занят, удален/не удален.

Модифицирование:

a) найти запись с ключом v₁, если нет то выход;

b) запись найдена. Если в ключ входит хотя бы одно из модифицированных полей, то удаление из внешней памяти. Среди модифицированных полей нет ни одной записи, в которую входит ключ, то изменить и записать на прежнее место.

Включение: (добавить запись с ключом v₁)

a) новую запись надо добавить в 1 блок. v₁ меньше, чем первая запись первого блока значит первую запись в индексе надо изменить;

b) если v₂≤v₁не в первый блок, тогда в начало среднего блока никогда не добавится; v₂<v₁ запись не будет первой; если v₂=v₁, то аварийный останов.

Т.о. если добавляется не в 1 блок, то файл индекса никогда не изменяется. Еще при добавлении: - есть место в блоке – добавили и все; - если места в блоке нет, тогда добавление новой записи в ОП в данный блок нужно отсортировать в порядке и дальше этот блок делят: последнюю запись выталкивают в следующий блок, следовательно, индекс модифицируется. Обработка последнего блока – выталкивать некуда, тогда надо взять у OS новый блок.

Удалить: (запись с ключом v₁)

a) найти запись с ключом v₁, если не найдена, то ошибка;

b) запись найдена, то удаление производится сдвигом влево, начиная с записи следующей за удаленной. Установка бита свободен/занят в состояние свободен. Если удаляется первая запись в блоке, то корректируется индекс. Если после удаления блок полностью пустой, то вернуть блок в OS и удалить запись из индекса. Если она последняя и первая, то блок главного файла вернуть в OS и удалить 1 запись из индекса.

2. Использование цепных файлов при индексной организации.

При выполнении операций включения иногда требуется найти следующий блок главного файла. Эту процедуру можно упростить, если в заголовок каждого блока поместить ссылку на следующий блок (цепная организация файла). Аналогично может быть организованна структура файла индекса. При использовании линейного поиска в индексе цепная организация позволяет избавится от справочника (таблицы) блоков индекса (необходим лишь адрес его первого блока).

Дата добавления: 2014-01-05