Последовательные таблицы

Новые записи помещаются в конец таблицы в порядке поступления. Поиск осуществляется перебором записей. Пусть таблица содержит N записей. Для успешного поиска единственной записи требуется просмотреть в среднем N/2 запи­сей; в случае неудачного поиска придется просмотреть всю таб­лицу, то есть N записей. Поиск по вторичному ключу требует просмотра N записей. В любом случае время поиска пропорционально размеру таблицы.

Для того, чтобы физически удалить запись из таблицы, требуется выполнить сдвиг на одну позицию вверх всех нижележащих записей, что требует значительного времени. Как правило, так не поступают. Вместо этого запись помечают как удаленную в специально отводимом для этого байте. Операция упаковки, то есть физического удаления помеченных на удаление записей производится изредка. Такова, например, дисциплина работы со старейшим форматом файлов баз данных – dbf – форматом. Удаленные записи можно "сшить" в стек свободного пространства и использовать для вставки новых записей.

Последовательные таблицы есть смысл использовать, когда таблица мала или скорость поиска несущественна.

Контрольные вопросы

1) Напишите функцию, выполняющую физическое удаление записей из последовательной таблицы, помеченных символом ‘*’ в 1-м байте.

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

3) Напишите функцию, помещающую новую запись в первую удалённую позицию последовательной таблицы, или в конец таблицы, если удалённые позиции отсутствуют.