СУБД дают пользователям возможность осуществлять непосредственное управление данными, а программистами – разрабатывать более совершенные средства их обработки (приложения). Характеристики готовых приложений определяются, прежде всего, принятой в СУБД организацией данных и типом используемого транслятора.

По современным воззрениям,

Программа = алгоритм + структура данных

В этом определении подчеркивается, что машинная обработка информации обязана учитывать не только логику вычислений, но и организацию данных, в соответствии с которой производится их выборка и запоминание результатов. Для облегчения соста­вления программы и повышения ее эффективности структура данных должна соответ­ствовать упомянутой логике. Это требование особенно актуально для баз данных, где удельный вес расчетных операций относительно невелик и основная трудоемкость за­проса приходится на выборку данных. Основной проблемой является поиск (записи) по содержимому одного из ее полей — например, информации о занимаемой должности и окладе по фамилии сотрудника.

Простейшей структурой данных является массив (таблица), элементы которо­го выбираются по их номерам. В случае многомерного массива элемент задается не­сколькими координатами (для матрицы — номерами строки и столбца). Поиск в не­упорядоченном массиве требует просмотра в среднем половины его объема, тогда как в упорядоченном можно применить дихотомический поиск (метод половинного деле­ния). С другой стороны, упорядочение возможно по содержимому только одного поля, а его применение существенно усложняет добавление новой информации. В связи с этим весьма эффективен метод хеширования — вычисление адреса по содержимому ключевого поля. Он широко применяется, например, в трансляторах алгоритмиче­ских языков (таблица идентификаторов). Его недостатками являются неоднозначность вычисления адреса, усложняющая реализацию метода, и увеличение потребности в памяти.

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

работка производится по схеме «первый пришел — первый обслужен», во втором — по противоположному принципу.

Динамические (часто меняющие объем) структуры данных хранить в массивах невыгодно. В таких случаях используются списки. Каждый элемент списка содержит информационные и ссылочные поля. В последних указываются адреса предшествую­щего и (или) последующего элементов списка. Списки могут быть и разветвленными. В частности, ссылки могут указывать не только последовательность, но и отношения включения, принадлежности, подчиненности, старшинства и т. п. Удобства операций над списками (поиск, вставка, исключение) опре­деляются количеством и назначением ссылочных полей. Поиск элемента с нужным значением информационного поля требует последовательного просмотра списка.

Хранение взаимосвязанных единиц информации обычно организуется на основе графов, отражающих эту связь.