<<
>>

3.2 МЕТОДЫ УСКОРЕНИЯ ДОСТУПА К ДАННЫМ

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

Эти же методы необходимы при организации доступа к информации по нескольким ключевым атрибутам одновременно.

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

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

Адресная функция

Расстановка записей происходит в соответствии с так называемой адресной функцией (другие общеупотребительные ее названия - "рандомизирующая функция" и "хэш-функция"). Применяемые при этом методы организации данных часто называются методами рандомизации.

Адресной функцией называется зависимость

где і - номер (адрес) записи;

р - значение ключевого атрибута в записи.

Адресная функция может вырабатывать одинаковое значение і для значений р, принадлежащих разным записям, которые в этом случае называются синонимами. К функции f предъявляются следующие требования: •

она должна быть задана аналитически и вычисляться достаточно быстро; •

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

число записей-синонимов должно «оставлять 10-20% от общего числа записей.

Известно достаточно много адресных функций, хорошо соответствующих этим требованиям. Простейшая адресная функция имеет вид:

і = р - а.

где а - константа.

Пусть известны минимальное значение ключевого атрибута в массиве р' и максимальное значение р " .

Тогда а = р' - 1. Необходимый участок памяти для данных оценивается в р" - р' +1 запись. Записи-синонимы связываются в цепочки с помощью адресов связи, оии занимают дополнительную (резервную) память.

Пример размещения записей с ключами 13,11,14,11,15,18, 14,16 согласно адресной функции і = р - а показан на рис. 3.9.

Рве. 3.9. Организация записей в соответствии с адресной функцией і = р - а

При доступе к записи с ключом q вычисляется i=f(q) и производится обращение к і-й записи. При необходимости с помощью адресов связи извлекаются все сииоиимы.

Недостаток адресной функции вида і = р - а - большой объем неиспользуемой памяти, если р "- р 'много больше, чем количество записей М.

Указанного недостатка лишена функция вида

і - ОСТ (р/га).

Здесь m - целое число; ОСТ - остаток от деления р на т.

Вычисление і на языке Паскаль производится с помощью оператора і: =р mod m.

Значение m принимается равным простому числу, которое непосредственно больше либо непосредственно меньше числа записей М.

Выделяются 2 зоны памяти - основная и резервная. Основная зона содержит m записей. Резервная зона предназначена для размещения записей-синонимов.

-L

Резервная зона

Основная зона

Рис. 3.10. Организация записей в соответствии с адресной функцией і = OCT (p/m)

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

Например, для массива ключей со значениями 17, 9, 4, 14, 25, 21, 20, 11 необходимо выбрать щ=7, поскольку М=8 (возможно также т=19). Содержимое основной и резервной зон иллюстрирует рис.3.10. Резервная зона заполняется последовательно. При поиске значения, например q=l 1, вычисляется і = ОСТ(11/7)—4, и далее последовательно сравниваются 4 и 11, 25 и 11и т. д. В рассматриваемом примере число записей-синонимов составляет 3/8.

<< | >>
Источник: Мишенин А. И.. Теория экономических информационных систем: Учебник. - 4-е изд., доп. и перераб. - М.: Финансы и статистика. - 240 с. 2002

Еще по теме 3.2 МЕТОДЫ УСКОРЕНИЯ ДОСТУПА К ДАННЫМ:

  1. Глава 2 УСКОРЕННЫЕ МЕТОДЫ КОРРОЗИОННЫХ ИСПЫТАНИИ МЕТАЛЛОВ
  2. Раздел I ОСНОВЫ ТЕОРИИ КОРРОЗИИ И МЕТОДЫ УСКОРЕННЫХ КОРРОЗИОННЫХ ИСПЫТАНИИ МЕТАЛЛОВ
  3. Глава 5 МЕТОДЫ УСКОРЕННЫХ ИСПЫТАНИЙ ДЛЯ ОПРЕДЕЛЕНИЯ ЗАЩИТНЫХ СВОЙСТВ ЛАКОКРАСОЧНЫХ ПОКРЫТИЙ
  4. 4.18. Ускоренное обучение
  5. Ускоренная утилизация
  6. МАКСИМАЛЬНОЕ УСКОРЕНИЕ
  7. Глобальная сводка по данным ООН
  8. Лекция 16 ГРЕЦИЯ В XI-IX ВВ. ДО н. э. ПО ДАННЫМ ГОМЕРОВСКОГО ЭПОСА
  9. 5.5 Разработка ускоренной технологии получения крепкого напитка
  10. Ускорение экономического роста и его противоречивый характер
  11. ДУХОВНАЯ И МАТЕРИАЛЬНАЯ КУЛЬТУРА ВРЕМЕН ИНДОЕВРОПЕЙСКОЙ ОБЩНОСТИ ПО ДАННЫМ ЛИНГВИСТИКИ
  12. Восприятие как выдвижение гипотезы и придание смыслов сенсорным данным
  13. Определенную помощь в ускорении сбора материалов может оказать диктофон
  14. 8.2.8. Имитационное моделирование технологического процесса и оценки адекватности модели по данным работы опытной установки.
  15. ГЛАВА V ОБ УСКОРЕНИИ ДВИЖЕНИЯ ПРИ ПАДЕНИИ ТЕЛ. ПРОСТРАНСТВО, ПРОЙДЕННОЕ В ПЕРВУЮ СЕКУНДУ
  16. Методы требования и контроля за поведением. Метод переключения. Комплексное использование методов воспитания
  17. К ПРОБЛЕМЕ ЭТНОГЕНЕЗА УЙГУРОВ (ПО ДАННЫМ СРАВНИТЕЛЬНОЙ АНТРОПОЛОГИИ НАСЕЛЕНИЯ СРЕДНЕЙ АЗИИ И СИНЬЦЗЯНА) (табл. 40 — 44)
  18. 3.13. Использование глазных ключей доступа