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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Например:

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

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