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