Методы адресации данных по первичному ключу

1) Последовательное сканирование файла(поиск) он заключается в последовательной проверке всех записей на соответствие некоторому условию поиска Q.

Записи, удовлетворяющие этому условию, выдаются в качестве результата.

Существуют различные виды поиска:

а)поиск по равенству К=а

б)поиск по интервалу значений а К b

в)поиск по множеству значений К=a_i, i=1…n

2) Блочный поиск.

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

3) Бинарный поиск

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

4) Поиск по бинарному дереву.

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

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

Основной файл F упорядочен по ключу. На его основе строится новый файл FB, в котором все записи упорядочены по ключу и формат записи этого файла имеет вид (к,р’), где К- поле, принимающее значение ключа 1-ой записи блока основного файла F, р- указатель на этот блок. Полученный файл называют неплотным индексом.

Например:

6) Индексно-произвольный файл(плотный индекс)

Исходный файл F не упорядочен по ключу. Доп. файл строится как и в предыдущем случае, только К- ключ записи основного файла.