6.4. Плотный индекс

Плотный индекс представляет собой вспомогательный массив ind размерно­стью n*2 такой, что для любого i=1..n ind[i,1]=x, ind[i,2]=k, где k - адрес блока, в котором хранится запись с соответствующим значением. Другими словами, плот­ный индекс - есть массив пар вида (<искомый элемент, его адрес>). Построение плотного индекса, как в наихудшем, так и в среднем требует n операций.

Алгоритм выглядит так:

for i Î {множество поисковых значений} do begin

ind[i,1]:=x;

ind[i,2]:=block(x)

end;

Алгоритм поиска c помощью плотного индекса выглядит так:

m:=find_in_index(x);//процедура поиска в плотном индексе

k:=ind[m,2];

Примечание. В случае если поиск организован по неключевому полю результат поиска в

индексе будет неоднозначным, но обратим внимание, что это не приводит к трудно-разре-

шимым проблемам, как при хешировании.

Организовать поиск в плотном индексе можно различными методами, самое

очевидно решение – поддерживать плотный индекс в отсортированном порядке.

Тогда можно воспользоваться методами дихотомии или золотого сечения, в этом

случае T~logn, Tcр~logn. Трудоемкость построения упорядоченного плотного

индекса определяется трудоемкостью сортировки:

T~n logn, Tср~nlogn

Приведем пример

ФИО

Телефон

Addr 1 Воронов

111-111

Addr 1 Фирсов

444-444

Addr 1 Виталин

777-777

Addr 2 Логман

666-666

Addr 2 Зимина

555-555

Addr 3 Собинова

333-333

Addr 3 Ларин

222-222

Плотный индекс - {(Воронов,Аdr 1),(Ларин, Аdr 3),

(Собинова, Аdr 3),(Фирсов, Аdr 1), (Зимина, Аdr 2),(Логман,

Аdr 2),(Виталин, Аdr 1)}

Основной недостаток такого метода - невозможность при модификации данных оперативного включения в индекс или удаления из индекса нового элемента (эти операции требуют ~ n операций). Этих проблем можно избежать, если использовать разреженный индекс.