Поиск данных. Введение в поиск данных

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

Таблица или файл является некоторой группой элементов, каждый из которых представляется записью. С каждой записью ассоциируется некоторый ключ, который используется для того, чтобы отличить одну запись от другой. Соответствие между записью и ключом может быть простым или сложным. В простейшем случае ключ является некоторым полем внутри записи, располагающимся с некоторым конкретным сдвигом от начала записи. Такой ключ называется внутренним ключом или встроенным ключом. В других случаях ключом является относительная позиция записи внутри файла или имеется некоторая отдельная таблица ключей, которая содержит указатели на записи. Такие ключи называются внешними ключами. Для каждого файла имеется по крайней мере один набор ключей (возможно и несколько таких наборов), которые являются уникальными (т.е. никакие две записи в файле не имеют одинакового значения ключа). Такой ключ называется первичным ключом. Например, если файл хранится как некоторый массив, то индекс некоторого элемента в этом массиве является уникальным внешним ключом для этого элемента. Однако поскольку любое поле записи может служить в качестве ключа в каком-либо конкретном приложении, то ключи не всегда должны быть уникальными.

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

Алгоритмом поиска является такой алгоритм, который, воспринимая некоторый аргумент a, пытается локализовать некоторую запись, ключ которой равен а. Данный алгоритм может возвратить всю данную запись или чаще всего может возвратить некоторый указатель на эту запись. Успешный поиск называется извлечением. В противном случае алгоритм может возвратить некоторую специальную «пустую запись» или некоторый пустой указатель. Однако чаще такое условие приводит к появлению некоторой ошибки или установке во флаге некоторого конкретного значения, которое указывает, что данная запись отсутствует. Если поиск закончился неудачно, то часто бывает желательно добавить некоторую новую запись с этим аргументом в качестве ключа. Алгоритм, который выполняет эту функцию, называется алгоритмом поиска и вставки [3].

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