Прямые методы доступа. Классификация методов индексирования
Индекс - зто вспомогательная структура данных в, файловых системах, среде хранения базы данных, средах хранилищ данных других типов, служащая для:
повышения производительности выполнения операций поиска данных, удовлетворяющих заданному критерию,
обеспечения обработки данных в соответствии с порядком значений ключа и/или вычисления различных статистических характеристик, зависящих только от значений ключей.
Следует заметить, что повышение производительности системы хранения данных при использовании техники индексирования достигается за счет выделения дополнительных ресурсов памяти для хранения индексов, а также вычислительных ресурсов для их модификации при выполнении операций вставки, удаления и обновления данных.
Используются различные подходы к организации индексов, ориентированные на поддержку различных операций доступа к данным в среде хранения. Классификацию индексов можно провести по разным основаниям. При этом различают:
по уровням
одноуровневые индексы, в записях (статьях) которых непосредственно используются адреса индексируемых объектов и пространств памяти базы данных,
многоуровневые индексы, организованные в виде дерева страниц памяти; в статьях страниц-листьев этого дерева содержатся указатели самих индексируемых объектов данных, а в страницах (блоках) более высоких уровней – указатели номеров страниц более низкого уровня, где нужно продолжать поиск.
по значению ключей
первичный индекс файла по значению первичного ключа; каждой статье такого индекса соответствует единственная (уникальная) запись в файле,
вторичный индекс файла по значению вторичного ключа; поскольку значения вторичного ключа не являются уникальными, каждой статье вторичного индекса может соответствовать, вообще говоря, несколько записей файла.
по способу организации
плотный (или полный) индекс, включающий явным образом статьи для всех актуальных (имеющихся на данный момент) значений ключа индексирования,
неплотный (или неполный, разреженный) индекс, содержащий статьи не для всех актуальных значений ключа индексирования, а только для их диапазонов; тем самым индекс указывает не точный адрес данных в среде хранения, а некоторую достаточно ограниченную область (например, страницу), где они содержатся,
индекс со структурой В-дерева; многоуровневый индекс, в котором страницы верхних уровней являются разреженными индексами страниц следующего нижнего уровня, а страницы самого нижнего уровня (листья дерева) образуют, по существу, плотный индекс для индексируемого множества записей,
индекс на битовых шкалах (битовый индекс).
Одна организация индекса отличается от другой, главным образом, в способе поиска ключа с заданным значением. В следующих пунктах этого раздела рассматриваются основные методы доступа с использованием первичного индекса.
Доступ с полным (плотным) индексом
Метод доступа с полным (плотным) индексом (или индексно-произвольный метод) представляет собой такую организацию файла, при которой для каждого экземпляра записи в файле предусмотрен соответствующий элемент индекса (рис. 28.). Этот элемент включает значение ключа записи и указатель на блок, содержащий искомую запись. Обычно для ускорения поиска в индексе его элементы упорядочиваются.
Достоинством данного метода доступа является произвольное расположение записей данных в основном файле, что обеспечивает их физическую независимость при хранении.
Основной недостаток проявляется в тех случаях, когда:
Выдается оперетор выборки всех или большинства записей, и при этом требуется упорядочивание полученных данных.
Сложность процесса обновления основного файла, особенно при добавлении в него новых записей (требуется перестройка индекса).
Рис.28. Схема организации метода доступа с плотным индексом