Прямой метод

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

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

Индексные методы

В основе индексных методов доступа лежит создание вспомогательной структуры – индекса, содержащего ключи поиска и ссылки на физические адреса данных. Термин «ключ поиска» не обязательно подразумевает его уникальность, это просто атрибут (комбинация атрибутов), который должен удовлетворять критерию поиска. Используются понятия первичного (уникального) ключа, и вторичного, который не обязательно должен быть уникальным.

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

Индексы могут быть устроены по-разному. Различаются первичные и вторичные индексы в зависимости от вида ключа поиска. Если поиск и выборка производится по комбинации атрибутов (индексному выражению), соответствующий индекс называется составным. Индекс, построенный на иерархии ссылок, называется многоуровневым. Индекс, который содержит ссылки не на все записи, а на некоторый диапазон, называется неплотным. Плотный индекс содержит ссылки на все записи. Элемент индекса часто называют статьей.

Существует множество индексных методов доступа. Рассмотрим три из них: индексно-последовательный, индексно-произвольный и метод инвертированных списков.