Если таблица упорядочена по уменьшающемуся или увеличивающемуся значению ключа записей, то последовательный поиск по такой таблице эффективен. Он требует намного меньше сравнений, чем в не отсортированной таблице [3].
Предположим, что можно собрать некоторое большое число запросов на поиск до того, как они будут обработаны. Например, во многих приложениях ответ на запрос информации может быть отсрочен до следующего дня. В таких случаях все запросы за некоторый день могут быть собраны вместе, и реальный поиск может быть осуществлен в течение ночи, когда новые запросы не поступают. Если таблица и список запросов отсортированы, то может быть выполнен последовательный поиск при одновременном продвижении и по таблице, и по списку запросов, начиная поиск каждого следующего элемента списка запросов в том месте, где окончился предыдущий поиск. Таким образом, нет необходимости выполнять поиск по всей таблице для каждого запроса на поиск.
Для увеличения эффективности поиска в отсортированном файле существует другой метод, но он приводит к увеличению требуемого пространства. Этот метод называется индексно-последовательным методом поиска. В дополнение к отсортированному файлу заводится некоторая вспомогательная таблица, называемая индексом. Каждый ее элемент состоит из ключа kindex и указателя на запись в файле, соответствующую этому ключу pindex. Элементы в таблице index должны быть отсортированы по этому ключу также как и элементы в файле. Рассмотрим пример такого построения [3].
Рис. 4.1. Индексно-последовательный файл
Алгоритм, используемый для поиска в индексно-последовательном файле, прост.
Пусть kindex будет массивом ключей в индексе, и пусть pindex будет массивом указателей внутри индекса на записи в файле. Пусть данный файл представлен в виде массива, n — размер файла, nindex — размер таблицы индекса; тогда алгоритм может быть представлен следующим фрагментом программы:
// key – искомый ключ записи
…
search=0;
i=1;
while ((i<=nindex) && (kindex[i]<=key)) i:=i+1;
// установить lowlim на наименьшую возм. позиц.в таблице
if (i==1) lowlim=1;
else lowlim=pindex[i-1];
//установить hillim на наиб. возм. позиц.в таблице
if (i==nindex+1) hillim=n; // последний элемент
else hillim=pindex[i];
// поиск в таблице от позиции lowlim по дозиции hilim
for (j= lowlim;j<= hillim;j++)
{
if (k[j]==key )
{
search:=j; cout<<”Элемент найден. Его номер =”<< j;
return;
}
}
…
Последовательный поиск вначале выполняется по меньшей таблице индекса. Когда найден индекс или диапазон, где ключ должен находиться, то дальнейший поиск выполняется по небольшой части записей самой таблицы.
Индекс применяется для отсортированной таблицы, представленной или в виде связанного списка, или в виде массива. Использование связанного списка приводит к несколько большим накладным расходам по пространству для указателей, хотя вставки и удаления могут быть выполнены проще. Если таблица является такой большой, что даже использование индекса не дает достаточной эффективности (или из-за того, что индекс большой, или из-за того, что индекс мал, так что соседние ключи в индексе находятся далеко друг от друга в таблице), то может быть использован индекс второго уровня в свою очередь. Индекс второго уровня действует как индекс для первичного уровня, последний указывает на элементы основной таблицы записей.
Рис. 4.2. Использование вторичного индекса
Удаление из индексно-последовательной таблицы может быть сделано при помощи отметки удаленных записей флагом. При последовательном поиске по таблице удаленные записи игнорируются. Отметим, что если некоторый элемент удален, то даже если его ключ находится в индексе, ничего не надо делать с индексом, а надо отметить флагом данный элемент первоначальной таблицы.
Вставка в индексно-последовательную таблицу является более трудной, поскольку между двумя уже существующими элементами таблицы может не быть свободного места, что приводит к необходимости сдвигать большое число элементов таблицы. Однако, если некоторый недалеко расположенный элемент в таблице был отмечен флагом как удаленный, то необходимо сдвинуть только часть элементов и поверх удаленного элемента может быть записана новая информация. Это в свою очередь может привести к необходимости изменения индекса, если элемент, на который указывал некоторый элемент индекса, был сдвинут.
В общем случае, когда инициализируется некоторая таблица, по всей таблице расставляются пустые записи, чтобы оставить место для вставок. Другой подход состоит в том, чтобы в некотором другом месте иметь некоторую область переполнения, а вставляемые записи связывать между собой. Однако для этого потребуется дополнительное поле указателя в каждой записи первоначальной таблицы. Возможное решение этой проблемы состоит в том, чтобы иметь только один указатель после каждой группы записей. Таким образом, если вставляется новая запись в соответствующее ей место, то все записи после вставленной сдвигаются на одну позицию. Если последняя запись данной группы попадает за пределы отведенной области, то она должна помещаться в область, на которую указывает указатель группы свободных ячеек.
