А) Нещільний індекс
Нехай основний файлFупорядкований по полю ключаК.Побудуємо додатковий файлFDза таким правилом:
1) записи файлуFDмають форматFD(K, Р),деК –поле, що приймає значення ключа першого запису блоку основного файлуF; Р - покажчик на цей блок;
2) записи файлуFDупорядковані по полюК.
Отриманий файлFDназиваєтьсянещільним індексом.Кількість записів файлуFDдорівнює кількості блоків основного файлуF.Для організації файлуFDпотрібна додаткова зовнішня пам'ять.
В-дерево.Оскільки нещільний індекс упорядкований по ключовому полю, то над ним можна побудувати ще один нещільний індекс (нещільний індекс нещільного індексу) і т.д., поки на останньому верхньому рівні не залишиться всього один блок.
Отримана структура називаєтьсяВ-деревомпорядкут,дет –кількість записів у блоці індексу. Таке дерево повинно мати в кожному вузлі не меншет/2залежних вузлів і все листя повинне розташовуватися на одному рівні.
Для здійснення послідовного пошуку блоки першого рівня можуть бути пов'язані в ланцюг зростання значення ключа. Пошук у дереві виконується так само, як і в нещільному індексі. Вдалий та невдалий пошук запису в В-дереві вимагаєhобмінів, деh –число рівнів В-дерева.
При пошуку по інтервалу значеньа ≤ До ≤ bспочатку виконується пошук поК = ау дереві, а потім – послідовний пошук за умовоюК ≤ bу блоках 1-го рівня В-дерева.
Б) Щільний індекс
Нехай через будь-які причини неможливо впорядкувати основний файлFза ключомК.Побудуємо додатковий файлFDза правилом:
1) записи файлуFDмають форматFD(K, Р),деК –поле, що приймає значення ключа запису основного файлуF;Р –покажчик на цей запис;
2) записи файлуFDупорядковані по полюК.
Отриманий файл називаєтьсящільним індексом.Він будується майже так само, як і нещільний індекс. Відмінність у тому, що кожного значення ключаКу файліFDє окрема запис, а неповному індексі - лише значення ключа першого запису блоку.
Над щільним індексом можна побудувати В-дерево.
Хешований пошук
Швидкодія забезпечується заміною перебірних і пошукових процедур на пряме обчислення розташування шуканого запису за значенням ключа. Обчислення містить три основні кроки:
1) перетворення значення ключа на числове значення (при нечисловому ключі),
2) хешування, що полягає в перерахунку числового еквівалента ключа значення рандомізованої змінної з імовірно рівномірним законом розподілу. Для перерахунку використовується обрана хеш-функція, що дає бажаний ефект рандомізації,
Цей алгоритм простий, але неефективний у часі при заповненні таблиці більш ніж наполовину. Крім того, при нерівномірному розподілі ключів цей алгоритм призводить до локальних згущень записів і збільшення кількості колізій за відносно вільної таблиці.