Индексированные файлы

В обоих предыдущих примерах записи идентифицировались и сравнивались по ключевому атрибуту — слову или числу. Стратегия поиска была основана на значениях самих ключевых атрибутов. Элементы, которые вы ищете в ГИС, это главным образом точки, линии и области. Однако вряд ли вы будете искать их по присвоенным им номерам. Другими словами, вы не будете запрашивать ГИС отобразить линию номер 3001 (ее порядковый номер при вводе в систему). Каждому объекту даются некие описательные атрибуты (характеристики), поэтому чаще всего ищутся элементы с определенным набором атрибутов. Так, например, вы могли бы попросить ГИС отыскать для отображения и анализа все земельные участки в отличном состоянии. Или вы могли бы выбрать участки в плохом состоянии, причем такие, у которых уклон меньше 25%.

Каждому объекту может быть приписано большое количество атрибутов, но мы физически не можем отсортировать записи в файле одновременно более чем одним способом. И если для того атрибута, по которому мы отсортировали массив записей, мы можем применить быстрый поиск делением пополам, то для всех других атрибутов нам придется выполнять утомительный последовательный поиск. Нам нужен какой-то выход, ведь мы же не можем пересортировывать файл для каждого запроса! Решение для этого существует -внешний индекс. Строится он вот как: из исходного файла в новый файл копируются значения одного атрибута для всех записей вместе с положениями этих записей. То есть каждая запись в новом файле состоит из значения атрибута и адреса записи в исходном файле, из которой это значение было взято. Затем нужно упорядочить записи нового файла в соответствии со значениями атрибута. Теперь, чтобы найти запись с заданным значением атрибута, мы можем в новом файле использовать поиск делением пополам. Найдя нужные записи в индексном файле, мы получим адреса записей исходного файла, по которым можем получить все атрибуты объектов. Таким образом, для поиска в основном файле используется дополнительный индексный файл, который называется внешним индексом, а сам исходный файл, таким образом, сталиндексированным.

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

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

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