31. Индексирование и хеширование

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

Пусть в базе данных содержатся сведения о продажах автомобилей в таблице ПРОДАЖИ

Марка автомобиля	Менеджер	Месяц	Объем продаж
Опель-Астра	Иванов	Январь	12
Опель-Омега	Сидоров	Февраль	24
Опель-Астра	Иванов	Март	5
Опель-Вектра	Петров	Январь	5
Опель-Омега	Сидоров	Февраль	18
Опель-Вектра	Петров	Февраль	19

Данные этой таблицы хранятся в файле ПРОДАЖИ. Предполагается, что пользователи будут составлять запросы на поиск менеджеров, продавших тот или другой автомобиль.

При необходимости поиска менеджеров, продавших, например, Опель-Вектра, нужно просмотреть весь файл ПРОДАЖИ и найти все записи, у которых марка автомобиля есть «Опель- Вектра».

Возможен и другой подход. Создается файл АВТОМОБИЛИ с расположением в нем марок автомобилей в алфавитном порядке, в другом поле записывается порядковый номер записи данного автомобиля в таблице ПРОДАЖИ, как показано в таблице.

Записи файла АВТОМОБИЛИ

Марка автомобиля ( МА-индекс)	Указатель номера записи в файле ПРОДАЖИ
Опель-Астра	1
Опель-Астра	3
Опель-Вектра	4
Опель-Вектра	6
Опель-Омега	2
Опель-Омега	5

В этом файле просматриваются записи со значением поля Марка автомобиля «Опель-Вектра» и соответственно указателям номера записи в файле ПРОДАЖИ извлекаются из него записи об искомых менеджерах.

Файл АВТОМОБИЛИ называют индексным файлом, поле Марка автомобиля – индексом, а файл ПРОДАЖИ – индексированным. Индекс – это средство ускорения операций поиска в таблице базы данных, а также других операций, требующих поиска: извлечения, корректировки, сортировки и т.д. Индексный файл – это файл, в котором хранится информация об индексе.

В нем записи состоят из двух значений:

1. данного из индексированного файла;

2. указателя номера записи индексированного файла, в котором хранится информация об этом данном.

Файл данных может иметь несколько индексов. Так, если предполагается составлять запросы на поиск менеджеров, продавших то или другое количество автомобилей, то для файла ПРОДАЖИ можно создать индексный файл ОБЪЕМЫ с записями как в таблице.

Записи индексного файла ОБЪЕМЫ

Объем продаж (ОБ – индекс)	Указатель номера записи в файле ПРОДАЖИ
5	3
5	4
12	1
18	5
19	6
24	2

Индексы МА и ОБ могут использоваться как раздельно, так и совместно для более эффективного доступа к данным, например, на случай поиска менеджеров, продавших пять Опель- Вектра. По индексу МА буду найдены записи с указателями 4, 6, а по индексу ОБ – записи с указателями 3, 4. После сравнения двух наборов полученных указателей будет установлено, что условию запроса удовлетворяет запись файла ПРОДАЖИ с порядковым номером 4, и только тогда эта запись будет извлечена. Индексы могут создаваться на основе комбинации двух и более полей.

Таким образом, цель использования индексирования – это ускорение извлечения данных за счет уменьшения количества дисковых операций ввода-вывода.

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

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