Метод доступа с полным (плотным) индексом (или индексно-произвольный метод)
представляет собой такую организацию файла, при которой для каждого экземпляра записи в
файле предусмотрен соответствующий элемент индекса (рис. 28.). Этот элемент включает
значение ключа записи и указатель на блок, содержащий искомую запись. Обычно для
ускорения поиска в индексе его элементы упорядочиваются.
Достоинством данного метода доступа является произвольное расположение записей
данных в основном файле, что обеспечивает их физическую независимость при хранении.
Основной недостаток проявляется в тех случаях, когда:
1. Выдается оператор выборки всех или большинства записей, и при этом требуется
упорядочивание полученных данных.
2. Сложность процесса обновления основного файла, особенно при добавлении в него
новых записей (требуется перестройка индекса).
Доступ с неплотным индексом (индексно-последовательный метод доступа) строится на
основе физически упорядоченного по возрастанию значения ключей последовательного файла
и совокупности пронумерованных индексных элементов (индексе), каждый из которых
содержит ключ подобно записям основного файла; элементы в индексе упорядочиваются по
возрастанию значений ключей. Значение ключа в индексном элементе представляет
наибольший (или наименьший) из значений ключей записей, входящих в блок основного
файла с номером, совпадающим с номером индексного элемента.
Алгоритм поиска при данной организации файла очевиден и включает два этапа:
- Поиск в индексе элемента, указывающего на блок, в котором должна находиться искомая запись, используя максимальное (или минимальное) значение ключей записей, размещенных в блоках основного файла.
- Последовательный просмотр записей найденного блока.
Таким образом, к записям индексно-последовательного файла с помощью индекса осуществляется прямой доступ к блоку (странице), включающему требуемую запись, и последовательный доступ в соответствии с упорядоченностью записей по этому ключу индексирования.
Использование индексно-последовательной организации наиболее эффективно, когда модификация исходного файла не предполагает его расширения. В противном случае, как праавило, необходимо введение области переполнения, существование которой принципиально ломает простоту алгоритм поиска, присущую индексно-последоватльному методу доступа
Сравнение метода полного индекса с индексно-последовательной организацией
- В методе полного индекса не предусмотрена обработка переполнения; вместо этого всякий раз при включении новой записи в основной файл выполняется переупорядочивание индекса.
- При отсутствии переполнения поиск всех записей в обоих методах имеют одинаковую производительность.
- В обоих методах достаточно эффективно выполняется операция поиска записей с уникальными ключами.
- Вследствие физически последовательного размещения записей операции типа ПОЛУЧИТЬ СЛЕДУЮЩУЮ и ПОЛУЧИТЬ ПРЕДЫДУЩУЮ выполняются гораздо эффективнее в методе неплотного индекса.
- Добавление, а так же изменение значений первичных ключей в основном файле в обоих методах трудоемко, поскольку, как правило, влечет обновление индекса.