Физически последовательная организация

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

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

Основной недостаток физически-последовательной организации связан со сложностью расширения файла.

Связная последовательная организация

Позволяет размещать записи в несмежных участках памяти (рис.23.).

Таким образом, участки файла образуют список. Такая организация существенно облегчает процесс модификации файла (рис.24.).

На рисунке пунктирной линией обозначена связь, которая разрывается при добавлении новой записи с ключем 04.

Список может быть двусвязным (рис.25.). При такой организации появляется возможность эффективной реализации поиска предшествующей записи.

 

01 Иванов …

02 Петров …

03 Сидоров …

…

01, 02, 03 – значения первичного ключа.

Рис.22. Пример физически последовательной организации

 

Рис.23. Пример связной последовательной организации

 

 

Рис.24. Механизм добавления записи в связную последовательную структуру

 

 

 

 

Рис.25. Двусвязная последовательная организация

 

4. Опишите метод доступа – хеширование. В чем состоит проблема синонимов.

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

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

Пусть v есть значение ключа записи и h – Хеш-функция. Тогда h (v) - адрес участка, в котором должна находиться искомая запись (в том случае, если она присутствует вообще). Общая схема организации хешированного файла представлена на рис.26.

Проблема синонимов

при реализации Хеш-функции отношения 1:1 между значениями ключей и номерами участков размер справочника участков становиться неприемлемо большим, а величина самих участков неприемлемо малой=>к нерациональному расходу памяти.

Реальным выходом из этой ситуации является принятие соглашения, при котором в общем случае Хеш-функции осуществляет отображение типа 1:M; однако в этом случае фиксируется эффект возникновения синонимов, когда записи с различными значениями ключей направляются для хранения в один участок, что приводит, в конечном счете, к различной степени загруженности участков.

И, если при использовании связанной последовательной организации блоков внутри участков (именно такая организация представлена на рис.26.) наличие синонимов приводит, в основном, только к различию во времени поиска в пределах отдельных участков, то при использовании физически последовательной организации могут возникнуть дополнительные проблемы, связанные с необходимостью введения области переполнения (рис.27.).

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

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

5. Опишите метод доступа с полным индексом и индексно-последовательный метод доступа. Сравните эти методы. В чем достоинства и недостатки каждого из них.

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

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

 

 

Рис.28. Схема организации метода доступа с плотным индексом

Основной недостаток проявляется в тех случаях, когда:

1. Выдается оперетор выборки всех или большинства записей, и при этом требуется упорядочивание полученных данных.

2. Сложность процесса обновления основного файла, особенно при добавлении в него новых записей (требуется перестройка индекса).

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

Структура индексно-последовательного файла представлена на рис.29.Алгоритм поиска при данной организации файла очевиден и включает два этапа:

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

 

 

Рис.29. Схема организации индексно-последовательного файла

 

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

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

⇐ Предыдущая123456Следующая ⇒

Поделиться: