являє собою послідовний масив індексів, в який з основного масиву виноситься інформація про записи, номери яких утворюють арифметичну прогресію з кроком d> 1, причому перший індекс адресує перший запис. Основний масив, доповнений таким індексом, зазвичай називається індексного-послідовним.
Індекси такого типу називаються К - індексами (від слова «ключ»). Крок арифметичної прогресії для К - індексів дорівнює:, де M - кількість елементів у вихідному масиві.
Рандомізований індекс. Якщо ключі записів, інформація про яких виноситься в індекс, наближено утворюють арифметичну прогресію, отримуємо ситуацію з адресною функцією для індексу (рандомізація індексу), причому перший індекс адресує перший запис.
Індекси такого типу називаються А - індексами (від слова «адреса»).
Точний опис рандомізованого індексу полягає в наступному. А - індекс з номером i зберігає адресу запису основного масиву, ключ якої дорівнює або безпосередньо більше значення:, де z - константа (крок арифметичної прогресії), р1 - значення ключа першого запису основного масиву.
Точної формули для кроку арифметичної прогресії z для А - індексів не існує, використовують формулу:, де pi - значення ключа i-й записи.
Завдання 6. Побудувати А - і К - індекси. Вставку провести з урахуванням значення 55 і видалення з урахуванням значення 36.
, 52, 33, 66, 29, 36, 34, 41, 38, 37, 23, 34, 29, 33, 24, 57, 35
Впорядкуємо по зростанню вихідний масив. Масив буде мати наступний вигляд (рис. 3.3, а). Для побудови А - і К - індексів обчислимо крок арифметичної прогресії d, z.
Обчислимо крок арифметичної прогресії для К - індексів:
M=17,. Отримуємо К - індекси (рис. 3.3. Б).
Обчислимо крок арифметичної прогресії для А - індексів:
max (52 - 41)=11,.
Визначимо А - індекси, використовуючи формулу, де pi - значення ключа i-й записи, p1 - значення ключа першого запису, z - крок арифметичної прогресії:
z=22;
p1=23, А1=0100;
(т. к. у вихідному масиві такого значення ключа немає, то виберемо наступне більшу, тобто 52), А2=0114. Отримуємо А - індекси (рис. 3.3. в).
Малюнок 3.3 - Основний масив організації даних (а); К - індекси з урахуванням коригування (б); А - індекси з урахуванням коригування (в)
При коригуванні записів індекси також повинні змінюватися: завжди К - індекси і рідше А - індекси. При включенні нового запису з ключем q визначаємо К - індекс, такий, що K i - 1? q < K i, де i - номер К - індексу. Потім усім К - індексах із номером i і більше присвоюємо значення ключів і адрес тих записів, які безпосередньо передують раніше зафіксованих у цих індексах записам основного масиву. Аналогічно при видаленні запису з ключем q всім К - індексах із номером i і більше присвоюємо значення ключів і адрес тих записів, які безпосередньо випливають за раніше зазначеними в цих індексах записами основного масиву. При коригуванні масиву змінюються менше значень А - індексів, ніж К - індексів. Значення К - і А - індексів представлені з урахуванням змін на малюнку 3.3 (б, в).
Таким чином, А - індекси доцільніше К - індексів - вони характеризуються меншим об'ємом пам'яті, необхідним для їх розміщення, а також більш швидким пошуком при досить великій кількості елементів в масиві.
