logo
Ответы на ИТ

Индексные файлы, двоичный поиск данных

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

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

Если ближайшее значение ключа в индексе больше искомого значения, то указатель перемещается в середину «верхней» половины таблицы, меньше – в середину «нижней» половины, и опять проводится сравнение.

Если в таблице Nзаписей , то при самом неблагоприятном варианте – искомое значение ключа будет в последней записи , придется проделатьNшагов. Для рассмотренного простейшего алгоритма максимальное число шагов при поиске –log2N

  1.