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

Наиболее эффективны методы индексирования и хеширова­ния значений ключей отношения.

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

Индексы позволяют находить строки, в которых значения клю­чевых полей совпадают с заданным значением или принадлежат заданному интервалу.

Хеширование (hashing) — использование хэш-функций, кото­рые вычисляют вес строки таблицы по значению ее ключевых атрибутов. Результат вычисления хэш-функции — целое число в диапазоне физических номеров строк таблицы.

Идеальная хэш-функция должна давать разные значения веса для разных ключевых атрибутов. Но это не всегда возможно. На практике обычно используют простые хэш-функции, например f(k)=к mod p, где к — целое число, первичный ключ отношения; р — простое целое число; mod — операция, вычисляющая остаток при целочисленном делении. Если ключевой атрибут — стро­ка символов, то для вычисления f(k) выбирается один из методов преобразования строки в число, например вычисление конт­рольной суммы.

Для организации доступа к данным при хешировании создает­ся таблица с пустыми строками, которая заполняется следующим образом:

• по первичному ключу новой строки вычисляется значение хэш-функции f(k) и результат трактуется как номер строки в со­зданной таблице;

• если строка уже занята, производится проверка следующих строк по специальному алгоритму до тех пор, пока не будет обна­ружено свободное место.

Аналогично производится поиск нужной строки:

• если после вычисления f(k) на месте в таблице, которое со­ответствует вычисленному значению, оказывается пустая строка, значит, искомой строки просто нет;

• если значение ключа совпало с искомым, поиск заканчива­ется;

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

Если таблица заполнена не более чем на 60 %, то для размеще­ния новой или поиска существующей строки необходимо прове­рить в среднем не более двух ячеек. Хеширование используют для поиска строк по точному совпадению значения ключевого атри­бута кортежа с нужным значением ключа.