6.1. Задача поиска информации и понятие об индексах

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

Преподаватели

Таким образом, длина всей записи постоянна - 102 байта.
В более сложном случае приходится использовать записи переменной дли¬ны, например:
Новости

Понятно, что на практике длина часто все же незначительно колеблется. В случае незначительных колебаний самое очевидное решение - резервировать место по максимуму, как мы поступили с полем ФИО в предыдущем примере. В случае же значительных колебаний используется механизм ссылок. Физически в этом случае создается вспомогательный файл, то есть на физическом уровне будет организовано 2 файла:

ТЕКСТЫ - данный файл состоит из записанных «друг за другом» текстов новостей. Доступ к конкретному тексту осуществляется по адресу, то есть по смещению от начала файла ТЕКСТЫ в байтах, при этом количество рассматриваемых байтов будет определяться длиной текста, также хранимой в таблице НОВОСТИ.
Примечание.
1. Говоря здесь о файлах, мы понимаем под файлом инструмент к доступу информации. СУБД могут использовать механизм файлов, поддерживаемый операционной системой или не использовать. В последнем случае внутри СУБД продублированы функции файловой системы, и работа может вестись с несколькими файлами с точки зрения СУБД, но вся база данных может находиться в одном файле с точки зрения операционной системы.
2. Очевидно, что приведенные здесь методы хранения информации решают эту проблему для простейшей модели данных - модели плоских файлов. На самом же деле именно этим методы применяются и для любой другой модели данных, только обычно требуется использование большего числа файлов. Так, при реализации реляционной модели, каждое отношение (таблица) хранится в отдельном файле.
На уровне систем управления файлами, как отмечалось в 1.7, решены задачи чтения из файла и записи в файл, к которым сводятся любые операции манипулирования данными независимо от используемых МД и ЯМД.
Но в тоже время на уровне стандартных систем управления файлами не решена задача эффективного (быстрого) доступа к нужной записи по значению какого-либо поля. Эта задача решается внутри СУБД.
Опишем задачу более формально. На входе даны файл и конкретное значение искомого элемента. На выходе требуется получить смещение требуемых данных внутри файла или непосредственно получить доступ к данным (практически тождественные задачи, так как смещение дает возможность получить доступ за 1 шаг). Например, дан файл:
 

Требуется найти телефон Зиминой.
Наиболее очевидный метод решения этой задачи - последовательный про¬смотр всех записей в файле.
Пример.

 ВХОД - f - файл. reset(f);

while not eof(f) do begin read(f,r);

if r.fio='3MMMHa' then begin return(OK); //задача решена break end end

Примечание. В наихудшем случае T~n , где n - число записей в таблице (в случае реляци­онной модели - число кортежей в отношении).

На практике в дополнение к таблице строятся специальные структуры дан­ных, облегчающие поиск. Эти структуры называются индексами, а способы их построения и использования в процессе поиска - методами индексации.

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