2. Индексный массив

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

Элемент данных, состоящий из значений ключа и начальных адресов всех содержащих это значение записей, назовем группой. Адреса записей в группе должны быть упорядочены. Массив групп, упорядоченный по значениям ключа, есть индексный массив. Группы имеют неопределенную длину. На рис. 7 показана основная последовательная структура данных и ее индексный массив. Прописными латинскими буквами обозначены значения ключа.

Основной эффект инвертированного массива проявляется при поиске данных по нескольким условиям. Пусть дан запрос «найти все записи, содержащие ключи А и С». Система обратится к инвертированному массиву и найдет группы ключей А и С. Совпадающие значения адресов в А и С укажут в нашем примере на искомую запись с адресом 140. Этот пример поясняет и общее правило. Тем же способом, например, может быть установлено отсутствие записей, удовлетворяющих запросу «В и С».

100	B	E			A
					140
					220
140	A	C	E		B
					100
					220
					C
220	D	B	A		140
					240
					D
					220
240	E	C			E
					100
					140
					240
	Основной			Индексный
	массив					массив

Рис 7. Последовательная структура данных

и ее индексный массив

Следует отметить, что поиск по инвертированному массиву об­наруживает только адреса записей и очень плохо приспособлен для указания всех ключей, связанных с найденной записью. Между тем эта информация часто запрашивается в процессе эксплуатации реальных информационных систем. В примере запись с адресом 140 была найдена по значениям ключа А и С очень быстро, но, чтобы узнать, пользуясь только инвертированным массивом, что в этой записи есть третий ключ Е, трудно предложить что-либо, кроме последовательного перебора остальных групп.

Когда запрос содержит несколько значений, связанных между собой конъюнкциями, поиск может быть ускорен по сравнению с описанным выше общим методом. В инвертированном массиве отыскивается одна из указанных в запросе групп (предположим, первая). По всем адресам, содержащимся в группе, организуется вход в основной массив, и записи, определяемые этими адресами, последовательно проверяются на наличие остальных значений ключей. Например, для запроса «А и С» после обнаружения группы А находится запись с адресом 140, где устанавливается наличие значения С, и затем находится запись с адресом 220, где значение С не обнаруживается.

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