Записи в базе данных связаны в целое по ключевым полям. Если планируется частое выполнение запросов по неключевым атрибутам, то лучшее решение проблемы – введение “вторичных индексов”.
Файл со вторичным индексом связывает значения из домена неключевого атрибута либо напрямую с записями, либо косвенно через значение ключа. Очевидно, что связь через ключ записи требует дополнительного обращения за соответствующей записью, однако этот вариант может быть выгоднее по объему памяти, если значение ключа занимает меньше места, чем указатель на запись.
Пример структуры со вторичным индексом приведен на рисунке, где z1, z2,... – значения неключевых атрибутов; цифры – количество указателей p.
Здесь используется списковая структура потому, что количество значений неключевого атрибута, хранящихся в произвольный момент времени, заранее не известно.
Конечно, в случае частых перезаписей данных лучше не вводить вторичные индексы и выполнять поиск методом перебора.
При проектировании некоторых баз данных возникает задача поиска по двум и более атрибутам, не образующим ключ. Поиск записей с заданными значениями нескольких полей называют поиском по частичному соответствию.
Задача поиска по частичному соответствию может быть решена с помощью вторичных индексов по заданным атрибутам. Между найденными с помощью вторичных индексов указателями (или значениями ключа) выполняют операцию пересечения. Если указатели адресуют блок записей, то, конечно, следует дополнительно проанализировать все записи в найденном блоке.
Поиск по частичному соответствию достаточно экономично реализуется в хешированном файле при подборе хеш-функции по методу раздельного хеширования. В методе раздельного хеширования хеш-функция H(N1, N2, ... , Nk) вычисляется по значениям атрибутов N1, N2, ... , Nk, которые планируются в запросах. Причем хеш-функция H(N1, N2, ... , Nk) строится как произведение частичных хеш-функций Hk(Nk):
H(N1, N2, ... , Nk) = H1(N1) · H2(N2) · ... · Hk(Nk).
Число значений хеш-функции и соответственно число цепочек записей равно
M = M1 · M2 · ... · Mk.
В запросе на поиск по частичному соответствию значения некоторых атрибутов обычно заданы и поэтому по каждому j-му атрибуту необходимое число просматриваемых цепочек будет уменьшаться в Mj раз.