Структуры данных

Но очень скоро стало понятно, что невозможно обойтись общей библиотекой программ, реализующей над стандартной базовой файловой системой более сложные методы хранения данных. Поясним это на примере. Предположим, что требуется реализовать простую информационную систему, поддерживающую учет служащих некоторой организации. Система должна выполнять следующие действия:

– выдавать списки служащих по отделам;

– поддерживать возможность перевода служащего из одного отдела в другой;

– обеспечивать средства поддержки приема на работу новых служащих и увольнения работающих служащих, т.е. ввод и удаление данных о служащих.

Кроме того, для каждого отдела должна поддерживаться возможность получения:

– имени руководителя отдела;

– общей численности отдела;

– общей суммы зарплаты служащих отдела, среднего размера зарплаты и т. д.

Для каждого служащего должна поддерживаться возможность получения:

– номера удостоверения по полному имени служащего (для простоты допустим, что имена всех служащих различны);

– полного имени по номеру удостоверения;

– информации о соответствии служащего занимаемой должности и размере его зарплаты.

Предположим, что мы решили создать эту информационную систему на файловой системе и пользоваться одним файлом СЛУЖАЩИЕ, расширив базовые возможности файловой системы за счет специальной библиотеки функций. Поскольку минимальной информационной единицей в нашем случае является служащий, в этом файле должна содержаться одна запись для каждого служащего. Чтобы можно было удовлетворить указанные выше требования, запись о служащем должна иметь следующие поля:

– полное имя служащего (СЛЖ_ИМЯ);

– номер его удостоверения (СЛЖ_НОМЕР);

– данные о соответствии служащего занимаемой должности (СЛЖ_СТАТ = {«да», «нет»});

– размер зарплаты (СЛЖ_ЗАРП);

– номер отдела (СЛЖ_ОТД_НОМЕР).

Поскольку мы решили ограничиться одним файлом СЛУЖАЩИЕ, та же запись должна содержать имя руководителя отдела (СЛЖ_ОТД_РУК). Если мы этого поля не введем, то невозможно будет, например, получить имя руководителя отдела в котором работает служащий.

Чтобы информационная система могла эффективно выполнять свои базовые функции, необходимо обеспечить многоключевой доступ к файлу СЛУЖАЩИЕ по уникальным ключам СЛЖ_ ИМЯ и СЛЖ_НОМЕР. Ключ называется уникальным, если его значения гарантированно различны во всех записях файла. Если мы не обеспечить многоключевой доступ к файлу СЛУЖАЩИЕ, то для выполнения наиболее часто используемых операций получения данных о конкретном служащем понадобится последовательный просмотр в среднем половины записей файла.

Кроме того, система должна обеспечить возможность эффективного выбора всех записей с общим значением СЛЖ_ОТД_НОМЕР, т. е. доступ по неуникальному ключу. Если не поддерживать данный механизм доступа, то для получения данных об отделе в целом, в общем случае потребуется полный просмотр файла.

Но даже в этом случае, чтобы получить численность отдела или общий размер зарплаты, система должна будет выбрать все записи о служащих указанного отдела и посчитать соответствующие общие значения. Общая структура файла СЛУЖАЩИЕ показана на Рис. 1.6.

Рис. 1.6 - Структура файла СЛУЖАЩИЕ на уровне приложения

Таким образом, мы видим, что при реализации даже такой простой информационной системы на базе файловой системы возникают следующие затруднения:

– требуется создание сложной надстройки для многоключевого доступа к файлам;

– возникает существенная избыточность данных (для каждого служащего повторяется имя руководителя его отдела);

– требуется выполнение массовой выборки и вычислений для получения суммарной информации об отделах.

Кроме того, если в ходе эксплуатации системы потребуется, например, обеспечить операцию выдачи списков служащих, получающих указанную зарплату, то для этого либо придется полностью просматривать файл, либо нужно будет реструктурировать файл СЛУЖАЩИЕ, объявляя ключевым и поле СЛЖ_ЗАРП.

Для улучшения ситуации можно было бы поддерживать два многоключевых файла: СЛУЖАЩИЕ и ОТДЕЛЫ. Первый файл должен был бы содержать поля СЛЖ_ИМЯ, СЛЖ_НОМЕР, СЛЖ_СТАТ, СЛЖ_ЗАРП и СЛЖ_ОТД_НОМЕР, а второй – ОТД_НОМЕР, ОТД_РУК (номер удостоверения служащего, являющегося руководителем отдела), ОТД_СЛЖ_ЗАРП (общий размер зарплаты служащих данного отдела) и ОТД_ЧИСЛ (общее число служащих в отделе). Структура этих файлов показана на Рис. 1.7.

Введение этих двух файлов позволило бы преодолеть большинство неудобств, перечисленных выше. При этом:

– каждый из файлов содержал бы только не дублируемую информацию;

– не возникала бы необходимость в динамических вычислениях суммарной информации по отделам.

Но добавление в информационную систему второго файла создает принципиально иную ситуация, которая приводит к тому, что наша информационная система должна обладать особенностями, сближающими ее с СУБД.

Рис. 1.7 - Структура файлов СЛУЖАЩИЕ и ОТДЕЛЫ на уровне приложения