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

Ускорение доступа к данным достигается применением принципиально иных методов размещения информации и ее поиска либо путем создания массивов вспомогательной информации о хранимых данных. Эти же методы необходимы при организации доступа к информации по нескольким ключевым атрибутам одновременно. Доступ к требуемым записям может осуществляться не только путем сравнения искомого значения ключа с ключами записей, извлекаемых из массива по определенному алгоритму (как это было в рассмотренных методах обработки данных), но и в результате вычисления местоположения требуемой записи. Сами записи могут быть упорядочены алгоритмом сортировки либо используется специальная расстановка записей. Адресная функция Расстановка записей происходит в соответствии с так называемой адресной функцией (другие общеупотребительные ее названия - "рандомизирующая функция" и "хэш-функция"). Применяемые при этом методы организации данных часто называются методами рандомизации. Адресной функцией называется зависимость I = f(p), где i - номер (адрес) записи; р - значение ключевого атрибута в записи.

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

Для ускорения поиска записей в массиве используется дополнительная информация, организованная в виде массива индексов. Индексом называется набор ключей и адресов записей, которые выбираются из основного массива по определенному закону. Отдельный элемент набора индексов также называется индексом, хотя это не соответствует значению слова index -список. Имеются три важные разновидности индексов: • информация о каждой записи основного массива попадает в индекс (сплошная индексация); • номера записей, информация о которых выносится в индекс, образуют арифметическую прогрессию с шагом d > 1. Основной массив, дополненный таким индексом, обычно называется индексно-последовательным; • ключи записей, информация о которых выносится в индекс, приближенно образуют арифметическую прогрессию.

Дата добавления: 2015-11-04