Поиск по частичному соответствию

Вторичные индексы (инвертированные файлы).

Структуры данных для организации поиска по не ключевым полям.

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

В FoxPro используют LOCATE– недостаток – большое время доступа.

Пусть имеется файл, записи которого содержат некоторое поле F. Это поле принимает возможные значения из множества D, домена поля F. F может входить или не входить в ключ.

Вторичный индекс по полю F представляет собой связь между доменом D и множеством записей рассматриваемого файла (ранее рассматриваемые индексы связывают значение ключа с записями файла – называется первичным индексом). Файл с вторичным индексом по полю F называется инвертированным по полю F.

В нотации записей переменной длинны вторичные индексы имеют вид:

Значение (запись)*

где «значение»– значение поля F из домена, (запись)*– список ссылок на записи основного файла.

Если в список входят физические указатели на запись (номера записей) следовательно запись основного файла закреплена.

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

Пример: цвет (список инв. номеров с данным цветом).

Требуется найти запись со значением v₁ поля F₁, v₂ поля F₂ … v_к поля F_к . Эти поля не образуют полного первичного ключа. Если S_i есть множество записей, для которой F_i имеет значение v_i то требуется найти:

Рассмотрим методы решения.

1) Использование множественного вторичного индекса. Достаточно пересечь вторичные индексы (возможно в оперативной памяти). Недостаток: поддержка индексов при включении и удалении. Пример: система «ADABAS».

2) Функции разделенного хеширования. В хеш – файле число участков 2ⁿ. Логический адрес n бит. Разделим n бит на k групп. Одна i-тая группа соответствует одному полю F_i. Для каждой группы построим свою хеш – функцию h_i (V_i). В качестве номера участка примем последовательность бит: h₁ (V₁) h₂ (V₂)… h_k (V_k). Сумма длин всех участков равна h. Каждое значение V_i переведем в часть ключа h_i (V_i), построим общий ключ →поиск в построенном номере участка.

Дата добавления: 2014-01-05