Организация индексов в СУБД HyTech

Индексы предназначены для оптимизации доступа к данным при выполнении поисковых запросов.
В СУБД HyTech индексы организованы на основе инвертированных списков.

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

· Поиск ведется в ассоциаторе без обращения к самим данным;

· Время поиска не зависит от длины строки и от длины ключа;

· Время поиска практически не зависит от числа целевых строк и от числа строк в базе данных;

· Результатом поиска являются число целевых строк и список их номеров.

Устройство ассоциатора в СУБД HyTech изучается в данном курсе в теме 2 при рассмотрении вопросов архитектуры СУБД HyTech.

Индексы на основе инвертированных списков имеют недостатки, главным из которых является следующий: при добавлении/изменении значения ключевого поля требуется перестроение ассоциатора, которое при значительном размере БД может занять длительное время. Данный недостаток не является фатальным и вполне преодолим, например, в СУБД HyTech изменения данных записываются в переменную часть таблицы, а ассоциатор строится для постоянной части. Такой подход имеет определенные неудобства, поскольку требуется периодическая операция «слияния» постоянной и переменной части таблицы (в HyTech операция слияния называется «упаковкой»). Необходимость такой операции обусловлена ростом переменной части таблицы. Поскольку эта часть не индексируется, то при ее значительном росте возможно замедление поисковых запросов.