6.5. Разреженный индекс

6.5.1 Разреженный индекс обычно создается, как вспомогательная структура для поиска в плотном индексе, хотя может применяться и как первичная структура поиска. Разреженный индекс представляет из себя структуру вида:

<ук-тель> <знач.> <ук-тель> .... <ук-тель> <знач.> <ук-тель>

Для каждого значения указатели справа и слева определяют диапазон поис­ка искомого элемента в основной структуре. Число указателей в разреженном ин­дексе - его параметр m (число значений соответственно равно m-1). Для построе­ния разреженного индекса с параметром m исходную структуру следует разбить на m блоков. Обозначим эти блоки B_i, где i=1..m. Должно выполняться условие:

для любых i, j=1..m [((xe Bi, ye Bj) A (i<j)) => (x<y)].

При этом блоки могут располагаться не обязательно в упорядоченном по­рядке. Элементы внутри блока упорядочены.

T~ m+log(n/m) ~ m+ logn - logm.

Пример применения разреженного индекса для поиска в плотном индексе:

Пусть плотный индекс выглядит так:

(2,1), (3,2), (1,3), (4,4), (8,5), (7,6), (6,7), (5,8).

Примечание. Считаем, что в каждом блоке хранится по одной записи исходной структуры

Построим разреженный индекс с параметром 3= log 8 (т.к m=8) .

(1)3(2)6(3)

Предполагается, что можно хранить три записи плотного индекса в блоке (параметр e=3) и они распределены по блокам следующим образом:

[(1,3), (2,1),(3,2)] [(4,4),(5,8),(6,7)] [(7,6), (8,5)] .

По условию в блоке может быть k элементов, где (e+1)/2<=k<=e.

Удаление элемента из плотного индекса означает его удаление из блока. Если в результате удаления очередного элемента в блоке осталось менее (e+1)/2, то переносится один элемент из соседнего блока, а если в соседнем блоке ровно (e+1)/2 элементов, то блоки объединяются. После этого корректи­руются записи разреженного индекса (фактически удаляется одно из значений).

Рис. 25. Удаление из разреженного индекса

При включении нового элемента ищется по разреженному индексу блок, куда он должен быть помещен. Элемент помещается в этот блок, если в нем есть место (число элементов <e), иначе блок расщепляется на два и корректируется разреженный индекс (фактически вставляется новое значение).
Пример (рис. 26).