Индексация данных

структуре хранения, как при поиске элемента данных, так и при

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

отыскать в индексе его ключ, а потом получить сам блок,

который хранится по адресу, связанному с этим ключом

с помощью соответствующего бинарного дерева .Это бинарное дерево можно реализовать

в виде самостоятельного файла (или индекса). При этом операции поиска будут освобождены от необходимости каждый раз вычислять адреса записей.

К. Построим дополнительный файл FD по правилу 1) записи файла

FD имеют формат FD(K, Р), где К – поле, принимающее значение ключа первой записи блока основного файла F; Р – указатель на этот блок; 2) записи файла FD упорядочены по полю К.

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

индекс. Различие заключается в том, что для каждого значения ключа

К в файле FD имеется отдельная запись, а в неполном индексе - только для значения ключа первой записи блока. Над плотным индексом можно также построить В-дерево.

файла, а за тем этот блок считывает в оперативную память

и в нем, например, с помощью последовательного поиска, определяется требуемая запись.
В-дерево. Так как неплотный индекс упорядочен по ключевому полю, то над ним можно построить еще один неплотный индекс (неплотный индекс неплотного индекса) и т.д., пока на самом последнем, верхнем уровне не останется всего один блок

записей в блоке индекса. Такое дерево должно иметь в каждом

узле не менее т / 2 зависимых узлов и все листья должны располагаться на одном уровне. Для осуществления последовательного поиска блоки первого уровня могут быть связаны в цепь по возрастанию значения ключа.

не точное местоположение нужной информации. Например, это можно реализовать путем

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