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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Объем продаж (ОБ – индекс)	Указатель номера записи в файле ПРОДАЖИ

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

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

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

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

Сжатие данных.

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

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

Пусть имеется три записи, содержащие следующие значения:

Эколог………….

Экология……….

Экологический…

Тогда после сжатия приведенных записей по этой технологии будет записано:

0 – Эколог

6 – ия

7 – ческий

Другой тип технологии сжатия основан на иерархическом сжатии данных.

Пусть в файле ПРОДУКТЫ записи упорядочены по возрастанию значений номера накладной (поля НН), как показано в таблице.

Записи файла ПРОДУКТЫ

Номер накладной (НН)	Код покупателя (КП)	Наименование продукта (НП)	Количество, кг (КОЛ)	Цена, руб (ЦЕНА)
		сыр
		масло
		шоколад
		сахар
		крахмал

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

1) постоянная – номер накладной и код покупателя (повторяются в записях);

2) переменная – данные о продуктах: наименование, количество, цена.

Результат иерархического сжатия показан в таблице.

Результат иерархического сжатия записей файла ПРОДУКТЫ

НН	КП	НП	КОЛ	ЦЕНА
		сыр
масло
шоколад
		сахар
крахмал

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

Пусть некоторые значения записаны с помощью символов A, Б, В, Г и подсчитана частота, с которой они встречаются. Принцип кодирования Хаффмана показан в таблице.

Кодирование Хаффмана

Символ	Частота, %	Код
A
В
Г
Б

Символ А встречается чаще других и его код поэтому самый короткий. Все остальные коды длиннее. Использовать в качестве первого кода 0 нельзя, так как он будет совпадать с начальной частью последующих более длинных кодов.

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