Разработка и сопровождение баз данных в среде СУБД MS SQL Server 2000. Сивохин А.В - 35 стр.

содержит ключевое слово и номер страницы, на которой расположена нужная
информация. По такому же принципу устроен и индекс базы данных. Каждый
элемент индекса хранит значение, соответствующее значению индексированного
столбца конкретной строки, а также ссылку на исходную строку. Однако стоит
обратить внимание, что индекс производит упорядочивание только конкретного
столбца, а не всех данных таблицы.
    Практически все алгоритмы ускорения поиска данных работают только с
упорядоченными данными. Индексы позволяют упорядочить данные, даже если
физически данные сохранены без всякого порядка. В большинстве систем
управления данными индексы применяются автоматически.
    SQL Server 2000 не является исключением. Если в ходе выполнения запроса
происходит обращение к столбцу, для которого был определен индекс, то сервер
автоматически производит поиск нужных значений непосредственно не в таблице, а
в индексе. Когда в индексе находится искомое значение, сервер обращается к
соответствующей строке таблицы и выбирает нужные данные уже из нее. Хотя на
самом деле данные в столбце могут быть и неупорядочены, за счет того, что столбец
будет   иметь   индекс,   можно   реализовать   эффективные   алгоритмы   поиска
информации. Это как раз и сделано в SQL Server 2000.
    Одним из наиболее эффективных методов поиска, реализованных и в SQL
Server 2000, является метод “деления пополам”, работающий с упорядоченным
представлением данных, т.е. с индексами. При поиске конкретного значения в
отсортированном по возрастанию наборе в простейшем случае берется значение из
середины упорядоченной последовательности и сравнивается с искомым. Если
искомое значение больше, то все значения левее выбранного отбрасываются. Тем
самым промежуток поиска уменьшается вдвое. Искомое значение сравнивается со
значением, расположенным в центре правой области данных. Если значения опять
не совпали, то интервал снова уменьшается вдвое и процесс продолжается. Когда
значения, наконец, совпадут, поиск прекращается. Этот метод позволяет очень
быстро находить требуемые значения.
    Метод деления пополам можно оптимизировать, если при выборе начальной
точки выбирать не просто середину интервала, а применять специальные