Индексно-последовательный поиск

Для увеличения эффективности поиска в отсортированном файле существует другой метод, но он приводит к увеличению требуемой памяти. Этот метод называетсяиндексно-последовательным методом поиска. В дополнение к отсортированной основной таблице (файлу) организуется некоторая вспомогательная таблица, называемаяиндексом. Каждый элемент индекса состоит из ключа kindex и указателя на запись в файле, соответствующую этому ключу pindex. Элементы в индексе, так же как и элементы в файле, должны быть отсортированы по этому ключу. Если индекс имеет размер, составляющий одну шестую от размера файла, то каждая шестая запись в файле представлена первоначально в индексе. Это показано на рисунке 10.1.

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

Индекс применяется для отсортированной таблицы, представленной и в виде связанного списка, и в виде массива. Использование связанного списка приводит к несколько большим накладным расходам по памяти для указателей, хотя вставки и удаления могут быть выполнены проще. Может также использоваться некоторая смешанная реализация, при которой все записи между двумя соседними элементами индекса хранятся в небольшой отдельной таблице, которая также содержит указатель на следующую такую же таблицу.

Рисунок 10.1 – Индексно-последовательная таблица

Если таблица является такой большой, что даже использование индекса не дает достаточной эффективности, то может быть использован индекс второго уровня (вторичный индекс). Индекс второго уровня действует как индекс для первичного индекса, который указывает на элементы в основной таблице. Это показано на рисунке 10.2.

Причины для организации вторичного индекса две: либо индекс большой, чтобы уменьшить последовательный поиск по таблице, либо индекс маленький, так что соседние ключи в индексе находятся далеко друг от друга в таблице.

Вставка элемента в индексно-последовательную таблицу является довольно трудной, поскольку между двумя уже существующими элементами таблицы может не быть свободного места, что приводит к необходимости сдвигать большое число элементов таблицы. Однако если некоторый недалеко расположенный элемент в таблице был отмечен флагом как удаленный, то необходимо сдвинуть только несколько элементов и поверх удаленного элемента может быть записана новая информация. Это в свою очередь может привести к необходимости изменения индекса, если элемент, на который указывал некоторый элемент индекса, был сдвинут. В общем случае, когда инициализируется некоторая таблица, по всей таблице расставляются пустые записи, чтобы оставить место для вставок. Другой метод состоит в том, чтобы в некотором другом месте иметь некую область переполнения, а вставляемые записи связывать между собой. Однако для этого потребуется дополнительное поле указателя в каждой записи первоначальной таблицы. Возможное решение этой проблемы состоит в том, чтобы иметь только один указатель после каждой группы записей, вставлять новую запись в ее соответствующее место, а все записи после вставленной записи сдвигать вперед на одну позицию. Если последняя запись данной группы сдвигается, то она помещается в область переполнения, на которую указывает один указатель в группе.

Рисунок 10.2 – Использование вторичного индекса

Удаления из индексно-последовательной таблицы могут быть сделаны наиболее простым способом - при помощи отметки удаленных записей флагом. При последовательном поиске по таблице удаленные записи игнорируются. Отметим, что если некоторый элемент удален, то, даже если его ключ находится в индексе, ничего не надо делать с индексом, а надо отметить флагом данный элемент первоначальной таблицы.