Последовательный метод

Методы хранения данных и доступа к ним

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

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

Для оценки методов доступа и хранения используются понятия эффективности доступа и эффективности хранения.

Определение. Эффективность доступа – отношение числа логических обращений к числу физических при выборке элемента данных.

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

Например, если на одно логическое обращение требуется два физических, то эффективность доступа 0,5. Если на 10 байт информации требуется одна двухбайтовая ссылка, эффективность хранения 10/12.

Последовательный метод

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