Индексирование, хеширование данных в базах данных

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

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

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

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

¡ вида содержимого в поле ключа записей индексного файла;

¡ типа используемых ссылок (указателей) на запись основной таблицы;

¡ метода поиска нужных записей.

Основная структура хранения данных содержит записи исходной таблицы и представлена в виде неупорядоченной последовательности физических записей. Для поиска по определенному ключу создается дополнительная структура хранения (так называемый индекс). Число записей в индексе равно числу записей исходной таблицы (числу физических записей в основной структуре хранения). Каждая запись индекса имеет два поля: ключевое поле записи основной структуры и указатель – адрес записи основной структуры с соответствующим значением ключа. Записи индекса (индексного файла) упорядочены по значению ключа. Адреса связи этих записей определяют логическое упорядочение записей основной структуры хранения.

Рисунок 1Индексирование

Пример соответствующей структуры хранения приводится на рис. 1. Рассматриваемую структуру хранения называют еще инвертированным списком.

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

Дата добавления: 2015-05-10