При таком поиске организуется две таблицы: таблица данных со своими ключами - упорядоченных по возрастанию, и таблица индексов, которая тоже состоит из ключей данных, но эти ключи взяты из основной таблицы через определенный интервал. Последовательный поиск выполняется по меньшему индексу, а не по большой таблице. Когда найден правильный индекс, второй последовательный поиск выполняется по небольшой части записей самой таблицы. Индекс применяется для отсортированной таблицы, представленной и в виде связанного списка, и в виде массива.
Порядок эффективности индексно-последовательного поиска
В сравнении с последовательным, эффективность индексно-последовательного поиска гораздо выше, особенно для больших массивов, но не следует забывать, что последовательность элементов должна быть упорядочена.
Таблицы индексно - последовательного поиска